ปัญหา P เทียบกับ NP
ปัญหา P เทียบกับ NP เป็นคำถามที่ว่าปัญหาทุกอย่างที่สามารถตรวจสอบคำตอบได้อย่างรวดเร็ว สามารถแก้ไขได้อย่างรวดเร็วด้วยหรือไม่ ซึ่งเป็นคำถามเปิดที่สำคัญที่สุดของวิทยาการคอมพิวเตอร์เชิงทฤษฎี และเป็นหนึ่งในปัญหา Clay Millennium Prize
Definition
P คือคลาสของปัญหาที่สามารถแก้ไขได้ในเวลาพหุนาม และ NP คือคลาสของปัญหาที่คำตอบที่เสนอสามารถตรวจสอบได้ในเวลาพหุนาม ปัญหา P เทียบกับ NP ถามว่าคลาสทั้งสองนี้เท่ากันหรือไม่ ซึ่งจะเป็นจริงก็ต่อเมื่อปัญหา NP-สมบูรณ์บางอย่างสามารถแก้ไขได้ในเวลาพหุนาม
Scope
หัวข้อนี้ครอบคลุมถึงการระบุอย่างเป็นทางการของ P เทียบกับ NP ความเท่าเทียมกันกับคำถามที่ว่าปัญหา NP-สมบูรณ์ใดๆ มีอัลกอริทึมเวลาพหุนามหรือไม่ ผลที่ตามมาของคำตอบทั้งสองอย่าง อุปสรรคต่างๆ เช่น การทำให้เป็นสัมพัทธ์ (relativization) การพิสูจน์ตามธรรมชาติ (natural proofs) และการทำให้เป็นพีชคณิต (algebrization) ที่ขัดขวางความก้าวหน้า และข้อสันนิษฐานที่แพร่หลายว่าคลาสทั้งสองแตกต่างกัน
Core questions
- การค้นหาคำตอบนั้นยากกว่าการตรวจสอบคำตอบโดยพื้นฐานหรือไม่?
- เหตุใดคำตอบจึงขึ้นอยู่กับว่าปัญหา NP-สมบูรณ์เพียงปัญหาเดียวอยู่ใน P หรือไม่?
- โลกจะเป็นอย่างไรหาก P เท่ากับ NP และหากไม่เท่ากัน?
- เหตุใดความพยายามหลายทศวรรษจึงไม่สามารถแก้ไขคำถามนี้ได้?
Key theories
- ความเท่าเทียมกันกับ NP-completeness
- P เท่ากับ NP ก็ต่อเมื่อปัญหา NP-สมบูรณ์ใดๆ มีอัลกอริทึมเวลาพหุนาม ดังนั้นคำถามที่ครอบคลุมจึงลดลงเหลือเพียงความสามารถในการแก้ไขปัญหาที่เป็นรูปธรรมเพียงปัญหาเดียว เช่น ปัญหาความพึงพอใจ (satisfiability)
- อุปสรรคในการพิสูจน์
- ผลลัพธ์ของการทำให้เป็นสัมพัทธ์ การพิสูจน์ตามธรรมชาติ และการทำให้เป็นพีชคณิต แสดงให้เห็นว่าเทคนิคการพิสูจน์หลักที่รู้จักไม่สามารถตัดสินปัญหา P เทียบกับ NP ได้ ซึ่งอธิบายถึงความยากลำบากและเป็นแนวทางในการค้นหาวิธีการใหม่ๆ โดยพื้นฐาน
Clinical relevance
ความไม่เท่าเทียมกันของ P และ NP ที่สันนิษฐานไว้เป็นสมมติฐานเบื้องหลังการพิจารณาปัญหา NP-hard ว่าแก้ไขได้ยาก และเบื้องหลังความปลอดภัยของการเข้ารหัส เนื่องจากหากสามารถแก้ไขปัญหา NP ได้อย่างมีประสิทธิภาพ จะทำให้การเข้ารหัสที่ใช้กันอย่างแพร่หลายถูกทำลายได้ การพิสูจน์เชิงสร้างสรรค์ว่า P เท่ากับ NP จะเปลี่ยนแปลงการเพิ่มประสิทธิภาพ โลจิสติกส์ และวิทยาศาสตร์อย่างมาก
History
คุกได้ตั้งคำถามนี้ในปี 1971 ควบคู่ไปกับ NP-completeness และได้รับการยอมรับอย่างรวดเร็วว่าเป็นพื้นฐาน ความพยายามผ่านขอบเขตล่างของวงจร (circuit lower bounds) ในทศวรรษ 1980 ได้พบกับอุปสรรคของการพิสูจน์ตามธรรมชาติที่ระบุโดย Razborov และ Rudich และในปี 2000 สถาบันคณิตศาสตร์เคลย์ (Clay Mathematics Institute) ได้กำหนดให้เป็นปัญหา Millennium Prize พร้อมรางวัลหนึ่งล้านดอลลาร์
Debates
- ปัญหา P เทียบกับ NP จะได้รับการแก้ไขหรือไม่ และคำตอบคืออะไร?
- นักวิจัยส่วนใหญ่คาดการณ์ว่า P ไม่เท่ากับ NP แต่ยังไม่มีการพิสูจน์ และเทคนิคที่รู้จักก็ไม่เพียงพออย่างเห็นได้ชัด ความคิดเห็นแตกต่างกันไปว่าการแก้ไขใกล้เข้ามาแล้วหรือไม่ ต้องใช้คณิตศาสตร์ใหม่โดยสิ้นเชิง หรือคำถามนี้อาจเป็นอิสระจากสัจพจน์มาตรฐานด้วยซ้ำ
Key figures
- Stephen Cook
- Leonid Levin
- Richard Karp
- Alexander Razborov
Related topics
Seminal works
- cook1971
- aroraBarak2009
Frequently asked questions
- จะเกิดอะไรขึ้นหาก P เท่ากับ NP?
- ปัญหาหลายอย่างที่เชื่อว่าแก้ไขได้ยากในปัจจุบัน ตั้งแต่การจัดตารางเวลาที่เหมาะสมที่สุดไปจนถึงการถอดรหัสลับ จะมีอัลกอริทึมที่มีประสิทธิภาพ และการค้นหาคำตอบจะไม่ยากไปกว่าการตรวจสอบคำตอบ ผลกระทบต่อการค้า ความปลอดภัย และวิทยาศาสตร์จะลึกซึ้ง ซึ่งเป็นส่วนหนึ่งที่ทำให้ผู้เชี่ยวชาญส่วนใหญ่คาดว่า P จะไม่เท่ากับ NP
- เหตุใดปัญหาจึงแก้ไขได้ยากมาก?
- การพิสูจน์ว่า P เท่ากับ NP ต้องใช้อัลกอริทึมที่รวดเร็วสำหรับปัญหา NP-สมบูรณ์ ซึ่งยังไม่มีใครค้นพบ การพิสูจน์ว่าแตกต่างกันต้องแสดงให้เห็นว่าไม่มีอัลกอริทึมดังกล่าวอยู่จริง ผลลัพธ์เกี่ยวกับการทำให้เป็นสัมพัทธ์และการพิสูจน์ตามธรรมชาติแสดงให้เห็นว่าเทคนิคมาตรฐานไม่สามารถสร้างสิ่งหลังได้โดยเนื้อแท้ ดังนั้นจึงจำเป็นต้องมีแนวทางใหม่โดยแท้จริง