Basic Information

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.

Advice

From our experience with this course here are some useful tips which will help to get the maximum benefit out of the course.

• Keep at it, Don't fall behind ! - In a conceptual and theoretical material in a course (like this), it takes time for ideas to sink in. It is extremely important to put in consistent effort throughout the semester, rather than hoping to learn everything together at the end, right before the deadlines or tests. Even though we divide the course into themes, the ideas are so inexplicably connected across themes. So, even missing a few lectures, can cause difficulty.
• Solve the problems from the problem sets ! - The problems in the problem sets are handpicked in order to ensure that you complete the thought process started in the lectures.
  Here is a useful scheme to work on the problem sets. Start working on the problem sets by yourself as soon as they are available. Think through possible approaches during your spare time, say while you are waiting in line (if you do !) at Tiffanys/mess. The earlier you start the more mature the thoughts will become before the deadline.
  About 3 days before the deadline, collect your thoughts (and mind-blocks) on a sheet of paper (consider this as a read only tape) - and hold a meeting with your partner for a discussion. The tape is read-only - so the conversation and the details of it will not be (and should not be) recorded. Go back on your own, reproduce the ideas which helped you get over your mind-blocks and of course cite the source. This will naturally avoid plagiarism and you definitely will learn the solution and the reason it gets you over the mindblock.
  Make sure you submit before the deadline even if you could not solve all the problems. There will be discussion sessions for problem sets.