ความสมบูรณ์ของ NP และการลดรูป

ปัญหาที่สมบูรณ์ของ NP (NP-complete problem) เป็นหนึ่งในปัญหาที่ยากที่สุดในกลุ่ม NP ในแง่ที่ว่าปัญหา NP ทุกปัญหาจะลดรูปไปเป็นปัญหานี้ได้อย่างมีประสิทธิภาพ ดังนั้น การแก้ปัญหา NP-complete เพียงปัญหาเดียวได้อย่างรวดเร็วจะสามารถแก้ปัญหาทั้งหมดได้

Definition

ปัญหาจะถือว่าเป็น NP-complete หากปัญหานั้นอยู่ในกลุ่ม NP และปัญหาทุกปัญหาในกลุ่ม NP สามารถลดรูปไปเป็นปัญหานั้นได้ด้วยการลดรูปในเวลาพหุนาม ปัญหาดังกล่าวเป็นสมาชิกที่ยากที่สุดของ NP ซึ่งเทียบเท่ากันในการแปลงที่มีประสิทธิภาพ

Scope

หัวข้อนี้ครอบคลุมกลุ่มปัญหา NP ที่สามารถตรวจสอบได้ในเวลาพหุนาม (polynomial time), การลดรูปแบบหนึ่งต่อหลายในเวลาพหุนาม (polynomial-time many-one reductions), ทฤษฎีบท Cook–Levin ที่ระบุว่าปัญหาความพึงพอใจ (satisfiability) เป็นปัญหา NP-complete, รายการปัญหาการจัดหมู่ (combinatorial problems) ที่เป็น NP-complete ของ Karp, และระเบียบวิธีในการพิสูจน์ว่าปัญหาใหม่เป็น NP-complete โดยการลดรูปจากปัญหาที่ทราบแล้ว

Core questions

• การที่ปัญหาใดปัญหาหนึ่งเป็นหนึ่งในปัญหาที่ยากที่สุดใน NP หมายความว่าอย่างไร?
• ทฤษฎีบท Cook–Levin ระบุปัญหา NP-complete ปัญหาแรกได้อย่างไร?
• การลดรูปถูกนำมาใช้เพื่อพิสูจน์ว่าปัญหาใหม่เป็น NP-complete ได้อย่างไร?
• เหตุใดความสมบูรณ์ของ NP ของปัญหาหนึ่งจึงส่งผลกระทบต่อปัญหาอื่นๆ อีกหลายพันปัญหา?

Key theories

ทฤษฎีบท Cook–Levin

ปัญหาความพึงพอใจแบบบูลีน (Boolean satisfiability) เป็น NP-complete เนื่องจากสามารถเข้ารหัสการคำนวณของตัวตรวจสอบใดๆ ที่ใช้เวลาพหุนามให้เป็นอินสแตนซ์ของปัญหาความพึงพอใจได้ ซึ่งเป็นปัญหาพื้นฐานที่สมบูรณ์ซึ่งปัญหาอื่นๆ ได้รับการอนุมานมา

การลดรูปของ Karp และเครือข่ายของปัญหา NP-complete

คาร์ปแสดงให้เห็นว่าปัญหาธรรมชาติยี่สิบเอ็ดปัญหา ตั้งแต่การระบายสีกราฟ (graph coloring) ไปจนถึงปัญหาการตัดสินใจของพนักงานขายเดินทาง (traveling salesman decision problem) เป็น NP-complete โดยการลดรูปในเวลาพหุนาม ซึ่งเป็นการเริ่มต้นการสร้างความยากผ่านเครือข่ายการลดรูปที่กำลังเติบโต

Clinical relevance

ความสมบูรณ์ของ NP เป็นการวินิจฉัยเชิงปฏิบัติของความไม่สามารถจัดการได้ (intractability) เมื่อปัญหาในการจัดตารางเวลา โลจิสติกส์ การออกแบบ หรือการตรวจสอบแสดงให้เห็นว่าเป็น NP-complete วิศวกรจะหยุดแสวงหาอัลกอริทึมที่แน่นอนและรวดเร็ว และหันไปใช้อัลกอริทึมประมาณค่า (approximation algorithms) ฮิวริสติกส์ (heuristics) ตัวแก้ปัญหาการเขียนโปรแกรมจำนวนเต็ม (integer-programming solvers) หรือข้อจำกัดที่ทำให้ปัญหาสามารถจัดการได้

History

คุก (Cook) พิสูจน์ว่าปัญหาความพึงพอใจเป็น NP-complete ในปี 1971 และเลวิน (Levin) ได้ผลลัพธ์ที่เทียบเท่ากันโดยอิสระในสหภาพโซเวียต ในปี 1972 คาร์ป (Karp) ได้แสดงให้เห็นปัญหา NP-complete เพิ่มเติมอีกยี่สิบเอ็ดปัญหา ซึ่งเผยให้เห็นถึงความแพร่หลายของปรากฏการณ์นี้ และทำให้ความสมบูรณ์ของ NP เป็นเครื่องมือหลักในการวินิจฉัยความยากในการคำนวณ

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp

Seminal works

• cook1971
• karp1972

Frequently asked questions

NP ย่อมาจากอะไร?

NP ย่อมาจาก nondeterministic polynomial time หรือกล่าวอีกนัยหนึ่งคือ ปัญหาอยู่ในกลุ่ม NP หากสามารถตรวจสอบคำตอบที่เสนอได้ในเวลาพหุนาม แม้ว่าการค้นหาคำตอบอาจดูยากก็ตาม ตัวอย่างเช่น เส้นทางของพนักงานขายเดินทางที่สั้นกว่าความยาวที่กำหนดนั้นง่ายต่อการตรวจสอบเมื่อได้รับ แต่ดูเหมือนจะยากที่จะค้นพบ

คุณจะพิสูจน์ได้อย่างไรว่าปัญหาใหม่เป็น NP-complete?

คุณต้องแสดงสองสิ่ง: หนึ่งคือปัญหานั้นอยู่ในกลุ่ม NP ซึ่งหมายความว่าสามารถตรวจสอบคำตอบที่เป็นไปได้อย่างรวดเร็ว และสองคือปัญหา NP-complete ที่ทราบแล้วบางปัญหาลดรูปไปเป็นปัญหานั้นได้ในเวลาพหุนาม การลดรูปนี้จะถ่ายทอดความยากที่ทราบแล้ว ทำให้ปัญหาใหม่เป็นหนึ่งในปัญหาที่ยากที่สุดใน NP