computability
Is there a fast route through every city?
It is the early 1970s, and computer science is discovering that some problems resist every clever algorithm anyone tries — not for lack of effort, but perhaps for a deep reason. Characterize the true computational difficulty of the traveling-salesman decision problem: is there a fast route visiting every city under a given budget? Place it precisely within the emerging hierarchy of complexity classes, and spell out what a fast general solution would imply — a vast web of problems long believed intractable falling at once. The stakes are foundational. Get it wrong and careers are wasted seeking an efficient algorithm that likely cannot exist, or problems merely hard are abandoned as hopeless — this classification reorganized what the whole field means by 'solvable.'
Who this problem belongs to
The two figures whose methods fit it best, out of 41 in contention.
This problem is essentially Cook's own 1971 paper, 'The Complexity of Theorem-Proving Procedures,' arriving on schedule. Cook supplied the exact machinery the task demands: polynomial-time reducibility, the class NP defined via nondeterministic polynomial-time verification, and the theorem that Boolean satisfiability is complete for NP — every NP problem reduces to it. With SAT established as the anchor, placing the traveling-salesman decision problem in the hierarchy is a matter of exhibiting one more reduction, and Cook's framework tells you precisely what a fast TSP algorithm would imply: P = NP, and the entire web of NP problems collapsing into tractability. The one caveat is division of labor — Cook built the foundation; the systematic cataloguing of specific problems like TSP was carried out by others. As the framework's author, he scores at the top.
Karp's 1972 paper 'Reducibility Among Combinatorial Problems' is the literal historical answer to this prompt: he took Cook's completeness theorem for SAT and propagated it, by a tree of explicit polynomial-time reductions, through 21 natural combinatorial problems — including directed and undirected Hamiltonian circuit, from which the TSP decision problem's NP-completeness follows immediately. The prompt's demand to 'spell out what a fast solution would imply' is exactly the rhetorical achievement of that paper: it revealed that dozens of problems practitioners had independently banged against were one problem in disguise. Karp had spent the 1960s designing efficient algorithms (later, Edmonds-Karp flows), so he knew intimately what polynomial-time solvability felt like and could recognize its absence. He scores a hair below Cook only because the foundational theorem was Cook's; the classification act itself is Karp's.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
41 figures are scored on this problem. Draw it in a battle to see where you land.