computability
More time, strictly more power
It is the dawn of complexity theory, and before anyone can compare problems they must establish something more basic: that giving a machine more of a resource genuinely lets it solve strictly more problems. Prove the hierarchy theorems — that with meaningfully more time (or space) there exist problems solvable that were not before — using diagonalization to construct an explicit problem that outruns every machine held to the smaller budget. This is the first evidence that complexity classes are truly distinct and not artifacts of definition. Get it wrong and the entire tower of classes might secretly collapse into one, making the field's careful distinctions meaningless — the hierarchy theorems are the load-bearing proof that "harder" is a real, provable relation.
Who this problem belongs to
The two figures whose methods fit it best, out of 45 in contention.
This is Turing's own method turned into a theorem. His 1936 halting-problem proof invented diagonalization for computation: construct a machine that, run on a listing of all machines, does the opposite of what the k-th machine does on input k, producing an object no machine on the list can be. The time and space hierarchy theorems of the 1960s are the direct descendants of exactly this trick, budgeted rather than unbounded, using a universal machine to simulate every smaller-budget machine and diagonalize against each. Turing gave the field both the universal machine the simulation needs and the diagonal argument the separation needs, a generation before the theorem was formally stated. He is not merely relevant; he is the reason the proof technique exists at all.
Cook's career is complexity classes taken as the central object of study, which is exactly what hierarchy theorems certify are meaningfully distinct. His 1971 NP-completeness theorem presupposes that P and larger classes are not trivially identical, resting on the same diagonalization foundation the hierarchy theorems supply. Working at Toronto through the 1960s and 70s on the structure of computation under resource bounds, Cook helped make precise the very notion of 'more time' as a formal resource, the currency the hierarchy theorems trade in. He would recognize the universal-machine simulate-and-diagonalize construction immediately as a cousin of his own reductions. He is not the theorem's original author but is squarely the tradition's leading architect, deeply fluent in every piece of its machinery.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
45 figures are scored on this problem. Draw it in a battle to see where you land.