Complexity Theory (สรุปด่วน)

เมื่อเรารู้แล้วว่าปัญหานั้น "แก้ได้" (Computable) ทฤษฎีนี้จะศึกษาต่อว่า ต้องใช้ Resource (Time และ Space) มากแค่ไหนในการแก้ปัญหา เมื่อ Input มีขนาดใหญ่มากๆ

1. Complexity Classes

ปัญหาที่แก้ได้ถูกจัดกลุ่มตามความยาก (ความสัมพันธ์กับการใช้เวลา / Time Complexity):

• P (Polynomial Time): ปัญหาที่ Computer สามารถหาคำตอบ (Solve) ได้อย่างรวดเร็ว (เช่น Sorting, Searching, Shortest Path) O(n^k)
• NP (Nondeterministic Polynomial Time): ปัญหาที่ยังไม่มีใครรู้ว่าหาคำตอบได้เร็วไหม แต่ถ้า "มีคนบอกคำตอบมา" Computer สามารถ ตรวจสอบ (Verify) ความถูกต้องได้อย่างรวดเร็ว

2. P vs NP Problem

นี่คือหนึ่งในปริศนาคณิตศาสตร์ที่ยิ่งใหญ่ที่สุดของสหัสวรรษ (Millennium Prize Problems)

• คำถาม: "ปัญหาทุกปัญหาที่ตรวจสอบคำตอบได้เร็ว (NP) จะสามารถหาคำตอบได้เร็ว (P) ด้วยหรือไม่?" (P = NP หรือไม่?)
• ปัจจุบันคนส่วนใหญ่เชื่อว่า P ≠ NP (การแก้ปัญหาจริงๆ ยากกว่าการตรวจคำตอบเสมอ)

3. NP-Completeness

กลุ่มปัญหาที่ "ยากที่สุด" ใน NP Class

• คุณสมบัติ: ถ้ามีคนพบวิธีแก้ปัญหา NP-Complete ตัวใดตัวหนึ่งได้แบบ Polynomial Time (P) ปัญหาที่เหลือในกลุ่ม NP ทั้งหมดจะสามารถถูกแก้ได้ด้วยความเร็วระดับ P ทันที! (ส่งผลให้ P = NP)
• ตัวอย่างปัญหา: Traveling Salesman Problem (TSP), Boolean Satisfiability (SAT), Knapsack Problem
• Applications: ปัญหาเหล่านี้ถูกนำมาใช้ประยุกต์เป็น Cryptography (เช่น RSA) เพราะมันเป็นเรื่องที่ "หาคำตอบยากมาก แต่ตรวจคำตอบได้ง่ายมาก" ถ้าระบบสามารถแก้ปัญหาเหล่านี้ได้แบบ P การเข้ารหัสบนโลกปัจจุบันจะพังทลายทั้งหมด