Turn a formula into a graph and a solution into a set of vertices. How one hard problem wears the costume of another
A reduction translates every instance of one problem into an instance of another, quickly, so that yes stays yes and no stays no. If the second problem could be solved fast, so could the first: hardness flows along reductions. In 1972 Richard Karp used them to show that 21 famous problems are all equally hard.
Flip the switches and watch one true literal per clause light up: when every clause is satisfied they form an independent set of size m. Then click vertices yourself and try to break the rule.
Each triangle is a clause, each vertex one of its literals. Grey edges join literals of the same clause; amber arcs join x and ¬x in different clauses. A green ring marks a literal that is true under the current assignment; picked vertices glow fuchsia, or red when an edge joins two of them. The graph has exactly 3m vertices, so it grows in step with the formula. Click any vertex to pick or unpick it.
An independent set is a set of vertices with no edge between any two of them. Given a 3-CNF formula with m clauses, build a triangle for each clause, one vertex per literal, and join every x to every ¬x in other clauses. An independent set can take at most one vertex from each triangle, so it has at most m vertices. If the formula is satisfiable, take one true literal from each clause: no two of them contradict, so they are independent. Conversely, an independent set of size m picks one literal per clause with no x and ¬x together, so making those literals true satisfies every clause. Satisfiable if and only if the graph has an independent set of size m.
This is a polynomial-time many-one reduction: a fast translation of each instance, with the answer preserved. Richard Karp’s 1972 paper “Reducibility Among Combinatorial Problems” used chains of such translations, starting from satisfiability, to show 21 problems NP-complete, among them clique, vertex cover, chromatic number, Hamiltonian circuit and knapsack. Independent set is clique in disguise: a set is independent in a graph exactly when it is a clique in the complement graph. And a set is independent exactly when the remaining vertices form a vertex cover, a set touching every edge.
Notice the size: 3m vertices and at most a quadratic number of edges, but the number of vertices grows only linearly with the formula. That matters for finer questions than “polynomial or not”. If a reduction blows n variables up into n² vertices, a 2^√N algorithm for the target would only give a 2ⁿ algorithm for the source. Linear-size reductions carry exponential lower bounds across intact. See also The Exponential Time Hypothesis.
Toggle the variables and watch the gadgets: a clause with a true input colours cleanly, a clause with none pulses red. Switch to the unsatisfiable formula and press “Solve the colouring”.
Green = T, rose = F, blue = B. Each literal pair is joined to B, so one of x, ¬x is T and the other F. In each gadget, u is or(a, b) and o is or(u, c); the little F and B tags under o stand for edges to the palette, which force o to be T. Gadgets are coloured by trying all 3⁶ = 729 options; “Solve the colouring” searches the whole graph by backtracking and reads the switches off the result.
Three colours, three meanings. The palette triangle fixes which colour means true, which means false, and a third base colour B. Joining x and ¬x to each other and to B forces one of them to be T and the other F: the colouring has become a truth assignment. The OR gadget is the clever part. With inputs a and b, the triangle p₁, q₁, u can give u the colour T whenever a or b is T, but if both are F then p₁ and q₁ must take T and B, leaving u only F. Chain two of these to get or(or(a, b), c), and join the final output to F and B so it has to be T. The gadget can be coloured exactly when some input is T — the module’s tests check all eight input patterns.
Gadgets are the working method of NP-completeness proofs: small local widgets that simulate logic inside another problem. Karp’s list includes chromatic number, the question of whether a graph can be coloured with k colours. In 1973 Larry Stockmeyer showed that 3-colouring stays NP-complete even for planar graphs, using a crossover gadget that lets two edges cross without interacting.
Two colours are a different story. A graph is 2-colourable exactly when it is bipartite, which breadth-first search decides in linear time: colour a vertex, give its neighbours the other colour, and look for a clash. The jump from two colours to three is a jump from easy to NP-complete, just as 2-SAT is solvable in linear time while 3-SAT is not known to be.
Click cells to set clues and watch the formula grow, then press “Solve with SAT”. Try the empty grid, and the puzzle whose contradiction is hidden.
Click a cell to cycle its clue: blank, 1, 2, 3, 4
Click a bar to list that family of clauses. “Each cell holds a digit” clauses have four positive literals; every other rule is a pair of negated literals saying “not both”. To count solutions, each one found is forbidden by a new clause — the negation of its 16 true variables — and the solver is run again.
The first two demos reduced SAT to other problems, showing they are at least as hard. This one goes the other way, and the direction is general. The Cook–Levin theorem, proved independently by Stephen Cook in 1971 and Leonid Levin in 1973, says every problem in NP reduces to SAT. A problem is in NP when a proposed answer can be checked in polynomial time; Cook and Levin showed how to compile any such checker, step by step, into a formula that is satisfiable exactly when some answer passes the check. SAT was the first problem shown NP-complete, and Karp’s reductions started from it.
The same idea is an everyday engineering tool. Hardware verification, software package dependency resolution and automated planning are routinely solved by encoding them into SAT and handing the formula to a solver, as this demo does with a 4×4 Sudoku: 64 variables, about 400 clauses, and a solver that knows nothing about puzzles. The empty grid has 288 completions, all the 4×4 Sudoku grids there are.
Ordinary 9×9 Sudoku is a fixed, finite puzzle, so it has no interesting asymptotic complexity. The generalised version on an n² × n² grid is NP-complete, shown by Takayuki Yato and Takahiro Seta in 2003.
Spot a mistake or have an idea?