Personal website Rudolf Adamkovič

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.


© 2025 Rudolf Adamkovič under GNU General Public License version 3.
Made with Emacs and secret alien technologies of yesteryear.