Changelog : Title was updated from "Advanced Theory of Computation" to the current one on Jul 2016.
Syllabus :
- Computability: Review of Turing Machines, view of PDAs, 2DFAs, FAs as restricted TMs and related theorems. Tape reduction, and robustness of the model. Encoding and Enumeration of Turing Machines, Undecidability. Rice-Myhill-Shapiro theorem. Relativisation. Arithmetic and Analytic Hierarchy of languages. Proof of Godel's incompleteness theorem based on computability. Kolmogorov Complexity. Resource bounded computation. Notion of a computational resource. Blum's Speedup theorem.
- Time Complexity: Time as a resource, Linear Speedup theorem. Crossing Sequences and their applications. Hierarchy theorems. P vs NP. Time Complexity classes and their relationships. Notion of completeness, reductions. Cook-Levin Theorem. Ladner's theorem. Relativization Barrier : Baker-Gill-Solovoy theorem.
- Space Complexity: Space as a resource. PSPACE, L and NL. Reachability Problem, Completeness results. Savitch's theorem, Inductive Counting to show Immerman-Szelepscenyi theorem. Reachability Problems, Expander Graphs, SL=L
- Complexity of Counting & Randomization : Counting Problems. Theory of #P-completeness. The complexity classes PP, ParityP, BPP, RP, BPP is in P/poly, Toda's theorem.
Text Books:
We will follow material from the following four textbooks.
