1971
Stephen Cook proves NP-completeness
Stephen Cook published his theorem on NP-completenessThe property of being among the hardest problems in NP — central to computational complexity theory. in 1971 — defining the hardness class behind thousands of optimization problems.
What it was for
Cook's work (and Karp's reductions) explained why many problems seem equally hard — shaping cryptography, scheduling, and complexity theory. P vs NP remains the field's defining open question.
People
- Stephen Cook — researcher
Why it's here
NP-completenessThe property of being among the hardest problems in NP — central to computational complexity theory. is the central concept in computational complexity theory.
Why it mattered
It gave a framework for identifying intractable problems in software and research.
What it solved
There was no rigorous way to classify which problems were feasibly solvable.
Media
ImageStephen CookJiří Janíček, CC BY-SA 3.0, via Wikimedia Commons