Home / Computer science / NP-complete
Discovery
NP-completeness was discovered by [1]1 who
proved that every problem in NP reduces to SAT,
and applied by [2] 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.