ผลต่างระหว่างรุ่นของ "204512-53/lecture13"
ไปยังการนำทาง
ไปยังการค้นหา
G521455033 (คุย | มีส่วนร่วม) |
G521455033 (คุย | มีส่วนร่วม) |
||
| แถว 7: | แถว 7: | ||
x' = T(x) , | x' | = poly (| x |) <br> | x' = T(x) , | x' | = poly (| x |) <br> | ||
และถ้า x เป็น yes instance ของ A , x' เป็น yes-instance ของ B <br> | และถ้า x เป็น yes instance ของ A , x' เป็น yes-instance ของ B <br> | ||
| − | x เป็น no instance ของ A , x' เป็น no-instance ของ B | + | x เป็น no instance ของ A ,<math>x'</math> เป็น no-instance ของ B |
| + | THM: 3-SAT <math>\leqslant</math> p INDEP-SET | ||
| + | Proof: ให้ <math>\varnothing</math> เป็น 3-CNF ใดๆ <br> | ||
| + | 3-SAT <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> | ||
รุ่นแก้ไขเมื่อ 05:26, 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 ใดๆ
3-SAT
