Computational Complexity

Standard computational complexity topics from the canonical curriculum.

Core Topics

• Time Complexity Classes (P) — Running time, big-O order, and the class of polynomial-time problems.
• The Class NP & Verifiers — Short certificates, poly-time verifiers, and nondeterminism define NP.
• Polynomial-Time Reductions — Transform one problem into another to compare their hardness.
• Proving NP-Hardness (Gadget Reductions) — Gadget reductions from 3SAT and CLIQUE to show a new problem is hard.
• Space Complexity & PSPACE — Space as a resource, Savitch's theorem, and PSPACE-completeness via TQBF.
• L, NL & Savitch's Theorem — Log-space classes, NL-complete PATH, and the NL ⊆ L² simulation.
• Time & Space Hierarchy Theorems — Diagonalization: more time and space buy strictly more power.
• The Polynomial Hierarchy — Alternating quantifier blocks stack NP and coNP into an infinite tower.
• Boolean Circuits & P/poly — Nonuniform circuits, size and depth, and the class P/poly.
• Randomized Complexity (BPP, RP) — Probabilistic machines, one- vs two-sided error, and amplification.
• Approximation & PCP Theorem — Approximation ratios, the PCP characterization of NP, and inapproximability.

Not sure where to start? Take the ten-question placement test.