Formal Languages and Computability (INF3, Autumn'05)
Lecture 14
Main topic:
The class NP
Lecture Plan
- nondeterministic time complexity
- examples of problems in NP (HAMPATH, CLIQUE, SUBSET-SUM)
- the problem P=NP?
- closure properties
- polynomial time verifiers
Reading