Reducibility Among Combinatorial Problems
Twenty-one classic puzzles turn out to be one and the same hard problem in disguise.
Twenty-one famous puzzles that had stumped different fields for decades turned out to be, secretly, the very same puzzle.
The idea, unpacked
Some problems are easy to check but seem horribly hard to solve. Hand me a finished Sudoku and I can verify it in seconds; filling a blank one from scratch is far harder. A huge family of practical problems — scheduling, routing, packing, seating plans — share that lopsided character: a proposed answer is quick to check, but finding one seems to need a near-impossible search.
Karp's paper showed that twenty-one of these problems are not just similar but interchangeable. He found a way to translate any one of them into any other so faithfully that a fast solution to one would instantly give a fast solution to all. They are, in a precise sense, a single problem wearing twenty-one costumes.
Where it came from
In 1971 Stephen Cook proved that one logic problem — satisfiability, deciding whether a tangle of true/false conditions can all be met at once — was ‘hardest’ in a precise class of problems. It was a beautiful result, but it looked like it might be about that one problem. The next year, at an IBM symposium near New York, Richard Karp took Cook's tool and ran with it, showing through a chain of clever translations that twenty-one well-known problems were all just as hard. Overnight the result stopped being a curiosity and became a map.
Why it mattered
Before Karp, a researcher stuck on a hard problem couldn't tell whether they were missing a clever trick or facing something genuinely impossible. After Karp there was a test: show your problem is one of these — or reduces to one — and you've shown that nobody has a fast method for it, because a fast method would crack thousands of famous problems at once. He turned ‘I can't solve this’ into ‘this is provably as hard as the hardest problems we know.’
A way to picture it
Imagine a wall of twenty-one locked doors, each said to need its own special key. Karp built a set of adapters: a gadget that turns the key for any one door into the key for any other. Nobody has found a key yet — but now everyone knows that the first person to pick any single lock opens all of them. Whether such a key exists at all is the famous ‘P versus NP’ question, still unanswered.
Where it sits
Cook lit the match in 1971; Karp built the bonfire in 1972; and Leonid Levin, working in the Soviet Union, struck the same spark independently. Their idea — NP-completeness — sits beside Turing's 1936 limits on what computers can do at all: Turing asked what is computable, Cook and Karp asked what is computable quickly. The question they framed, P versus NP, is now one of the great unsolved problems in mathematics.
A large class of computational problems involve the determination of properties of graphs, digraphs, integers, arrays of integers, finite families of finite sets, boolean formulas and elements of other countable domains.