The course consists of three 50-minute lectures per week. Some familiarity with the theory of computation, algorithm design, and discrete mathematics is expected.
| Class-time: Monday 10:00-10:50; Wednesday 10:00-10:50; Friday 12:00-12:50 Room No. KD101 |
| Grading: Mid-sem: 30, End-sem: 50, Internal evaluation: 20 |
| Books |
(B1) Introduction to the Theory of Computation by Michael Sipser. (B2) Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. (B3) Computational Complexity: A Modern Approach by Sanjeev Arora, Boaz Barak. (B4) Mathematics and Computation: A Theory Revolutionizing Technology and Science by Avi Wigderson. |
| Lecture Notes |
(L1) Lecture Notes on Computational Complexity by Luca Trevisan. (L2) [CSS.203.1]: Computational Complexity (2024-I) by Ramprasad Saptharishi. |
| Lecture Videos |
(V1) Undergraduate Computational Complexity Theory by Ryan O'Donnell. (V2) NPTEL: Basics of Computational Complexity by Nitin Saxena. |
| LECTURE DATES | TOPICS | REFERENCES |
| Lecture 1 (08.01.2025) |
Course overview, grading policy, formalizing computation | [B4, B3] |
| Lecture 2 (10.01.2025) |
Turing machine model and its variants, Robustness | [B2, B1, B3] |
| Lecture 3 (13.01.2025) |
Robustness of Turing machine model, Universal Turing machine | [B2, B1, B3] |
| Lecture 4 (15.01.2025) |
Enumeration of Turing Machine, undecidability proof, diagonalization | [B2] |
| Lecture 5 (17.01.2025) |
Proof of Rice's Theorem
Introduction to Reduction |
[B2] |
| Lecture 6 (20.01.2025) |
A natural undecidable problem: Post's Correspondence Problem | [B2] |
| Lecture 7 (22.01.2025) |
Introduction to the complexity classes: P, NP, EXP
Class P: efficient computation |
[B4, B1, B3] |
| Lecture 8 (24.01.2025) |
Class NP: efficient verification, equivalent definitions Relationship of P, NP, EXP |
[B3, B1, B4] |
| Lecture 9 (27.01.2025) |
Proof of deterministic time hierarchy theorem | [L2] |
| Lecture 10 (29.01.2025) |
Time hierarchy theorem [continued] polynomial-time reductions |
[L2, B3] |
| Lecture - (31.01.2025) |
Class cancelled | - |
| Lecture 11 (03.02.2025) |
Introduction to NP-completeness and its properties Cook-Levin Theorem |
[L2, L3, B4] |
| Lecture 12 (05.02.2025) |
Proof of Cook-Levin Theorem [continued] | [L2, class-notes] |
| Lecture 13 (07.02.2025) |
Boolean circuits, Circuit evaluation A different proof of Cook-Levin Theorem |
[L2, L3] |
| Lecture - (10.01.2025) |
Class cancelled | - |
| Lecture 14 (12.02.2025) |
More on reduction Introduction to the class coNP Well-characterization of computational problems |
[B3, B4] |
| Lecture 15 (14.02.2025) |
NP-intermediate languages Ladner's theorem |
[L2, B3] |
| Lecture 16 (15.02.2025) |
Proof of Ladner's theorem [continued] | [L2, B3, class-notes] |
| Lecture 17 (17.02.2025) |
Proof of non-deterministic time hierarchy theorem | [L2] |
| Lecture 18 (19.02.2025) |
Sparsity of NP-complete languages -- Mahaney's theorem | [link] |
| Lecture - (21.02.2025) |
Mid-term week: no class | - |
| Lecture - (24.02.2025) |
Mid-term week: no class | - |
| Lecture - (26.02.2025) |
Mid-term week: no class | - |
| Lecture - (28.02.2025) |
Mid-term week: no class | - |
| Lecture 19 (03.03.2025) |
Oracle Turing machines difficulty of separating P, NP | [link] |
| Lecture 20 (05.03.2025) |
Introduction to space complexity configuaration graph, complexity class: PSPACE | [B3, L2, B1] |
| Lecture 21 (07.03.2025) |
Savitch's theorem PSPACE-complete problem | [L2, B3] |
| Lecture - (10.03.2025) |
Mid-term recess: no class | - |
| Lecture - (12.03.2025) |
Mid-term recess: no class | - |
| Lecture - (14.03.2025) |
Mid-term recess: no class | - |
| Lecture - (17.03.2025) |
Health issue: no class | - |
| Lecture - (19.03.2025) |
Health issue: no class | - |
| Lecture - (21.03.2025) |
Health issue: no class | - |
| Lecture 22 (24.03.2025) |
More on space complexity, log-space computation | [B3] |
| Lecture 23 (26.03.2025) |
Proof of Immerman-Szelepcsenyi theorem | [L1, L2, B3] |
| Lecture - (28.03.2025) |
Tech-fest: no class | - |
| Lecture - (31.03.2025) |
Institute holiday: no class | - |
| Lecture 24 (02.04.2025) |
Introduction to polynomial hierarchy quantifier-based definition | [B3, L2] |
| Lecture 25 (04.04.2025) |
Oracle-based definition of polynomial hierarchy | [B3, L2, class-notes] |
| Lecture 26-27 (05.04.2025) |
Polynomial hierarchy via alternating Turing machines Time-space tradeoff of SAT | [link, B3, class-notes] |
| Lecture 28 (07.04.2025) |
Introduction to randomized complexity | [B3, L2] |
| Lecture 29 (09.04.2025) |
Randomized complexity continued, Introducing probabilistic complexity classes | [B3, L2] |
| Lecture 30 (11.04.2025) |
Proof of error reduction Proof of Sipser-Gacs Theorem | -[L2, B3, class-notes] |
| Lecture 31-32 (12.04.2025) |
Boolean circuit complexity Proof of Karp-Lipton Theorem | [L1, L2, B3] |
| Lecture - (14.04.2025) |
Institute Holiday: no class | - |
| Lecture 33 (16.04.2025) |
Introduction to interactive proof system | [L1, B3] |
| Lecture - (18.04.2025) |
One-to-one interaction with the students | - |
| Lecture 34 (19.04.2025) |
Interactive Proofs [continued], IP is in PSPACE | [B1, B3] |
| Lecture 35-36 (20.04.2025) |
Proof of coNP is in IP and IP = PSPACE | [B3, B1, class-notes] |
| Lecture 37 (21.04.2025) |
Revisiting the course | - |