The Cook-Levin Theorem
In 1971, Stephen Cook proved that one specific problem sits at the top of the entire NP hierarchy — and that solving it would solve everything else. This is the result that launched the field of NP-Completeness.
In 1971, Stephen Cook proved that one specific problem sits at the top of the entire NP hierarchy — and that solving it would solve everything else. This is the result that launched the field of NP-Completeness.