ความสมบูรณ์ของ NP และความไม่สามารถจัดการได้

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

Definition

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

Scope

หัวข้อนี้ครอบคลุมคลาสความซับซ้อน P และ NP, การลดรูปในเวลาพหุนาม, คำจำกัดความของ NP-hardness และ NP-completeness, ทฤษฎีบท Cook-Levin ที่ยืนยันว่าปัญหาความพึงพอใจ (satisfiability) เป็น NP-complete, รายการปัญหา NP-complete ของ Karp, และผลกระทบเชิงปฏิบัติของความไม่สามารถจัดการได้ต่อการออกแบบอัลกอริทึม โดยจะนำแนวคิดเหล่านี้ไปใช้ในการรับรู้และจัดการกับปัญหาที่ยาก; ทฤษฎีที่เป็นทางการที่กว้างขึ้นของคลาสความซับซ้อนในการคำนวณจะได้รับการกล่าวถึงในสาขาย่อยทฤษฎีการคำนวณ

Core questions

• อะไรคือความแตกต่างระหว่างคลาสความซับซ้อน P และ NP?
• การลดรูปในเวลาพหุนามถ่ายทอดความยากจากปัญหาหนึ่งไปยังอีกปัญหาหนึ่งได้อย่างไร?
• ทฤษฎีบท Cook-Levin ยืนยันอะไร และเหตุใดความพึงพอใจจึงเป็นศูนย์กลาง?
• ปัญหาใหม่ได้รับการพิสูจน์ว่าเป็น NP-complete โดยการลดรูปจากปัญหาที่ทราบได้อย่างไร?
• เมื่อปัญหาได้รับการแสดงว่าเป็น NP-hard แล้ว กลยุทธ์อัลกอริทึมใดบ้างที่ยังคงอยู่?

Key concepts

• คลาสความซับซ้อน P
• คลาสความซับซ้อน NP
• การลดรูปในเวลาพหุนาม
• NP-hardness
• NP-completeness
• ทฤษฎีบท Cook-Levin
• ความพึงพอใจแบบบูลีน (SAT)
• คำถาม P เทียบกับ NP

Key theories

ทฤษฎีบท Cook-Levin

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

ความสามารถในการลดรูปในหมู่ปัญหาเชิงการจัดหมู่

Karp แสดงให้เห็นว่าการลดรูปในเวลาพหุนามเชื่อมโยงปัญหาธรรมชาติหลายอย่าง เช่น clique, vertex cover, Hamiltonian cycle, partition และอื่น ๆ เข้าด้วยกันเป็นเครือข่ายของปัญหา NP-complete ดังนั้นแต่ละปัญหาจึงสามารถพิสูจน์ความยากได้โดยการลดรูปจากปัญหาอื่น

Clinical relevance

การรับรู้ว่าปัญหาเป็น NP-complete เป็นหนึ่งในผลลัพธ์ที่มีประโยชน์ในทางปฏิบัติมากที่สุดในการคำนวณ: มันบอกวิศวกรว่าไม่ควรคาดหวังอัลกอริทึมที่รวดเร็วและแม่นยำ แต่ควรใช้อัลกอริทึมประมาณค่า, ฮิวริสติก, ตัวแก้ที่แม่นยำที่ปรับแต่งสำหรับกรณีทั่วไป, หรือการจำกัดเฉพาะกรณีพิเศษที่จัดการได้ ปัญหาการจัดตารางเวลา, การกำหนดเส้นทาง, การบรรจุหีบห่อ และการออกแบบจำนวนมากเป็น NP-complete

History

Stephen Cook ได้นำเสนอแนวคิด NP-completeness ในปี 1971 โดยพิสูจน์ว่า SAT เป็น NP-complete; Leonid Levin ได้ผลลัพธ์ที่คล้ายกันโดยอิสระ บทความของ Richard Karp ในปี 1972 แสดงให้เห็นว่ามีปัญหาธรรมชาติ 21 ปัญหาที่เป็น NP-complete ซึ่งเป็นการสร้างขอบเขตของกรอบแนวคิดนี้ หนังสือของ Garey และ Johnson ในปี 1979 ได้รวบรวมปัญหา NP-complete หลายร้อยปัญหาและกลายเป็นแหล่งอ้างอิงมาตรฐาน

Debates

P เทียบกับ NP

ไม่ว่า P จะเท่ากับ NP หรือไม่ — ไม่ว่าทุกปัญหาที่ตรวจสอบได้อย่างมีประสิทธิภาพจะสามารถแก้ไขได้อย่างมีประสิทธิภาพด้วยหรือไม่ — เป็นปัญหาที่ยังไม่ได้รับการแก้ไขที่สำคัญที่สุดในสาขานี้; นักวิจัยเกือบทั้งหมดคาดการณ์ว่า P ไม่เท่ากับ NP แต่คำถามนี้ยังไม่ได้รับการแก้ไขและเป็นปัญหา Millennium Prize

Key figures

• Stephen Cook
• Richard Karp
• Leonid Levin
• Michael Garey
• David Johnson

Seminal works

• cook1971
• karp1972
• cormen2009

Frequently asked questions

อะไรคือความแตกต่างระหว่าง NP-hard และ NP-complete?

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

NP-completeness หมายความว่าปัญหาไม่สามารถแก้ไขได้เลยหรือไม่?

ไม่ มันหมายความว่ายังไม่มีอัลกอริทึมเวลาพหุนามที่เป็นที่รู้จักสำหรับอินพุตทั้งหมด และมีแนวโน้มว่าจะไม่มีอยู่จริงหาก P ไม่เท่ากับ NP ในทางปฏิบัติ ปัญหาดังกล่าวจะได้รับการแก้ไขด้วยอัลกอริทึมประมาณค่า, ฮิวริสติก, ตัวแก้เวลาเอ็กซ์โพเนนเชียลที่ทำงานได้ในกรณีที่เป็นจริง, หรือโดยการจำกัดเฉพาะกรณีพิเศษ