How NP-hardness spreads out from SAT.
An arrow A → B means A reduces to B, so B is at least as hard as A.
WASD to fly, Q/E down and up, Shift faster, Esc back to the start. Drag to turn, scroll to zoom.
Three maps of hard problems, one per tab. An arrow A → B is a reduction: it turns any instance of A into an instance of B with the same answer, so B is at least as hard as A. Hardness flows down the arrows from the problems at the top.
Click a problem for its definition and the reductions that prove it hard, or an arrow for the construction. Each problem has one bright canonical arrow, and its height is the length of its chain of canonical arrows; thin arrows are other published reductions. Implied adds dashed lines for pairs joined only through a longer path. Search covers all three maps.
Drag to turn, right-drag or two fingers to pan, scroll or pinch to zoom. WASD to fly, Q and E down and up, Shift to go faster. / searches. Esc clears the selection, and a second Esc goes back to the start.
Each node is an NP-complete problem (decision version), and every arrow is a polynomial-time reduction. Everything starts from SAT, which is NP-complete by the Cook–Levin theorem.
A problem's canonical arrow is Karp's reduction where he gave one, otherwise the standard one from Garey & Johnson or the original paper. Every problem here is also in NP (its panel shows the certificate), so each one reduces back to SAT as well; those arrows are left out.
Karp's 1972 paper has typos in three constructions (Chromatic Number, Max Cut, Job Sequencing), noted on those arrows. His Exact Cover → Steiner Tree reduction is wrong as printed: zero-weight edges let the tree use a set without paying for it, so the map uses Garey & Johnson's version. Where a printed version can be run, the program shows that it fails and that the fix works.
Codes like GT1 or SP5 are from the appendix of Garey & Johnson's Computers and Intractability (1979), still the closest thing to a catalogue of NP-complete problems. For complexity classes rather than problems, see the Complexity Zoo.
Each node is PSPACE-complete, with the two exceptions below, and most are games and puzzles. Every arrow is a polynomial-time reduction, starting from TQBF, true quantified Boolean formulas (Stockmeyer & Meyer).
Canonical arrows are the standard proofs; for the puzzles that is Hearn & Demaine's constraint logic, which replaced several longer first proofs. Each panel shows a polynomial-space algorithm for the problem, so it also reduces back to TQBF; those arrows are left out. The exceptions are Go and Checkers. Both are PSPACE-hard, but Checkers without a move limit and Go under Japanese ko rules are EXPTIME-complete (Robson), so they are not in PSPACE unless PSPACE = EXPTIME.
Hearn & Demaine's two Rush Hour gadgets were copied car by car from their figures, and every reachable position was searched. Both behave as claimed, though the text of their Lemma 18 has the OR gadget's directions backwards. Sipser's Geography graph also works for Edge Geography with the players swapped; the program found this, and it is not from a paper.
The puzzles follow Hearn & Demaine's Games, Puzzles, and Computation (2009); the logic and automata problems follow Garey & Johnson (codes like LO11) and Sipser's textbook.
Polynomial-time reductions say nothing inside P, because such a reduction can simply solve the problem. The arrows on this map are fine-grained reductions, which run faster than the problems they connect and keep track of exponents: if B could beat its known running time by a polynomial factor, so could A.
There is no single source. Each big node is a hypothesis about one problem's exact running time, mainly SETH (through Orthogonal Vectors), 3SUM and APSP, and each cluster is the family of problems whose hardness rests on one of them. The three main hypotheses were never shown to be related, and NSETH suggested that SETH cannot be reduced to the other two. Thin arrows pointing back up close equivalences, such as the APSP class. A few small nodes, like LIS, have no hardness at all and show how a special case can drop to near-linear time.
The orange family is about approximation. Distributed PCPs (PCP-Vectors) and an IP = PSPACE-style protocol (tropical similarity) turn SETH and OV into hardness for approximate inner products, LCS pairs and closest pairs. Gap Block Disjointness is the one hypothesis here that concerns only deterministic algorithms.
The 2026 button shows what three preprints from October and November 2026 did to the map, with a tab for each and one for all of them. Alman and Vassilevska Williams, with an algorithm found by Claude (Anthropic), refuted the 3SUM and APSP hypotheses; OpenAI refuted ETH and SETH; and Vassilevska Williams and Zamir, working with ChatGPT, refuted the k-Clique hypothesis. Reductions carry algorithms backwards along the arrows, so everything that reduces to 3SUM or APSP got faster, while the problems that had only been reduced from a refuted hypothesis lost their lower bounds. Most of the SETH family survives, because its bounds also follow from CNF-SAT with clauses of any width or from the OV hypothesis, and those are untouched. The combinatorial hypotheses about matrix products and cliques survive too: the new algorithms rely on algebraic cancellation, which "combinatorial" rules out.
Backurs and Indyk's edit distance gadgets and Abboud, Backurs and Vassilevska Williams' LCS gadgets are run with the smallest constants their proofs allow; the published ones (such as l0 = 1000d) make strings too long to solve exactly. One printed construction fails: in Cygan et al.'s reduction from superadditivity testing to unbounded knapsack, the threshold D is too small, because a light item can be used twice. A larger D fixes it, and the checker confirms both the failure and the fix.
Vassilevska Williams' survey On some fine-grained questions in algorithms and complexity (2018) is the closest thing to a catalogue. The convolution problems follow Cygan et al. (2017) and the geometry Gajentaan & Overmars (1995).
Each problem and arrow lists its own sources.