ผลต่างระหว่างรุ่นของ "204512/บรรยาย 13"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 15: แถว 15:
 
เพราะฉะนั้นเราจะสามารถสร้าง procedure Q' ที่มีอัลกอริทึมดังนี้ได้
 
เพราะฉะนั้นเราจะสามารถสร้าง procedure Q' ที่มีอัลกอริทึมดังนี้ได้
  
   '''Procedure Q'(program P)'''
+
   '''Procedure''' Q'(program P)
 
       If Q(P, P) then
 
       If Q(P, P) then
 
         loop forever
 
         loop forever
แถว 21: แถว 21:
 
         halt
 
         halt
  
จาก procedure Q' พิจารณา Q'(Q') ว่า halt หรือไม่
+
จาก procedure Q' พิจารณา Q'(Q') ว่า halt หรือไม่<br/>
 
<br/>'''Case1 : Q'(Q') halt'''  
 
<br/>'''Case1 : Q'(Q') halt'''  
 
<br/>นั่นคือ Q(Q',Q') = False  -->  Q'(Q') = False คือ Q'(Q') ติด loop *Contradict*
 
<br/>นั่นคือ Q(Q',Q') = False  -->  Q'(Q') = False คือ Q'(Q') ติด loop *Contradict*
 
<br/>'''Case2 : Q'(Q') loop'''
 
<br/>'''Case2 : Q'(Q') loop'''
 
<br/>นั่นคือ Q(Q',Q') = Ture  -->  Q'(Q') = True คือ Q'(Q') halt *Contradict*
 
<br/>นั่นคือ Q(Q',Q') = Ture  -->  Q'(Q') = True คือ Q'(Q') halt *Contradict*
 
+
<br/><br/>
 
เกิด Contradiction จึงสรุปได้ว่าไม่สามารถสร้าง procedure Q' ได้
 
เกิด Contradiction จึงสรุปได้ว่าไม่สามารถสร้าง procedure Q' ได้
 
เพราะฉะนั้น สมมติฐานที่มีอัลกอริทึม Q ที่แก้ปัญหา Halting Problem ได้ ไม่เป็นเป็นจริง
 
เพราะฉะนั้น สมมติฐานที่มีอัลกอริทึม Q ที่แก้ปัญหา Halting Problem ได้ ไม่เป็นเป็นจริง

รุ่นแก้ไขเมื่อ 14:52, 22 กันยายน 2550


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

นายเกรียงไกร ลิ่มทอง   รหัส : 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

ปัญหา Program Equivalence

Decision Problem

ปัญหา Satisfiability (SAT)

ปัญหา 3-Satisfiability (3-SAT)

ปัญหา Independent Set

Class NP

ปัญหา Vertex Cover

ปัญหา 3-Color