computability
The problem all others reduce to
It is 1971, and complexity theory needs a keystone: a first natural problem proven hardest in its class, so all others can be measured against it. Take Boolean satisfiability — is there an assignment making a logical formula true — and prove that every problem verifiable in polynomial time reduces to it, so that a fast algorithm for satisfiability would collapse the whole class at once. The proof must encode an arbitrary computation as a formula, mechanically. Then wield the tool: reduce satisfiability to fresh problems to grow the family of the provably hard. Get it wrong and the field has a zoo of hard-seeming problems with no way to relate them; get it right and one reduction technique organizes thousands into a shared fate.
Who this problem belongs to
The two figures whose methods fit it best, out of 39 in contention.
Cook is the theorem. His 1971 paper 'The Complexity of Theorem-Proving Procedures,' presented at the ACM Symposium on Theory of Computing, proved that Boolean satisfiability is NP-complete: every problem whose solutions can be verified in polynomial time can be reduced to it in polynomial time, by directly encoding an arbitrary nondeterministic Turing machine's computation history as a satisfiability instance. This single construction created the entire field of NP-completeness, gave complexity theory its first natural hard problem, and supplied the reduction technique that Karp immediately generalized. No one on this roster is closer to having personally invented the exact object, technique, and result this problem describes; the only reason the score is not 100 is that Leonid Levin independently discovered the same result in the Soviet Union, unknown to Cook.
Karp's 1972 paper, published one year after Cook's original theorem, took the single hardness result for satisfiability and showed it was the seed of an entire universe: twenty-one additional problems, from clique to vertex cover to the traveling salesman decision problem, all proven NP-complete via explicit polynomial-time reductions, transforming Cook's isolated theorem into the systematic map of computational hardness that defines the field today. Karp's reduction technique — showing how satisfiability reduces to problem after problem — is the tool that turns Cook's result into a universal organizing principle, exactly what this problem's second half asks for. He arrives one year after Cook, applying and generalizing rather than originating the initial theorem, but no one demonstrated its reach more decisively or more immediately.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
39 figures are scored on this problem. Draw it in a battle to see where you land.