CS 721: Introduction to Complexity Theory

Semester: Autumn 2026–27  ·  IIT Bombay
Instructor: Vishwas Bhargava
Time: 3:30 – 5 pm
Location: LT003
Complexity class diagram showing relationships between AC⁰, L, NC, P, NP, coNP, BPP, PH, PSPACE, EXP and others
Known relationships between complexity classes
About Topics Grading Assignments Lectures References

About

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

Tentative Topics

Definite topics (Arora–Barak Chs 1–7, plus some of Chs 8, 11)
Possible topics (material from Arora–Barak Chs 8, 13, 14, 16, 17, 19)

Grading

Quiz / Assignment
7 total, best 5 counted — every other Friday		 25%
Mid-sem exam30%
End-sem exam45%
Paper presentation
Bonus		 +20%

Assignments

1 Assignment 1 (PDF)
Tested in class on Fri, Aug 7, following a discussion / doubt-clearing session.
2 Assignment 2 (PDF)
Tested in class on Fri, Aug 21.
3 Assignment 3 (PDF)
Tested in class on Fri, Sep 4.

Lectures

Handwritten Notes

Lectures 1–2  ·  Lecture 3 onwards (running notebook, GoodNotes, view-only)

Date # Topic
Tue, Jul 28 1
Introduction
Administrivia; problems of interest; Turing machines
[AB] §1.1–1.3
Fri, Jul 31 2
P, NP, and reductions
Definitions of P and NP; polynomial-time reductions
[AB] §2.1–2.2
Tue, Aug 4 3
Cook–Levin theorem and NP-hardness
Cook–Levin theorem; NP-hardness reductions
[AB] §2.3–2.4
Fri, Aug 7 4
Assignment 1 quiz
Discussion / doubt-clearing session, followed by the in-class test
Tue, Aug 11 5
The art of reductions
Special lecture on designing NP-hardness reductions
Fri, Aug 14 6
coNP and the time hierarchy theorem
Padding argument; coNP; the (deterministic) time hierarchy theorem
[AB] §2.6, §3.1
Tue, Aug 18 7
Ladner's theorem and relativization
Ladner's theorem (NP-intermediate problems); the relativization barrier
[AB] §3.4–3.5
Fri, Aug 21 8
Assignment 2 quiz
In-class test, followed by the proof of the Baker–Gil–Solovay theorem
Tue, Aug 25 9
Space complexity: PSPACE
Configuration graphs; space complexity classes; PSPACE-completeness (TQBF)
[AB] §4.1–4.3
Fri, Aug 28 10
Logspace complexity: L, NL
Logspace reductions; NL-completeness
[AB] §4.4
Tue, Sep 1 11
NL = coNL, and the polynomial hierarchy
The Immerman–Szelepcsényi theorem; the polynomial hierarchy (PH)
[AB] §4.4.2, §5.1–5.2
Fri, Sep 4 12
Assignment 3 quiz
In-class test, followed by more on alternation and the polynomial hierarchy
[AB] §5.3–5.5
Tue, Sep 8 13
Boolean circuits
Boolean circuits and circuit families; P/poly
[AB] §6.1
Fri, Sep 11 14
Parallel computation and NC
Definition of NC and related circuit classes
[AB] §6.5.1
More lectures to be added as the course progresses.

References