204512/บรรยาย 13

จาก Theory Wiki

รุ่นแก้ไขเมื่อ 14:01, 22 กันยายน 2550 โดย 58.64.70.40 (คุย) (→‎ปัญหา Halting Problem)

(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)

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

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

นายเกรียงไกร ลิ่มทอง รหัส : 50653732

นายธีรวัฒน์ ตออำนวย รหัส : 50653815

เนื้อหา

1 NP Completeness
- 1.1 ปัญหา Halting Problem
- 1.2 ปัญหา Program Equivalence
2 Decision Problem
3 Class NP
- 3.1 ปัญหา Vertex Cover
- 3.2 ปัญหา 3-Color

NP Completeness

ปัญหา Halting Problem

ให้โปรแกรม P และ input X ถามว่า P(x)

ปัญหา Program Equivalence

Decision Problem

ปัญหา Satisfiability (SAT)

ปัญหา 3-Satisfiability (3-SAT)

ปัญหา Independent Set

Class NP

ปัญหา Vertex Cover

ปัญหา 3-Color

ดึงข้อมูลจาก "http://158.108.32.49/wiki/index.php?title=204512/บรรยาย_13&oldid=2987"