Home / Computer science / NP-complete
Discovery
NP-completeness was discovered by Cook (1971)1 who
proved that every problem in NP reduces to SAT,
and applied by Karp (1972) who showed it holds to
reduced 21 important combinatorial problems,
both receiving Turing Awards.
Footnotes:
1
Per the Cook-Levin theorem, where Levin co-discovered NP-completeness in Soviet Russia.