Computational Complexity

Assumed background

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.

Course plan

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.

Reference books

  1. Computational Complexity: A Modern Approach by Sanjeev Arora, and Boaz Barak Online draft[AB]
  2. Lecture notes by Ramprasad Saptharishi
  3. Computational Complexity by Christos Papadimitriou
    4. [CP]
  4. Introduction to the Theory of Computation by Michael Sipser
    5. [MS]
There are several online lecture notes. I will mention appropriate references from time to time.
Top

Evaluation

There will be assignments, a midsem, and an endsem exam. Top

Copying policy

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.
Top

Lectures

Topics covered so far (refer to [AB] unless otherwise mentioned):

  1. Jan 7: Introduction, computation, Turing machines, informal definitions of complexity classes (Ref:introduction in [AB], and relevant parts of Chapter 1 of [AB].)
  2. Jan 9: Turing machines, non-determinism, definitions of P,NP,EXP,NEXP,L,PSPACE, multitape vs two tape Turing machines, alphabet reduction, universal Turing machine (Sections 1.2,1.3,1.4 of [AB], also see first three lectures of [RP]
  3. Jan 14: Reductions, NP-completeness, SAT, beginning of Cook-Levin theorem (Ref: [AB] and [RP])

    4. Jan 16: No class (instructor traveling)
  4. Jan 21: Proof of Cook-Levin theorem (Ref: Sipser's book "Introduction to the Theory of Computation)

    5. Jan 23: No class (Tessellate)
  5. Jan 28: Decision vs search for NP, self-reducibility of SAT, co-NP, EXP, NEXP, relation between P,NP vs EXP,NEXP, space complexity: configuration graphs, containment of space and time classes (Ref: Sections 2.4, 2.5, 3.1, 3.2 from [AB])
  6. Jan 30: Savitch's theorem, Reachability is NL-complete (Sections 8.1, 8.4, 8.5 of [Sipser])