204512/บรรยาย 13

---

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

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

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

---

NP Completeness

NP : Non-deterministic Polynomial time ปัญหาที่เป็น NP เป็นปัญหาที่ไม่สามารถแก้ได้ภายใน polynomial time เป็นวิธีหนึ่งที่จะแสดงว่าปัญหาที่กล่าวถึงนั้นยาก แต่ก่อนที่จะกล่าวถึงปัญหาที่อยู่ใน NP Class จะกล่าวถึงปัญหาที่ไม่มีอัลกอริทึมใดแก้ได้ก่อนนั่นคือ ปัญหา Halting problem

  Note : ปัญหา Halting problem ไม่ใช่ปัญหาใน NP Class เพราะไม่สามารถแก้ได้

ปัญหา 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 (HP) ไปสู่ปัญหา Program Equivalence (PE)

Proof : สมมติว่ามีอัลกอริทึม Q ที่แก้ปัญหา Program Equivalence ได้
ให้มี procedure HP(P,x) สำหรับแก้ปัญหา Halting Problem
- สร้าง program P' ที่ทำงานเหมือน P(x) แต่ไม่รับ input และไม่มี output แต่ก่อนจบพิมพ์ "done"
- สร้าง program P" ที่ไม่ทำอะไรพิมพ์ "done" อย่างเดียว
- ให้ procedure นี้ return Q(P',P")
เพราะเราสามารถบอกได้ว่า HP(P,x) ไม่สามารถแก้ได้ดังนั้น Q(P',P") ไม่สามารถแก้ได้ด้วยคือ reduction จาก HP ไป PE

Decision Problem

Description : คือปัญหาที่ต้องการคำตอบเป็น Yes หรือ No

ปัญหา Decision Problem P สามารถนิยามใหม่ ด้วย Language P ซึ่งเป็นเซ็ตของ instance ที่ตอบ yes เช่น

Decision Problem

Prime : ให้จำนวนจริง X ถามว่า X เป็น prime หรือไม่
Shortest path : ให้หาว่ามี Shortest path จาก s ไป t ที่ยาวไม่เกิน p หรือไม่

Language

Prime : {3, 5, 7, 11, ...}
Shortest path : {...} (set ของ Shortest path จาก s ไป t ที่ยาวไม่เกิน p)

นิยาม : Problem คือกลุ่มของปัญหา Instance คือตัวปัญหาแต่ละตัว

มีปัญหา A กับ B จะกล่าวว่า A สามารถลดรูป (reducible) ไปยัง B ได้แบบ polynomial time
ถ้ามี function T  ที่ $\forall instance\ x\in A\ ,\ T(x)\in B$

และ $\forall instance\ x\notin A\ ,\ T(x)\notin B$

เขียนแทนด้วย

ถ้าต้องการวัดประสิทธิภาพของ $A$ ว่าทำงานเป็น polynomail time ไหม และทราบว่า B ทำงานใน polynomail time ให้หาว่ามี T ที่ทำงานใน polynomail time และเป็นไปตามข้อกำหนดด้านบนไหม ถ้ามีคือ ... แสดงว่า A ทำงานได้ใน polynomail time

ปัญหา Satisfiability (SAT)

นิยาม : CNF formula คือนิพจน์ทางตรรกศาสตร์ที่เขียนให้อยู่ในรูปของการ AND กันของ Clause ที่เป็นการ OR กับของตัวแปรหรือนิเสธของตัวแปร
ตัวอย่างเช่น

$(X_{1}\lor X_{2})\land (X_{3}\lor X_{2}\lor \neg X_{1})\land (\neg X_{3}\lor \neg X_{2}\lor X_{1}\lor X_{4})$

ปัญหา SAT คือ กำหนด CNF formula ${\boldsymbol {\phi }}$ ให้ถามว่า มีวิธีกำหนดค่าให้กับตัวแปรต่างๆ ใน ${\boldsymbol {\phi }}$ ที่ทำให้ ${\boldsymbol {\phi }}$ เป็นจริงหรือไม่

  Note : Clause ที่เป็นการ OR กับของตัวแปรหรือนิเสธของตัวแปร เรียกว่า Disjunction ตัวอย่างเช่น $(X_{1}\lor X_{2})$