204512-53/lecture13

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

นายเสกสิทธิ์ สุวรรณ รหัสนักศึกษา 5214550332
นางสาวสลิตตา นกขุนทอง รหัสนักศึกษา 5214550308

NP Complete

ปัญหา A $\leqslant$ P (Polynomail time to) ปัญหา B ถ้า มี poly-time algo ที่สำหรับทุกๆ instance x ของ A
x' = T(x) , | x' | = poly (| x |)
และถ้า x เป็น yes instance ของ A , x' เป็น yes-instance ของ B
x เป็น no instance ของ A ,$x'$ เป็น no-instance ของ B THM: 3-SAT $\leqslant$ p INDEP-SET Proof: ให้ $\varnothing$ เป็น 3-CNF ใดๆ
และ m clause เรียกเป็น $C_{1},C_{2},C_{2},...,C_{M}$ จะสร้างกราฟได้ดังนี้

• • ในแต่ละ clause $C_{i}$ สร้างสามเหลี่ยมที่ประกอบไปด้วยโหนดตัวแปรที่ปรากฎใน C ได้กราฟที่มี 3 โหนด ตามรูป

สำหรับทุกตัวแปร $X_{i}$ เชื่อมทุกโหนดที่แทนตัวแปร $X_{j}$กับทุกโหนดที่แทน $\lnot X_{j}$ สังเกตุว่าขั้นตอนดังกล่าวสามารถทำให้เป็น polynomial time ได้และกราฟที่ได้มีขนาดเป็น poly ในขนาด $\varnothing$
พิสูจน์ 1. ถ้า $\varnothing$ Satisfiable ,G มี independent set ขนาด m นั้นคือ มี assignment ให้กับตัวแปร $x_{1},x_{2},...,x_{n}$
ที่ทำให้ทุก clause เป็นจริงพร้อมกัน
เนื่องจาก Ci เป็นจริงจะมีตัวแบ่งอย่างน้อย 1 ตัวใน Ci เป็นจริง,เลือกโหนดใน G ที่สอดคล้องกับตัวแปรตัวนั้นใส่ Set I โดยที่ Set I ที่มีสมาชิก M ตัว
จะพิสูจน์ว่า I เป็น Independent set ใน G
assume ว่า I ไม่เป็น independent Set นั้นคือเชื่อมระหว่างบางคู่ของโหนด u,v $\epsilon$ I
เนื่องจากเชต I มีโหนดเพียงโหนดเดียวจากแต่ละสามเหลี่ยมดังนั้นไม่มีทางที่เส้นเชื่อมดังกล่าวจะเป็นเส้นเชื่อมในสามเหลี่ยมได้ ดังนั้น ต้องเป็นเส้นเชื่อมระหว่างตัวแปร Xi บางตัวกับ $\lnot x_{i}\Rightarrow$ เนื่องจากเราเลือกตัวแปรจาก assign ที่เป็นจริง กรณีที่ป็นไปไม่ได้ นั้นคือ I เป็น Independent set ในกราฟมีขนาด m
x1 = T , x2 = T ,x3 = F , x4 = T
Ex สมมุติมี formular
$(\lnot x_{4}\lor x_{1}\lor \lnot x_{3})\land (x_{1}\lor x_{2}\lor x_{3})\land (\lnot x_{3}\lor \lnot x_{1}\lor x_{4})$
วาดกราฟได้ดังรูป

พิสูจน์ x1= T, x2=T , x3 = F ,x4 = T ให้เป็นจริง
สูจน์ให้ได้ว่า clause 1.เป็นจริง
2.เป็นจริง
3.เป็นจริง
2.ถ้า G มี independent Set ขนาด m แล้ว $\varnothing$ Satisfiable

---

SUBSET SUM ในเซต A = {x1,x2,x3,..,xn} จำนวนเต็ม มี subset B \subseteq A ที่ $=\sum _{xe0}x=t$
ต้องการพิสูจน์ว่า
thm: 3-SAT $\leqslant$ subset-sum
Ex. $(\lnot \lor x_{4}\lor x_{2}\lor \lnot x_{3})\land (x_{1}\lor \lnot \ x_{2}\lor x_{3})\land (\lnot \ x_{3}\lor \lnot \ x_{1}\lor x_{4})$
จะได้ว่า

		C
x1	1 0 0 0 0	1
$\lnot$x1	1 0 0 0 0	0
x2	0 1 0 0 0	0
$\lnot$x2	0 1 0 0 0	1
x3	0 0 1 0 0	1
$\lnot$x3	0 0 1 0 0	0
	1 1 1 0 0	4

Ex.
$(x_{1}\lor \lnot x_{2}\lor \ x_{3})\land (\lnot x_{1}\lor \lnot \ x_{3}\lor x_{4})\land (\ x_{3}\lor \ x_{2}\lor \lnot x_{4})$

จะกล่าวว่าปัญหา A สามารถตรวจคำตอบได้อย่างมีประสิทธิภาพ (Efficiently certifiable) ถ้ามี Algorithm V ที่ทำงานใน Polynomial time

• ที่ทุกๆ Yes - instance x ของ A มี Certificate C ที่

 |C| = poly (|X|) และ V (x,c) = 1 

• ที่ทุกๆ No - instance x ของ A สำหรับทุกๆ Certificate C ที่

 V(x,c) = 0 

Decision Problems (ปัญหาที่ตอบ yes/no)

P (Polynomial)

ปัญหา A จะอยู่ในกลุ่ม P

ถ้ามี Algorithm ที่ทำงานใน Polynomial time ที่แก้ ปัญหา A

NP (Nondeterministic Polynomial) ปัญหา A จะอยู่ในกลุ่ม NP

ถ้า A สามารถตรวจคำตอบได้อย่างมีประสิทธิภาพ

ตัวอย่าง SAT อยู่ใน NP Algorithm V ที่รับ CNF $\varnothing$

และ assignment เป็น certificate จะสามารถตรวจคำตอบของปัญหาได้โดย

ถ้า $\varnothing$ ทำให้เป็นจริงได้ จะมี assignment ที่ทำให้ V ตอบ Yes

แต่ ถ้า $\varnothing$ ไม่สามารถทำให้เป็นจริงได้ ไม่ว่าจะใช้ assignment ได้ V จะตอบ No เสมอ

ปัญหา Composite ให้จำนวนเต็ม N , N เป็นจำนวนประกอบหรือไม่

พิสูจน์ว่า Composite เป็น NP

(ต้องมี 2 อย่าง คือ Certificate , Verificate)

• ให้ตัวประกอบ 2 ตัว x,y ของ N เป็น Certificate

• Algorithm V ที่ตรวจคำตอบ คำนวน x,y และ ตรวจว่าเท่ากับ N หรือไม่

นิยาม ปัญหา A เป็น NP - hard ก็ต่อเมื่อ

สำหรับทุกๆ ปัญหา B ที่เป็น NP

B $\leqslant$ P A

นิยาม ปัญหา A เป็น NP - Complete ก็ต่อเมื่อ

1 A ต้องเป็น NP
2 A เป็น NP-hard

Cook - Lavin

 SAT เป็น NP-Complete

• ถ้า A $\leqslant$p B และ B $\leqslant$p C แล้ว A $\leqslant$p C ด้วย

• ถ้า A เป็น NP-Complete และ A $\leqslant$p B ได้ B เป็น NP-Hard

จะพิสูจน์ ปัญหา A เป็น NP-Complete (มี 2 ขั้น)

1 พิสูจน์ว่า A เป็น NP
2 หาปัญหา NP-Complete B , แล้วพิสูจน์ B $\leqslant$p A