Concept ก่อนเข้าใจ
**Deterministic Turing machine
** คอมพิวเตอร์ที่รันคำสั่งเหมือนเดิมทุกครั้ง ถ้าหาก Input และ State เหมือนเดิม (คอมพิวเตอร์ในปัจจุบัน)
**
Non-deterministic Turing machine
** คอมพิวเตอร์ที่รันคำสั่งอาจะไม่เหมือนเดิมทุกครั้ง ถ้าหาก Input และ State เหมือนเดิม (แยก Process ได้) มันสามารถแตกการกระทำได้มากกว่า 1 พร้อมๆกัน
ตัวอย่างปัญหา
อาทิเช่น Zero sum subset problem สมมุติว่ามี Set อยู่ {5,-2,-3, 7, 8} ต้องหา Subset ที่รวมกันได้ 0 (คำตอบก็คือ {5, -2, -3}) เป็นต้น
Deterministic Turing machine
DTM ไล่รวมไปเรื่อยๆ จนกว่าจะเจอ O(N+(N-1)+(N-2)+… 1) = O(N(N+1)/2) = O(N²)
Non-deterministic Turing machine
NDTM แตก Process เป็น Tree ได้เลย อาทิเช่น
Steps Solutions
1 {}
2 {5} {-2} {-3} {7} {8}
3 {5,-2} {5,-3} {-2, 5} {-2, 3}
NDTM ถ้าซักสายใดสายหนึ่งเจอ มันจะเอาสายที่เจอมาเป็นคำตอบและหยุดการทำงาน สมมุติว่าถ้าเรารู้ว่าคำตอบมันต้องใช้ 3 ตัว มันจะเจอใน Step ที่ 3 แน่นอน ยังไงก็ไม่มากกว่า N เพราะฉะนั้นมันคือ O(N)
ขี้โกงจริงๆ
คราวนี้มาเข้าเรื่อง P, NP, NP-Complete และ NP-Hard
P คือเซ็ตของโจทย์ที่สามารถแก้ได้โดย Deterministic Turing machine ด้วยเวลา Polynomial
NP คือเซ็ตของโจทย์ที่สามารถแก้ได้โดย Non-Deterministic Turing machine ด้วยเวลา Polynomial หรือ โจทย์ที่สามารถตรวจว่าคำตอบนี้ถูกหรือผิดได้บน Deterministic Turing machine ด้วยเวลา Polynomial เมื่อให้คำตอบมาให้
จริงๆแล้ว P ก็เป็น Subset ของ NP เนื่องจากว่าทุกโจทย์ของ P สามารถแก้ได้ด้วย Non-Deterministic Turing machine ด้วยเวลา Polynomial แน่นอน (เพราะง่ายกว่า) เพราะฉะนั้น NP จึงมี P เป็น Subset ด้วย
ในทางกลับกัน เค้าว่ากันว่า จริงๆแล้ว P=NP ก็ได้ ว่าทุกปัญหาใน NP สามารถแก้ได้ด้วย Deterministic Turing machine ด้วยเวลา Polynomial (อันนี้บางคนเชื่อ บางคนไม่เชื่อนะครับ เพราะยัง Proof ไม่ได้ เลยเป็นปัญหาระดับโลกที่รอคนคอยพิสูจน์อยู่ว่า P=NP? หรือไม่ ใคร Proof ได้ ได้ล้านเหรียญนะครับ)
NP-Complete คือเซ็ต NP-P (NP ลบ P) คือเซ็ตที่เป็น NP เพียวๆจริงๆไม่มี P เข้ามาแทรก หรือโดยนิยามคือหมายความว่าเป็น เซ็ตของโจทย์ที่สามารถแก้ได้โดย Non-Deterministic Turing machine ด้วยเวลา Polynomial แต่ไม่สามารถแก้ได้โดย Deterministic Turing machine ด้วยเวลา Polynomial
NP-Hard คือเซ็ตของปัญหาขนาดใหญ่ที่มีส่วนนึงของการแก้ปัญหาเป็นปัญหาแบบ NP-Complete ส่วนที่ยากของ NP-Hard ก็คือส่วนของ NP-Complete นี่แหละ ถ้าแก้ส่วนย่อยของปัญหาที่เป็น NP-Complete ได้แล้ว (หรือว่าได้คำตอบของส่วนย่อยปัญหาที่เป็น NP-Complete นี้ได้หมดแล้ว) ปัญหา NP-Hard นี้ก็จะไม่ยากอีกต่อไป แก้ได้ง่ายๆ แต่มันก็ยากกว่า NP-Complete เพราะขั้นตอนในการแก้มันเยอะกว่า
ถ้าเรียงตามความยากจริงๆก็คือ จากง่ายสุดไปยากสุด
- P
- NP
- NP-Complete
- NP-Hard (ขั้นตอนในการแก้เยอะกว่า NP-Complete)
เพื่อความเข้าใจ ก็เลยมีคนวาดให้เข้าใจง่าย ดังแผนภูมิภาพนี้นะครับบบบ
กลุ่มซ้ายคือสำหรับคนที่เชื่อว่า P != NP
กลุ่มขวาคือสำหรับคนที่เชื่อว่า P = NP