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 ใดๆ
และ 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 บางตัวกับ $\varnothing _{i}\Rightarrow$ เนื่องจากเราเลือกตัวแปรจาก assign ที่เป็นจริง กรณีที่ป็นไปไม่ได้ นั้นคือ I เป็น Independent set ในกราฟมีขนาด m
x1 = T , x2 = T ,x3 = F , x4 = T
Ex สมมุติมี formular
$(\varnothing x_{4}\lor x_{1}\lor \varnothing x_{3})\land (x_{1}\lor x_{2}\lor x_{3})\land (\varnothing x_{3}\lor \varnothing x_{1}\lor x_{4})$ 2.ถ้า G มี independent Set ขนาด m แล้ว $\varnothing$ Satisfiable