204512-53/lecture13

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

นายเสกสิทธิ์ สุวรรณ รหัสนักศึกษา 5214550332

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 ใดๆ
$(x_{1}\lor \lnot x_{2}\lor \lnot x_{3})\land (\lnot x_{1}\lor \lnot x_{3}\lor x_{4})\land (x_{5}\lor x_{6}\lor \lnot x_{4})$ และ 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
2.ถ้า G มี independent Set ขนาด m แล้ว $\varnothing$ Satisfiable