[CSS.203.1]
Computational Complexity
(2024, Jan–May)
Schedule: Tuesday, Thursday at 09:30 — 11:00 (IST)
Problem sets and exams
- Problem set 0: [PDF] (optional; recommended for those without prior background in automata theory)
- Problem set 1: [PDF] (Due date: 18 Feb 2024, last addition on 6 Feb 2024)
- Problem set 2: [PDF] (Due date: 9 Mar 2024, last addition on 22 Feb 2024)
- Problem set 3: [PDF] (Due date: 15 Apr 2024, last addition on 30 Mar 2024)
Lecture summary
Summary scribes: (only accessible internally)
[PDFs] [ZIP] [git repo]
- Lecture 1 (2024-01-16)
- Administrivia, introduction to the course, rough course outline and problems of interest, definition of Turing machines
- Lecture 2 (2024-01-18)
- Formal description of TMs and languages accepted by them, tape reduction, alphabet reduction, definition of universal Turing Machines, the class P.
- Lecture 3 (2024-01-23)
- Motivating non-determinism via automatas (aside: cloudflare outage), definition of non-determinism in TMs, the class NP and coNP, introducing CircuitEval, CircuitSAT, Tautology
- Lecture 4 (2024-01-25)
- Notion of reductions, Turing reductions and many-one-reductions, statement of the Cook-Levin theorem, reductions between independent set, clique, vertex cover, CNF-SAT, CircuitSAT etc.
- Lecture 5 (2024-01-30)
- Reductions to 3-colouring, introduction to computational tableau, proof of the Cook-Levin theorem
- Lecture 6 (2024-02-06)
- Padding arguments, proof of the deterministic time hierarchy theorem
- Lecture 7 (2024-02-08)
- Time-constructible functions, non-deterministic time hierarchy theorem
- Lecture 8 (2024-02-13)
- Ladner’s theorem - existence of NP-intermediate languages (assuming P != NP)
- Lecture 9 (2024-02-15)
- Oracle Turing Machines, Baker-Gill-Solovay theorem
- Lecture 10 (2024-02-22)
- Self-reducibility of NP, Mahoney’s theorem, introduction to the polynomial hierarchy
- Lecture 11 (2024-02-27)
- Polynomial hierarchy, complete problems, equivalence of Σ2 with NPNP etc.
- Lecture 12 (2024-02-29)
- Introduction to space complexity, classes such as L, NL, PSPACE, NPSPACE, configuration graphs and reachability, TQBF is PSPACE-complete and PSPACE = NPSPACE
- Lecture 13 (2024-03-05)
- (Instructor: Prahladh Harsha) Introduction to logspace machines, Savitch’s theorem, logspace reductions and properties
- Lecture 14 (2024-03-07)
- (Instructor: Prahladh Harsha) Non-deterministic logspace, NL-completeness, the PATH problem is NL-complete, read-once certificates for NL, Immerman-Szelepcsényi theorem
- Lecture 15 (2024-03-12)
- Wrapping up Immerman-Szelepcsényi theorem, introduction to circuits and non-uniformity, definition of AC0, NC0, AC1, NC1 etc., addition in AC0
- Lecture 16 (2024-03-14)
- Razborov-Smolensky’s proof that Parity is not in AC0
- Lecture 17 (2024-03-19)
- Circuit size hierarchy theorem, Karp-Lipton theorem, non-uniformity and advice
- Lecture 18 (2024-03-21)
- Introduction to randomised complexity classes, success-probability amplification
- Lecture 19 (2024-03-26)
- Adleman/Bennett-Gill theorem and the Sipser-Gács-Lautemann theorem
- Lecture 20 (2024-03-28)
- ZPP and relation to RP and coRP, completeness for BPP, semantic vs syntactic classes, promise problems
No classes until Apr 20