Computational Complexity Theory
Prerequisites include basic courses on algorithms, discrete maths, and theory
of computing. In particular, please brush up a few topics like asymptotic notation,
Turing machines, NP-completeness, and basic probability theory.
We will follow the book by Sanjeev Arora and Boaz Barak, and will try to
cover part 1 of it. I may add/delete some topics as we go on.
There are several online lecture notes. I will mention appropriate references
from time to time.
- Computational Complexity: A Modern Approach by Sanjeev Arora, and Boaz Barak
- Computational Complexity by Christos Papadimitriou[CP]
- Introduction to the Theory of Computation by Michael Sipser[MS]
There will be two quizzes, midsem, and endsem.
While solving the assignments (and exams too!), you are not
supposed to discuss with anyone (neither in your class nor anyone else).
If at all you discuss an assignment problem
with someone, name of that person should be mentioned while writing the
solution of that particular problem. If you look up the solution on the
Internet, the link to the solution should also be mentioned while writing it.
Any other form of copying implies a fail grade in the course.
If you get stuck while solving
the assignment, you are welcome to discuss with me.
Topics covered so far (refer to [AB] unless otherwise mentioned):
- Jan 28: Introduction: Computation, Universal Turing Machines, complexity classes (Parts of Chapters 0 and 1 of [AB])
- Feb 02: Equivalence of Turing machines, universal Turing machine, deterministic time hierarchy theorem (Chapter 1 and Section 3.1 of [AB], also see these notes)
- Feb 04: Reductions, P-completeness (see these notes)
Also see this for the discussion on o(loglog n) space.
- Feb 09: Non-determinism, containment of NP in EXP and PSPACE, Proof of Cook-Levin theorem (Section 2.1 to 2.3 of [AB]), also see this
- Feb 11: co-NP, P,NP,EXP, NEXP, non-deterministic time hierarchy theorem. Here is the proof I presented in class.
- Feb 16: Ladner's theorem, Turing reductions, oracle Turing machines (Section 3.3, 3.4 of [AB])
- Feb 18: Oracle Turing machines, Turing reductions, Limits of diagonalization and Baker-Gill-Solovay theorem (Section 3.4 of [AB])
- Feb 23: Space complexity: Introduction, space constructibility, space hierarchy theorems, containments: L,NL in P, PATH is NL-complete, Savitch's theorem, PSPACE=NPSPACE (Chapter 4 of [AB])
- Feb 25: Immerman-Szelepsnyi theorem (Chapter 4 of [AB])
- Mar 2: TQBF and its PSPACE-completeness (Chapter 4 of [AB])
- Mar 4: Polynomial hierarchy (Chapter 5 of [AB])
- Mar 9: Circuit complexity: the classes P/poly, NC
- Mar 11: Karp-Lipton theorem, Meyer's theorem, Turing machines with advice (Chapter 6 of [AB] for both lectures)
- Mar 25: Randomized computation: BPP, RP, ZPP, BPP in P/poly
- Mar 30: Sipser-Gacs theorem (Chapter 7 of [AB]), introduction to IP (Section 8.1), interactive private coin protocol for graph non-isomorphism
- Apr 1: Definition of IP, IP is in PSPACE, #3SAT is in IP (Chapter 8 of [AB])
- Apr 06: Correctness of the interactive protocol for #3SAT, interactive protocol for QBF (Chapter 8 of [AB])