Syllabus
1) Turing machines and their variants, Church-Turing thesis.
2) Halting problem
3) RAM and their equivalence with Turing machines. Algorithmically computable functions.
4) Recursive and recursively enumerable languages and sets and their properties.
5) 1-reducibility and m-reducibility, 1-complete and m-complete sets.
6) Rice's theorem.
7) Nondeterministic Turing machines, basic complexity classes, classes P, NP, PSPACE, EXP.
8) Savitch's theorem - equivalence of PSPACE and NPSPACE.
9) Deterministic space and time hierarchy theorems.
10) Polynomial reducibility among problems. NP-hardness and NP-completeness.
11) Cook-Levin theorem, examples of NP-complete problems, proofs of NP-completeness.
12) Pseudopolynomial algorithms and strong NP-completeness.
13) Approximations of NP-hard optimization problems. Approximation algorithms and schemes.
14) Classes co-NP and #P.
Annotation
This is a basic course on the theory of algorithms, computability and computational complexity. Roughly the first half of the course is devoted to the introduction to computability theory: Turing machines. Computable functions.
Recursive and recursively enumerable languages and sets. Undecidable problems. The second half of the course is devoted to the study of space and time complexity classes: Equivalence of PSPACE and NPSPACE.
Deterministic hierarchy theorems. Class NP. Polynomial reducibility among problems. Proofs of NP- completeness. Approximation algorithms and approximation schemes.