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.
Each sphere is an NP-complete problem (decision version). An arrow A → B is a polynomial-time reduction A ≤p B: it translates every instance of A into an instance of B with the same answer, so if B had a fast algorithm, so would A. Hardness therefore flows along the arrows, starting from SAT, which is NP-complete by the Cook–Levin theorem.
Every problem here is also in NP, so each one reduces back to SAT as well; those arrows are left out. Click a problem for its formal definition and the reductions that prove it hard. Click an arrow for the construction.
Drag to turn, right-drag (or two fingers) to pan, scroll or pinch to zoom. On a keyboard, W, A, S and D fly forward, left, back and right, Q and E move down and up, and Shift speeds this up. / jumps to search; Esc clears the selection, and pressed again returns to the starting view.
Each problem has one canonical reduction (bright arrows): Karp's original one where it exists, otherwise the standard one from Garey & Johnson or the original paper. The height of a problem is the length of its canonical chain from SAT. Thinner arrows are other published reductions. Dashed lines, shown on request, are implied reductions: pairs connected only through a longer path, which compose because polynomial-time maps compose.
Karp's 1972 paper was read in full from a scan. Three of its printed constructions contain typos, which are noted on the edges concerned: the Chromatic Number reduction (wrong number of colors, and one ∈ that should be ∉), the Max Cut threshold (¼Σci2 for ¼(Σci)2), and the missing penalty bound in Job Sequencing. One is wrong outright: the Exact Cover → Steiner Tree construction, where zero-weight edges let the tree use a set without paying for it. Wherever the printed version can be run, the checker confirms that it fails and that the corrected one holds; the map uses Garey & Johnson's version of the Steiner Tree reduction instead.
Garey & Johnson codes (GT1, SP5, …) refer to the appendix of Computers and Intractability (1979), which is still the closest thing to a zoo of NP-complete problems; the Complexity Zoo catalogs complexity classes instead.