Syllabus
-
1. Turing machines and their variants, Church-Turing thesis -
2. Halting problem and other undecidable problems -
3. RAM and their equivalence with Turing machines. Algorithmically computable functions -
4. Decidable and partially decidable enumerable languages and their properties -
5. m-reducibility and m-complete languages -
6. Rice's theorem -
7. Nondeterministic Turing machines, basic complexity classes, classes P, NP, PSPACE, EXP. -
8. Savitch's theorem -
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. Classes co-NP and #P -
13. Paremeterized algorithms, class FPT -
14. Exponential time hypothesis (ETH, SETH) and conditional lower bounds -
15. Complexity and cryptography
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.