CS 721: Introduction to Complexity Theory
Known relationships between complexity classes
This course is a hike through the complexity zoo, with detours into different landscapes — space complexity, circuits, randomness, interactive proofs — and a look at how they connect. We begin with Turing machines and the classes P and NP, develop reductions and completeness, and work outward from there.
The main objective is a complexity-theoretic view of computation: how to formalize it, how to compare problems, and why establishing limits has proved so stubbornly hard.
| Prerequisites | A solid undergraduate background in algorithms, discrete mathematics and general mathematical maturity. Some familiarity with the theory of computation (Turing machines, P and NP) will be helpful but not required. |
| Teaching Assistants |
Aditya Neeraje (23b0940 [at] iitb [dot] ac [dot] in) Pavankumar N (25m0803 [at] iitb [dot] ac [dot] in) |
| Contact | vishwas [at] cse iitb [dot] ac [dot] in |
| Quiz / Assignment 7 total, best 5 counted — every other Friday |
25% |
| Mid-sem exam | 30% |
| End-sem exam | 45% |
| Paper presentation Bonus |
+20% |
| 1 |
Assignment 1 (PDF)
Tested in class on Fri, Aug 7, following a discussion / doubt-clearing session.
|
| Date | # | Topic |
|---|---|---|
| Tue, Jul 28 | 1 |
Introduction
Administrivia; problems of interest; Turing machines
|
| Fri, Jul 31 | 2 |
P, NP, and reductions
Definitions of P and NP; polynomial-time reductions
|
| Tue, Aug 4 | 3 |
Cook–Levin theorem and NP-hardness
Cook–Levin theorem; NP-hardness reductions
|
| TBD | 4 |
Diagonalization
Time and space hierarchy theorems, oracle separations
|
| More lectures to be added as the course progresses. | ||