Basic Information
Objectives
This course is an introduction to the study of limits of computation. Continuing from the concepts introduced in the 'Theory of Computation Course', the notion of Turing Computability will be introduced and discussed in detail. The second half of the course is aimed at motivating the study of 'resource restricted computability' (aka Çomputational Complexity Theory).
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. Resource bounded computation. Notion of a computational resource. Blum's Speedup theorem.
Time Complexity: Time as a resource, Linear Speedup theorem. 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.
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, Counting Hierarchy, Complete Problems for Counting Hierarchy.
Pre-requisites CS2200 (Languages, Machine and Computation) or a course with similar course content, and a basic course on Discrete Mathematics are necessary pre-requisites for the course. People without the abovesaid background are also welcome to attend the course, though you are advised to meet the instructor in person before the commencement of classes. Note that this course is a compulsory pre-requisite for the follow up course Advanced Complexity Theory which will be offered in the even semesters.
Intended Audience
Who?
- If you have developed some kind of appreciation and liking for the contents of a basic course in Theory of Computation, and are curious to further your knowledge topics therein, then this course is highly recommended for you.
- If you like algorithms, and feel the necessity of formalisms that explain the limit of algorithmic computation, this course is recommended for you.
Evaluation Scheme
- Problem Sets (40%): We plan to have 5-6 problem sets with equal weightage. They will be posted (at the course emailing list) with the following timeline.
- Exams (60%):
- Quiz 1 (15%):
- Quiz 2 (15%):
- End-sem Exam (30%):