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