ผู้ใช้:Chatchapol

204512-53/lecture13

จดบันทึกคำบรรยายโดย:

 นายชัชพล  นุโยค        รหัส 5214550049
 นายสุรเดช  วัฒนอุดมโรจน์  รหัส 5214550320

---

== NP Completeness ==

---

<<

<<

Lemma : พิจารณาเซต ใดๆ ให้ A เป็น imdenpendent set โดย V-A เป็น Vertec Cover

Proof : Indenpendent set Vertex Cover

นิยาม : ปัญหา A เป็น Polynomial time เพื่อลดปัญหา B ถ้ามี Algorithm T ที่ทำงานใน Polynomial time สำหรับทุกๆ instance X ของ A จะได้ T(x) เป็น instance ของ B

X' = T(x) เป็น instance ของ B และ |X'| = Poly (|X|)

   ถ้า x เป็น instance ตอบ "Yes" ใน A
   => x' เป็น instance ตอบ "Yes" ใน B

   ถ้า x เป็น instance ตอบ "No" ใน A
   => x' เป็น instance ตอบ "No" ใน B

Lemma : ถ้า A B และมี Algorithm ที่แก้ปัญหา B ได้ใน Polynomial time จะมี Algorithm ที่แก้ปัญหา A ใน Polynomial time ได้ด้วย

Proof : ให้ M เป็น Polynomial time Algorithm ที่แก้ปัญหา B จะได้ว่า A B นั้นคือ มี Polynomial time Algorithm T ที่ instance x ของ A x' = T(x) มีขนาด poly(|x|) และคำตอบของ x ในปัญหา A ตรงกับของ x' ในปัญหา B

สำหรับ Algorithm M' ดังนี้

  M'(x) :
  x' = T(x)
  return M(x')

แต่เนื่องจาก |x'| = poly(|x|) ดังนั้น เวลาในการคำนวณ M(x')คือ poly(|x'|) = poly(poly(|x|)) = poly(|x|)

จากนิยาม M'(x) เป็นคำตอบของ x ใน A เหลือแต่ต้องตรวจสอบว่า M' ทำงานใน Polynomial time หรือ poly(|x|)

---