204512/บรรยาย 13

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

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

นายเกรียงไกร ลิ่มทอง   รหัส : 50653732
นายธีรวัฒน์ ตออำนวย   รหัส : 50653815



NP Completeness

ปัญหา Halting Problem

ปัญหา Program Equivalence

Decision Problem

ปัญหา Satisfiability (SAT)

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

ปัญหา Independent Set

Class NP

ปัญหา Vertex Cover

ปัญหา 3-Color