Theory of Computation

CS41001, Autumn 2020-21, LTP: 3-1-0

Syllabus

Theory of Computability

• Notion of computation, models of computation, revision of Turing machines
• Recursive function theory: Turing computable functions, $S_{mn}$-theorem, recursion theorem and applications (ref: 3,5 and miscellaneous exercises 129-132 in 1)
• Other formalisms: Type-0 Grammars, Equivalence to Turing Machines, Lambda Calculus (ref: 1,3)
• Decidable and undecidable languages, examples
• Reduction, Rice's theorem
• Undecidable problems about CFL's, Post's correspondence problem (ref: 1,3,5)
• Gödel's Imcompleteness Theorem (ref: 1)

Complexity Theory

• Modelling efficient computation
• Complexity classes: P, NP, EXP
• NP-hardness, NP-completeness, Cook-Levin Theorem, review of some NP-complete problems (ref: 2,8,9)
• Space complexity: PSPACE, NPSPACE, PSPACE-completeness, L, NL, NL-Completeness
• Hierarchy Theorems
• Polynomial hierarchy: classes $\Sigma_i^p$, $\Pi_i^p$, PH, alternating Turing machines, time space trade-offs for SAT (ref: 2)

References

Evaluation

Lectures