ผลต่างระหว่างรุ่นของ "204512-53/lecture13"
ไปยังการนำทาง
ไปยังการค้นหา
G521455033 (คุย | มีส่วนร่วม) |
G521455033 (คุย | มีส่วนร่วม) |
||
| แถว 10: | แถว 10: | ||
THM: 3-SAT <math>\leqslant</math> p INDEP-SET | THM: 3-SAT <math>\leqslant</math> p INDEP-SET | ||
Proof: ให้ <math>\varnothing</math> เป็น 3-CNF ใดๆ <br> | Proof: ให้ <math>\varnothing</math> เป็น 3-CNF ใดๆ <br> | ||
| − | + | <math>(x_1\or\lnot x_2\or \lnot x_3 ) \and (\lnot x_1 \or \lnot x_3 \or x_4 ) \and (x_5 \or x_6 \or \lnot x_4)</math> | |
| + | และ m clause เรียกเป็น <math>C_1,C_2,C_2,...,C_M</math> | ||
รุ่นแก้ไขเมื่อ 05:33, 7 ตุลาคม 2553
จดบันทึกคำบรรยายโดย:
นายเสกสิทธิ์ สุวรรณ รหัสนักศึกษา 5214550332
NP Complete
ปัญหา A 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 , เป็น no-instance ของ B
THM: 3-SAT p INDEP-SET
Proof: ให้ เป็น 3-CNF ใดๆ
และ m clause เรียกเป็น
