ผลต่างระหว่างรุ่นของ "204512-53/lecture13"
ไปยังการนำทาง
ไปยังการค้นหา
G521455033 (คุย | มีส่วนร่วม) |
G521455033 (คุย | มีส่วนร่วม) |
||
| แถว 5: | แถว 5: | ||
== '''NP Complete''' == | == '''NP Complete''' == | ||
ปัญหา A <math>\leqslant</math> P (Polynomail time to) ปัญหา B ถ้า มี poly-time algo ที่สำหรับทุกๆ instance x ของ A <br> | ปัญหา A <math>\leqslant</math> P (Polynomail time to) ปัญหา B ถ้า มี poly-time algo ที่สำหรับทุกๆ instance x ของ A <br> | ||
| − | x' = T(x) , | x' | = poly (| x |) | + | x' = T(x) , | x' | = poly (| x |) <br> |
| + | และถ้า x เป็น yes instance ของ A , x' เป็น yes-instance ของ B <br> | ||
| + | x เป็น no instance ของ A , x' เป็น no-instance ของ B | ||
รุ่นแก้ไขเมื่อ 05:09, 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 , x' เป็น no-instance ของ B
