ทฤษฎีความซับซ้อนในการคำนวณ

ทฤษฎีความซับซ้อนในการคำนวณจำแนกปัญหาตามปริมาณเวลา หน่วยความจำ และทรัพยากรอื่น ๆ ที่อัลกอริทึมใด ๆ ต้องการในการแก้ปัญหา โดยแบ่งแยกอย่างชัดเจนระหว่างสิ่งที่สามารถแก้ไขได้อย่างมีประสิทธิภาพและสิ่งที่ดูเหมือนจะแก้ไขได้ยาก

Definition

ทฤษฎีความซับซ้อนในการคำนวณศึกษาความยากโดยธรรมชาติของปัญหาการคำนวณ ซึ่งวัดจากทรัพยากร โดยหลักคือเวลาทำงานและหน่วยความจำที่จำเป็นในการแก้ปัญหาบนแบบจำลอง เช่น เครื่องจักรทัวริง (Turing machine) และจัดกลุ่มปัญหาออกเป็นคลาสความซับซ้อนตามนั้น

Scope

สาขานี้ครอบคลุมคลาสความซับซ้อนด้านเวลาและพื้นที่ เช่น P, NP, PSPACE และลำดับชั้นพหุนาม (polynomial hierarchy), ทฤษฎีความสมบูรณ์ของ NP (NP-completeness) และการลดรูปพหุนามเวลา (polynomial-time reductions), คำถามหลัก P เทียบกับ NP (P versus NP), และแบบจำลองที่จำกัดทรัพยากรซึ่งรวมถึงการสุ่ม (randomness), การโต้ตอบ (interaction) และการพิสูจน์ (proofs) พร้อมกับลำดับชั้นและผลลัพธ์ความยากที่เชื่อมโยงคลาสเหล่านี้

Sub-topics

• NP-Completeness and Reductions
• Randomized and Interactive Computation
• The P versus NP Problem
• Time and Space Complexity Classes

Core questions

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

Key theories

ทฤษฎีลำดับชั้นเวลาและพื้นที่

เมื่อมีเวลาหรือพื้นที่เพิ่มขึ้นอย่างเคร่งครัด เครื่องจักรสามารถแก้ปัญหาได้มากขึ้นอย่างเคร่งครัด ซึ่งพิสูจน์ว่าคลาสความซับซ้อนก่อตัวเป็นลำดับชั้นที่แท้จริง และปัญหาบางอย่างมีความยากโดยธรรมชาติมากกว่าปัญหาอื่น ๆ

ความสมบูรณ์ของ NP

ทฤษฎี Cook–Levin ระบุปัญหาใน NP ที่ปัญหา NP อื่น ๆ ทุกปัญหาลดรูปไปหาได้ ดังนั้นอัลกอริทึมที่มีประสิทธิภาพเพียงหนึ่งเดียวสำหรับปัญหาใดปัญหาหนึ่งในกลุ่มนี้จะสามารถแก้ปัญหาทั้งหมดได้อย่างมีประสิทธิภาพ

แบบจำลองที่จำกัดทรัพยากร

การเพิ่มการสุ่ม การโต้ตอบ หรือการสลับ (alternation) กำหนดคลาสต่างๆ เช่น BPP, IP และลำดับชั้นพหุนาม ซึ่งความสัมพันธ์ของคลาสเหล่านี้ช่วยให้เข้าใจชัดเจนยิ่งขึ้นว่าทรัพยากรเพิ่มเติมสามารถทำอะไรได้บ้างและทำอะไรไม่ได้บ้าง

Clinical relevance

ทฤษฎีความซับซ้อนเป็นแนวทางในการปฏิบัติโดยการรับรองว่าปัญหาใดที่ยอมรับอัลกอริทึมที่มีประสิทธิภาพ และปัญหาใดที่เป็น NP-hard ซึ่งควรแก้ไขด้วยฮิวริสติกส์ (heuristics) หรือการประมาณค่า (approximation) นอกจากนี้ ความยากที่สันนิษฐานของปัญหาบางอย่างยังเป็นพื้นฐานของการเข้ารหัสสมัยใหม่ (modern cryptography) ซึ่งความปลอดภัยขึ้นอยู่กับงานที่เชื่อว่าไม่สามารถคำนวณได้ในทางปฏิบัติ

History

Hartmanis และ Stearns ได้ก่อตั้งสาขานี้ในปี 1965 โดยการกำหนดคลาสความซับซ้อนและพิสูจน์ทฤษฎีลำดับชั้น (hierarchy theorems) Cook และ Levin ได้นำเสนอ NP-completeness ประมาณปี 1971 Karp ได้แสดงให้เห็นว่าปัญหาธรรมชาติหลายอย่างสมบูรณ์ในปี 1972 และทศวรรษต่อมาได้เพิ่มแบบจำลองการพิสูจน์แบบสุ่ม แบบโต้ตอบ และแบบตรวจสอบได้ด้วยความน่าจะเป็น

Key figures

• Stephen Cook
• Richard Karp
• Leonid Levin
• Juris Hartmanis

Seminal works

• cook1971
• hartmanisStearns1965
• aroraBarak2009

Frequently asked questions

ความแตกต่างระหว่างความสามารถในการคำนวณ (computability) และความซับซ้อน (complexity) คืออะไร?

ความสามารถในการคำนวณถามว่าปัญหาหนึ่งสามารถแก้ไขได้ด้วยอัลกอริทึมใด ๆ เลยหรือไม่ โดยไม่คำนึงถึงต้นทุน ความซับซ้อนสมมติว่าปัญหานั้นสามารถแก้ไขได้และถามว่าการแก้ปัญหานั้นต้องใช้เวลาและหน่วยความจำมากน้อยเพียงใด โดยแบ่งแยกอย่างละเอียดระหว่างปัญหาที่สามารถแก้ไขได้ในทางทฤษฎี

เหตุใดความสมบูรณ์ของ NP จึงมีความสำคัญในทางปฏิบัติ?

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