Hardness travels along a wire. Karp gave the wire a shape: a polynomial-time many-one map f that carries one problem into another so that x is a YES-instance of A exactly when f(x) is a YES-instance of B — the biconditional. Build f from 3-SAT to INDEPENDENT-SET: a k-clause formula is satisfiable iff its clause-gadget graph has an independent set of size k. Down the center a formula goes in, the map builds a graph, and the answer comes out unchanged. The blue team proves the map preserves the answer; the red team ships a broken map that lies.
source R. M. Karp, Reducibility Among Combinatorial Problems, in Complexity of Computer Computations, Plenum Press 1972, pp. 85–103 — doi 10.1007/978-1-4684-2001-2_9 (author copy: cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf). Rendered, not quoted.
The map f turns a CNF formula into a graph, deterministically:
V1 one vertex per literal occurrence — clause i with j literals gives j vertices. E1 the clique: join every pair of vertices in the same clause (so an independent set takes at most one literal per clause). E2 the conflict edge: join two vertices whose literals are complementary — x and ¬x — anywhere they appear. k = the number of clauses.
Biconditional: picking one true literal per clause is a size-k independent set (clique edges force one-per-clause; conflict edges force consistency), and any size-k independent set is exactly such an assignment. Live map of the current formula:
| clause | vertices | within-clause edges |
|---|
One reduction is a wire between two problems. Karp laid 21 of them, linking SAT to CLIQUE, VERTEX-COVER, HAMILTONIAN, PARTITION and the rest — each a poly map, so a solver for any one solves them all.
The current flows in from the Cook–Levin theorem: Cook proved SAT is NP-complete — every NP problem reduces to it. Karp then carries SAT onward by maps exactly like this one, and NP-completeness propagates. Each sphere is the next one’s premise.
The blue team’s live check: re-run the biconditional over every formula in the bounded family and confirm SAT(x) equals INDSET(f(x)) in both directions. If red ships a broken map, the NO-direction fails here and this badge turns red.
Problem A is SAT: given a CNF formula over variables x1, x2, is there an assignment making every clause true? A clause is a disjunction (∨) of literals; the formula is their conjunction (∧). This is what you feed the map.
Problem B is INDEPENDENT-SET: given a graph and an integer k, is there a set of k vertices with no edge between them? The map f rewrites the A-question as a B-question without changing the answer.
SAT is decided by brute force over all assignments; INDEPENDENT-SET by brute force over all vertex subsets. Nothing is looked up — the answers are computed, then compared.
What the machine proves, exactly: across the whole bounded family, SAT(x) = INDSET(f(x)) in both directions — YES maps to YES and NO maps to NO. The output graph is linear in the input (|V| = total literals, |E| ≤ |V|²), so f runs in polynomial time, and a poly solver for B would decide A. That is a Karp reduction.
The blue witness (left) confirms the biconditional live; the red team (right) tries to make the map lie.
A Karp (many-one) reduction is also weaker than a Cook (Turing) reduction, which may call the B-oracle many times and negate. And it preserves only the yes/no bit — not solution quality, so it says nothing about approximation. Get the map wrong and it preserves nothing at all.
“A reduces to B means A is harder than B.” Cut. It means B is at least as hard as A (B ≥ A): if you can solve B fast, you can solve A fast. The arrow points the other way.
“NP-complete means unsolvable.” Cut. Every one is decidable by brute force — INDEPENDENT-SET is decided live here. What is unknown is a polynomial algorithm.
“Any polynomial map is a valid reduction.” Kept, corrected. It must also preserve the answer — the biconditional, both directions. A map that only keeps YES→YES is the tamper next door.
The red team ships a “reduction” that drops the conflict edges. It still keeps YES→YES, so it looks fine on satisfiable inputs — but a contradictory formula like (x1) ∧ (¬x1) now maps to two unconnected vertices, giving a size-2 independent set. B answers YES; A is NO.
Drop the conflict edges and the map lies on the NO-direction — a false YES. The witness (window 7) recomputes the biconditional, finds the mismatch, and turns red. Nothing is faked; the attack is real and it is caught.