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 |)