204512-53/lecture11

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

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

 นายชัชพล      นุโยค รหัส 5214550049 (Part I)
 นายชัชพล      นุโยค รหัส 5214550049 (Part I)
 นายสุรเดช      วัฒนอุดมโรจน์ รหัส 5214550324 (Part I)
 นายชัยณรงค์   เหมือนรุ่ง รหัส 5214550057 (Part II)
 นายศศิน         เทียนดี รหัส 5214550278 (Part II)
 น.ส.นันทณัฏฐ์ ภูทอง รหัส 5214550171 (Part II)
 น.ส.ชนาพร    คุรุรัตน์พันธ์  รหัส 5214550031 (Part II)

Part I NP Completeness


NP: Non-deterministic Polynomial time คือ เซตของ Algorithm ที่ไม่สามารถแก้ไขปัญหาได้ในเวลาที่เป็น polynomial โดยการนิยามเซตของปัญหาเพื่อประโยชน์ในการเปรียบเทียบระดับความยาก-ง่ายของ Algorithm ซึ่งเซตของปัญหาสามารถแบ่งเป็นเซต P, NP, NP-hard และ NP-complete

ในการเปรียบเทียบ Algorithm ใดๆ เราจะทำการพิจารณา Algorithm ว่าจัดอยู่ในเซตของปัญหาใด โดยใช้เทคนิคการลดรูปของปัญหา (Reduction) ว่าเป็นกลุ่มเดียวกับปัญหาที่อยู่ในเซตหรือไม่ ถ้าอยู่ในกลุ่มเดียวกันจะกล่าวว่า Algorithm มีความยากเท่ากัน ความยาก คือ มี Algorithm ที่มีประสิทธิภาพแก้ไขปัญหาหรือไม่

ปัญหา A สัมพันธ์ ปัญหา B

ปัญหา A ไม่ยากไปกว่า ปัญหา B

ปัญหา A NPComplete7.gif ปัญหา B

โดยมีความหมายว่า ถ้ามี Algorithm ที่สามารถแก้ปัญหา B ได้ ปัญหา A ก็จะสามารถแก้ได้เช่นกัน


ปัญหาที่ 1 : Independent Set เป็นปัญหากลุ่ม Decision Problem

นิยาม : ให้ Undirected graph G = (V, E) จะกล่าวว่า I NPComplete1.gif V เป็น Independent Set ก็ต่อเมื่อ สำหรับทุกๆโหนด U,V NPComplete1.gif I, U NPComplete5.gif V ไม่มีเส้นเชื่อมระหว่าง U และ V

ปัญหา : ให้กราฟ G = (V, E) และ integer k, มี Independent set ขนาด ≥ k หรือไม่

NPComplete8.gif

ในภาพทำการเลือกโหนด (k) เท่ากับ 1 จะกล่าวว่ามี Independent set ขนาด 1

สามารถนำไปใช้แก้ปัญหา หาคนที่ไม่รู้จักกันในห้อง หรือ การเปิด-ปิดไฟแดงที่แยก


ปัญหาที่ 2 : Vertex Cover

นิยาม : C NPComplete1.gif V เป็น Vertex Cover ก็ต่อเมื่อ NPComplete4.gif(U,V)NPComplete6.gif E,U NPComplete6.gif C หรือ V NPComplete6.gif C

ปัญหา : ให้กราฟ G = (V, E) และ จำนวนเต็ม k ถามว่ามี vertex cover ขนาด ≤ k หรือไม่

NPComplete9.gif


ถ้าสมมติให้ Independent Set NPComplete7.gif Vertex Cover

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

Proof : Indenpendent set NPComplete2.gifVertex Cover

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

NPComplete3.gif

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 NPComplete2.gifB และมี Algorithm ที่แก้ปัญหา B ได้ใน Polynomial time จะมี Algorithm ที่แก้ปัญหา A ใน Polynomial time ได้ด้วย

Proof : ให้ M เป็น Polynomial time Algorithm ที่แก้ปัญหา B จะได้ว่า A NPComplete2.gif B นั้นคือ มี Polynomial time Algorithm T ที่ NPComplete4.gifinstance 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|)



Part II

Np1.jpg

พิจารณา กราฟ G = (V,E) , C NPComplete6.gif V เรียกว่า Clique
ก็ต่อเมื่อ NPComplete4.gif u,v NPComplete6.gif C ที่ uNPComplete5.gifs
(u,v)NPComplete6.gif E


CLIQUE

ให้กราฟ G = (V,E) และจำนวนเต็ม K
กราฟ G clique = (V,E') เป็น Complement ของ G
ถ้า
 (u,v)NPComplete6.gif E <--> (u,v)Np-notnot.jpg E'
Lemma  กราฟ G = (V,E) มี Independent Set ขนาด K ใน G clique = (V,E') มี Clique ของ K
Proof (->)
       ให้ I เป็น Independent Set ขนาด K ใน G
       พิจารณาโหนด u,v NPComplete6.gif I ใดๆ ที่ uNPComplete5.gifv เนื่องจาก ณ เป็น Indep ใน G(u,v)Np-notnot.jpg E
       จากนิยามของ G clique , จะได้ว่า (u,v) NPComplete6.gif E clique
       ดังนั้นทุกๆ u,v NPComplete6.gif I ที่ uNPComplete5.gifv ,(u,v)NPComplete6.gif E Clique