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}$