คลังเก็บป้ายกำกับ: Non-Deterministic Polynomial

ปัญหา P กับ NP

ผมต้องส่งการบ้านในหัวข้อ “งานวิจัย NP ในปัจจุบัน” พอค้น ๆ ไปในอินเทอร์เน็ตถึงได้พบว่า อย่าว่าแต่ของคนไทยเลย ขนาดของพวกฝรั่งก็ยังเขียนลำดับให้เข้าใจไม่ค่อยได้ คือ เขาจะเขียนข้าม ๆ เป็นห้วง ๆ ไม่ลำดัีบเป็นขั้น ๆ เขาจะถือว่ารู้แล้ว (ซึ่งจริง ๆ เราไม่รู้) ดังนั้น ผมก็เลยต้องอ่านจากหลาย ๆ ที่ แล้วเอามาประมวลเป็นลำดับขั้นตอนเพื่อส่งการบ้าน ทีนี้เห็นว่ามันน่าจะเอามาเผยแพร่ได้ ให้คนทั่วไปเข้าใจได้ง่าย ๆ (เอ๊ะ หรือจะไม่ง่าย?) ก็เลยคิดว่าเอามาลงในบล็อกของตัวเองดีกว่า

งั้นเริ่มเลยล่ะกัน …

1.  บทคัดย่อ

ในวงการวิทยาการคอมพิวเตอร์ หากเรากล่าวถึง “ปัญหา” จะมีสิ่งให้ขบคิดอยู่สองประเด็น นั่นคือ เราจะหาคำตอบของปัญหานั้น ๆ อย่างมีประสิทธิภาพได้อย่างไร และ หากมีการเฉลยคำตอบของปัญหานั้น ๆ แล้ว เราจะหาวิธียืนยันคำตอบนั้น ๆ อย่างมีประสิทธิภาพได้อย่างไร ว่ามันเป็นคำตอบที่ “ใช่” หรือ “ไม่ใช่” ซึ่งกลุ่มของปัญหาที่ต้องการ ๆ ยืนยันคำตอบอย่างมีประสิทธิภาพหากคำตอบคือ “ใช่” จะถูกเรียกในทางทฤษฎีว่าเป็นกลุ่มปัญหา NP หรือ Non-deterministic polynomial time ซึ่งในบทความนี้จะนำเสนอถึงการวิจัย NP ในปัจจุบัน ว่ามีความก้าวหน้าไปอย่างไรบ้าง

2.  บทนำ

วิทยาการคอมพิวเตอร์เป็นศาสตร์ที่ใช้คณิตศาสตร์หลายแขนง เพื่อช่วยในการแก้ปัญหาให้กับศาสตร์ของตนเอง โดยเฉพาะการใช้ศาสตร์ที่เรียกว่า Combinatorics ในการแก้ปัญหา โดยเนื้อหาหลักของ Combinatorics ก็คือ “การจัดหมู่” ในสิ่งที่มีขอบเขต “จำกัด” จากนั้นจึงทำการ “นับ” มัน

ปัจจัยสำคัญใน “การนับ” ในทางวิทยาการคอมพิวเตอร์ก็คือการวนรอบ เพราะคุณลักษณะเด่นของคอมพิวเตอร์ก็คือ การที่สามารถวนรอบทำงานซ้ำ ๆ ได้ โดยไม่เหน็ดเหนื่อยและผิดพลาด ดังนั้น เมื่อมีการวนรอบก็จะหมายถึงการต้องเสียเวลา การวนรอบ 1 ชั้นก็หมายถึงการเสียเวลาน้อยกว่าหรือเท่ากับ n รอบ และการวนรอบ 2 ชั้นก็อาจหมายถึงการเสียเวลาน้อยกว่าหรือเท่ากับ n^2 รอบ เป็นต้น

ด้วยรูปแบบของการวนรอบเพื่อนับ จึงทำให้สามารถมองได้ว่าปัญหาส่วนใหญ่ในทางวิทยาการคอมพิวเตอร์ สามารถแก้ได้ในเวลา Polynomial Time แต่การแก้ปัญหาจะไม่ถือว่ามีประสิทธิภาพ หากใช้เวลาในการแก้ปัญหาเกินกว่าจะยอมรับได้ เช่นในการแก้ปัญหา Travelling Salesman Problem ที่กำหนดให้พนักงานขายเลือกเส้นทางที่สั้นที่สุด เพื่อเดินทางไปทีล่ะเมืองให้ครบทุกเมืองโดยไม่ซ้ำ แล้วย้อนกลับมายังเมืองที่ตั้งต้น ซึ่งการหาผลเฉลยที่ถูกต้องที่สุดก็คือการตรวจในทุก ๆ เส้นทางที่เป็นไปได้ แล้วเลือกเส้นทางที่สั้นที่สุดจากการตรวจสอบทั้งหมด โดยต้องใช้จำนวนรอบเพื่อหาผลเฉลยเท่ากับ n! ซึ่งหากมีจำนวนของเมือง 100 เมืองให้เดินทาง ก็หมายถึงการที่ต้องค้นหาผลเฉลยด้วยจำนวนรอบเท่ากับ 100! ซึ่งใช้เวลาที่มากเกินกว่าจะยอมรับได้

ดังนั้น ในทางทฤษฎีจึงเกิดแนวความคิดว่า ถ้ายังคงต้องการแก้ปัญหาที่ใช้เวลามาก ๆ ใน Polynomial Time ได้อย่างมีประสิทธิภาพ (และเราก็เชื่อว่ายังไงก็ต้องแก้แบบ Polynomial Time จนกว่ามันจะมีวิธีอื่นมาแทนที่ เช่น Quantum อะไรประมาณนั้น) จำเป็นอย่างยิ่งที่จะต้องเปลี่ยนแนวคิดของเครื่องจักรทางทฤษฎีที่ใช้ขับเคลื่อนการแก้ปัญหา จากเดิมที่ใช้เครื่องจักรทางทฤษฎีในการแก้ปัญหาที่มีกลไกเคลื่อนที่ 1 State เกิด 1 Action หรือที่เรียกว่า Deterministic Turing Machine ให้กลายเป็นเครื่องจักรทางทฤษฎีในการแก้ปัญหา ที่มีกลไกเคลื่อนที่ 1 State เกิดได้หลาย Action หรือที่เรียกว่า Non-deterministic Turing Machine

ซึ่งการแก้ปัญหาใน Polynomial Time บนเครื่องจักรทางทฤษฎีแบบ Non-deterministic Turing Machine จึงเรียกว่าเป็นการแก้ปัญหาแบบ Non-deterministic Polynomial Time หรือ NP และปัจจุบันก็มีงานวิจัยในหลากหลายแขนงวิชา ที่กำลังค้นคว้าวิจัยกลุ่มปัญหา NP อยู่ในขณะนี้ ดังจะกล่าวในหัวข้อถัดไป

อ่านเพิ่มเติม ปัญหา P กับ NP