ผลต่างระหว่างรุ่นของ "204512/บรรยาย 13"
| แถว 8: | แถว 8: | ||
'''NP : Non-deterministic Polynomial time''' | '''NP : Non-deterministic Polynomial time''' | ||
| − | === | + | === <u>ปัญหา Halting Problem<u> === |
'''Description :''' ให้โปรแกรม P และ input X ถามว่า P(x) ทำงานจบหรือไม่ | '''Description :''' ให้โปรแกรม P และ input X ถามว่า P(x) ทำงานจบหรือไม่ | ||
จะพบว่าเราไม่สามารถออกแบบอัลกอริทึมที่แก้ปัญหานี้ได้ ซึ่งสามารถพิสูจน์โดย contradiction ได้ดังนี้ | จะพบว่าเราไม่สามารถออกแบบอัลกอริทึมที่แก้ปัญหานี้ได้ ซึ่งสามารถพิสูจน์โดย contradiction ได้ดังนี้ | ||
รุ่นแก้ไขเมื่อ 16:00, 22 กันยายน 2550
จดบันทึกคำบรรยายโดย:
- นายเกรียงไกร ลิ่มทอง รหัส : 50653732
- นายธีรวัฒน์ ตออำนวย รหัส : 50653815
เนื้อหา
NP Completeness
NP : Non-deterministic Polynomial time
ปัญหา 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
ปัญหา Program Equivalence
Description : ให้โปรแกรม P1 และ P2 ถามว่า P1 และ P2 ให้ผลลัพธ์เหมือนกันในทุกๆ input หรือไม่ ในที่นี้เราจะพิสูจน์โดยวิธี Reduction จากปัญหา Halting Problem ไปสู่ปัญหา Program Equivalence
Proof : สมมติว่ามีอัลกอริทึม Q ที่แก้ปัญหา Program Equivalence ได้
ให้มี procedure HP(P,X) สำหรับแก้ปัญหา Halting Problem
