Manideep Burada, Siddharth Singh, Prajwal Singhania, Arkajyoti Pal
Syllabus
Theory of Computability
Notion of computation, models of computation, Turing machines and their variants, equivalence, universal Turing machines and diagonalisation
Decidable and undecidable languages, examples
Reduction, Rice's theorem
Undecidable problems about CFL's, Griebach's theorem, Post's correspondence problem (ref: 1,3,5)
Recursive function theory: Turing computable functions, $S_{mn}$-theorem, recursion theorem and applications (ref: 3,5 and miscellaneous exercises 129-132 in 1), quines
Gödel's Imcompleteness Theorem (ref: 1)
Other formalisms: Type-0 Grammars, Equivalence to Turing Machines, Chomsky Hierarchy (ref: 3)
Complexity Theory
Modelling efficient computation
Complexity classes: P, NP, EXP, R
NP-hardness, NP-completeness, Cook-Levin Theorem, review of some NP-complete problems (ref: 2,8)
Space complexity: PSPACE, NPSPACE, PSPACE-completeness, L, NL, NL-Completeness
Hierarchy Theorems, Ladner's Theorem (note), Relativisation and limits of diagonalisation
Polynomial hierarchy: classes $\Sigma_i^p$, $\Pi_i^p$, PH, alternating Turing machines, defining PH via oracle machines, time space trade-offs for SAT (ref: 2)
References
1. Automata and Computability by Dexter Kozen. (main text)
2. Computational Complexity by S. Arora and B. Barak. (main text)
3. Introduction to Automata Theory, Languages and Computation by John E. Hopcroft and Jeffrey D. Ullman. (reference for some topics covered in class)
4. Introduction to Computability by Fred C. Hennie. (recursive function theory)
5. Introduction to the Theory of Computation by Michael Sipser.
6. Elements of the Theory of Computation by H. Lewis and C. Papadimitriou.
7. Computational Complexity by C. H. Papadimitriou.
8. Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael Garey and David S. Johnson.
Evaluation
The evaluation for this course will be based on a class test mid-sem and end-sem examinations. Details are below.
50%: end-sem exam
30%: mid-sem exam
20%: class test(s)
Note: There will be no evaluation for the tutorials. The purpose is for you to get more exposure and be able to solve problems independently. DO NOT search for solutions online during these sessions. -->