204512/บรรยาย 13

---

จดบันทึกคำบรรยายโดย:

นายเกรียงไกร ลิ่มทอง   รหัส : 50653732

นายธีรวัฒน์ ตออำนวย   รหัส : 50653815

---

NP Completeness

ปัญหา Halting Problem

Description : ให้โปรแกรม P และ input X ถามว่า P(x) ทำงานจบหรือไม่ จะพบว่าเราไม่สามารถออกแบบอัลกอริทึมที่แก้ปัญหานี้ได้ ซึ่งสามารถพิสูจน์โดย contradiction ได้ดังนี้

Proof : สมมติให้มีอัลกอริทึม Q ที่แก้ปัญหา Halting Problem ได้ โดยมี Q(program P, input X) จะ return True ถ้า P(x) halt และ return False เมื่อ P(x) ติด loop เพราะฉะนั้นเราจะสามารถสร้าง procedure Q' ที่มีอัลกอริทึมดังนี้ได้

  Procedure Q'(program P)
     If Q(P, P) then
        loop forever
     Else
        halt

จาก procedure Q' พิจารณา Q'(Q') ว่า halt หรือไม่

Case1 : Q'(Q') halt นั่นคือ Q(Q',Q') = False --> Q'(Q') = False คือ Q'(Q') ติด loop *Contradict*

Case2 : Q'(Q') loop นั่นคือ Q(Q',Q') = Ture --> Q'(Q') = True คือ Q'(Q') halt *Contradict*

พบว่าเกิด Contradiction จึงสรุปได้ว่าไม่สามารถสร้าง procedure Q' ได้ เพราะฉะนั้น สมมติฐานที่มีอัลกอริทึม Q ที่แก้ปัญหา Halting Problem ได้ ไม่เป็นเป็นจริง

Note: ปัญหา Halting Problem ถูกพิสูจน์โดย Alan Turing