Formal Languages and Computability (INF3, Autumn'05)
Lecture 15
Main topic:
NP-completeness
Lecture Plan
polynomial time reduction and its properties
NP-completeness
SAT and Cook-Levin Theorem
Reading
Section 7.4 (275-280)