#### 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" - more fondly called computational complexity theory.

#### Course 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 theorems. Update (Nov 20, 2012) : This section was skipped mostly.

#### Intended Audience and Pre-requisites

This course is an ideal starting point (as electives) for students interested in theoretical aspects of computation and algorithms. 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. (Indeed, students without this background are also welcome to attend this course, but they are requested to meet the instructor before registering for the course).
Indeed, one of the aims of the course is to develop a fundamental perspective about the notion of computation - hence the course can also be envisaged as one for a general CS graduate as well.
Note that this course is a strict per-requisite for the Advanced Complexity Theory course that will be offered in the next semester.
To know more about where this fits in the stream of theory courses please see here.