Course Objectives:The course is to expose the attendee to the importance, history and progress of the study the limits of computation, its connection to various concepts that they have already seen in a basic "theory of computation" course. Then the course aims to motivate and expose to the fundamental understanding of "computation under resource constraints" - most often called computational complexity theory.
Intended Audience, Pre-requisites and Sequel CoursesBy design, the course is meant for 3rd year UG who have just finished their courses on Automata theory (CS2200) and Algorithm Design (CS2800), and incoming 1st year M.Tech/MS/PhD students (who would have had equivalent UG courses in their B.Tech courses).
The course provides a formal, unifying theoretical theme between these two subjects. This course is an ideal starting point (as electives) for students interested in theoretical aspects of computation and algorithms. If you wish to know more about the area this course start you on - here is a latest/recent article that is precise as well as accessible about the theory of computation as a fundamental area of study. The pre-requisites include the basic discrete mathematics and basic theory of computation (about regular languages, CFLs etc) courses in a typical BTech CS course.
Sequel Courses: There is also a sequel to this course that will be offered in the next semester (Jan-May 2019) titled Modern Complexity Theory. Note that this course is a strict pre-requisite for the Modern Complexity Theory course.. To know more about where this fits in the stream of theory courses please see here.
- Review: Turing Machines, view of PDAs, 2DFAs, FAs as restricted TMs, Tape reduction, Universal TMs, Undecidability.
- Computability: 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.