Theory of computation 2026

Computational Complexity Theory

Course overview

Computational complexity theory studies the resources required to solve computational problems and the fundamental limitations of efficient computation. The course develops the main models, techniques, and complexity classes used to reason rigorously about computational difficulty.

The course begins with time and space as computational resources and develops the basic complexity classes and hierarchy theorems. It then studies nondeterminism, NP-completeness, space complexity, circuits and nonuniform computation, the polynomial hierarchy, and randomized computation. The final part introduces communication complexity and shows how communication lower bounds can be used to prove lower bounds for streaming algorithms.

A recurring theme of the course is the use of reductions, diagonalization, counting, configurations, probabilistic arguments, and structural characterizations to compare computational models and establish upper and lower bounds.

Lecturers

Role	Lecturer
Course lecturer	Subin Pulari
Seminar lecturer	Yaroslav Ivanashev

Evaluation policy

The course has no homework component. Evaluation is based on two colloquia and two examinations.

• Colloquium 1 – during the first half of the course
• Colloquium 2 – during the second half of the course
• Midterm examination
• Final examination

Let <math>C_1,C_2</math> denote the two colloquium grades and <math>E_1,E_2</math> denote the two examination grades.

The final course grade is calculated as

<math>

\mathrm{Final\ Grade} = 0.6\left(\frac{C_1+C_2}{2}\right) + 0.4\left(\frac{E_1+E_2}{2}\right). </math>

Thus:

• 60% of the final grade comes from the average of the two colloquia;
• 40% comes from the average of the two examinations.

Lectures and seminars

Lecture	Contents	Lecture notes	Seminar notes
1	Computational models and resource bounds. Multitape Turing machines; configurations; time and space complexity; <math>\mathrm{DTIME}</math> and <math>\mathrm{DSPACE}</math>; <math>\mathbf P</math>, <math>\mathbf{PSPACE}</math>, and <math>\mathbf{EXP}</math>; machine-model robustness; efficient universal simulation in <math>O(T\log T)</math> time; time- and space-constructible bounds.	Lectures 1–4	Seminar 1–4
2	Nondeterminism, NP, and reductions. Nondeterministic computation; polynomial-time verifiers and certificates; equivalence of the two definitions of <math>\mathbf{NP}</math>; polynomial-time many-one reductions; NP-hardness and NP-completeness; bounded nondeterministic machine acceptance.	Lectures 1–4	Seminar 1–4
3	The Cook–Levin theorem. Computation tableaux; Boolean encoding of configurations; start, transition, and acceptance constraints; local consistency; the local-to-global argument; polynomial-size construction; SAT is NP-complete.	Lectures 1–4	Seminar 1–4
4	Time and space hierarchy theorems. Diagonalization; padded machine descriptions; universal simulation; deterministic time hierarchy; deterministic space hierarchy; constructibility; strict separations between resource-bounded classes.	Lectures 1–4	Seminar 1–4
5	Space complexity and Savitch's theorem. Configuration graphs; logarithmic space; directed <math>s</math>–<math>t</math> connectivity; log-space reductions; STCON is NL-complete; recursive reachability; Savitch's theorem <math>\mathrm{NSPACE}(s)\subseteq\mathrm{DSPACE}(s^2)</math>; <math>\mathbf{NPSPACE}=\mathbf{PSPACE}</math>.	Lectures 5–8	Seminar 5–8
6	The Immerman–Szelepcsényi theorem. Nondeterministic space and complementation; reachability layers; inductive counting; certification of nonreachability; <math>\mathbf{NL}=\mathbf{coNL}</math>; closure of nondeterministic space under complement.	Lectures 5–8	Seminar 5–8
7	PSPACE-completeness. Quantified Boolean formulas; recursive QBF evaluation; <math>\mathrm{TQBF}\in\mathbf{PSPACE}</math>; succinct configuration reachability; universal-selector compression; PSPACE-hardness of TQBF; games and succinct planning.	Lectures 5–8	Seminar 5–8
8	Boolean circuits and nonuniformity. Boolean circuits; circuit size and depth; circuit families; <math>\mathbf{P}/\mathrm{poly}</math>; simulation of polynomial-time machines by polynomial-size circuits; nonuniform computation; polynomial advice; equivalence between polynomial advice and polynomial-size circuit families.	Lectures 5–8	Seminar 5–8
9	Circuit size and parallel computation. Shannon's counting argument; existence and abundance of hard Boolean functions; uniformity; <math>\mathbf{NC}^k</math> and <math>\mathbf{AC}^k</math>; bounded-fan-in depth lower bounds; locality of <math>\mathbf{NC}^0</math>; constant-depth circuits for binary addition.	Lectures 9–12	Seminar 9–12
10	The polynomial hierarchy. Alternating quantified-predicate characterizations; <math>\mathbf{\Sigma}_k^{\mathbf P}</math> and <math>\mathbf{\Pi}_k^{\mathbf P}</math>; quantified-circuit complete problems; complementation; collapse of the polynomial hierarchy; <math>\mathbf{PH}\subseteq\mathbf{PSPACE}</math>.	Lectures 9–12	Seminar 9–12
11	Randomized computation. Probabilistic Turing machines; <math>\mathbf{RP}</math>, <math>\mathbf{coRP}</math>, <math>\mathbf{ZPP}</math>, and <math>\mathbf{BPP}</math>; one-sided and two-sided error amplification; <math>\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{coRP}</math>; Adleman's theorem <math>\mathbf{BPP}\subseteq\mathbf{P}/\mathrm{poly}</math>.	Lectures 9–12	Seminar 9–12
12	The Sipser–Gács–Lautemann theorem. Amplification to exponentially small error; dense and sparse accepting sets; translations of the Boolean cube; covering lemma and the probabilistic method; quantified covering characterization; <math>\mathbf{BPP}\subseteq\mathbf{\Sigma}_2^{\mathbf P}\cap\mathbf{\Pi}_2^{\mathbf P}</math>.	Lectures 9–12	Seminar 9–12
13	Communication complexity. Deterministic two-party protocols; protocol trees and transcripts; communication matrices; combinatorial rectangles; rectangle lower bounds; deterministic complexity of EQUALITY; public-coin fingerprinting; one-way communication; the INDEX lower bound.	Lectures 13–14	Seminar 13–14
14	Streaming algorithms and sketches. One-pass streaming and frequency vectors; point queries; pairwise-independent hashing; Count–Min Sketch; collision analysis and confidence amplification; fixed-query and simultaneous guarantees; sketch space complexity; communication reductions; INDEX-based streaming-space lower bounds.	Lectures 13–14	Seminar 13–14