Some problems get solved instantly however big they grow. Others seem to need time that doubles with every new variable. Complexity theory asks which is which, and why. This module builds that theory out of one puzzle — set some switches so that every clause is happy — across 21 interactive demonstrations. Watch random formulas fall off a cliff from easy to impossible. Race brute force against backtracking and a random walk. Turn a formula into a graph. Map P, NP and their neighbours. Follow the Exponential Time Hypothesis and its strong form down to lower bounds for edit distance. And weigh the two claims, made in October 2026 and still under review, that ETH is false.
See also: Algorithms for recurrences and running times, Mathematical Logic for normal forms and Gödel, and Graph Theory for the colourings and cliques that reductions land in.
Flip switches until every clause is happy. Why 2ⁿ assignments is a wall, and the sharp cliff where random formulas go from easy to impossible
Backtracking with unit propagation, Schöning’s random walk, and PPSZ — every trick lowers the base of the exponential, none removes it
Turn a formula into a graph and a solution into a set of vertices. How one hard problem wears the costume of another
Checking an answer is easy; finding one seems hard. Polynomial against exponential growth, and the map of complexity classes
Impagliazzo and Paturi’s 1999 bet: 3-SAT needs truly exponential time. The strong version, the sparsification lemma, and what follows
If SETH holds, edit distance can’t beat n². Split-and-list, orthogonal vectors, and lower bounds for problems already in P
In October 2026 OpenAI and Anthropic each posted a Lean-checked algorithm said to break ETH. What they claim, what Lean checks, and why SAT is not suddenly easy