Rudolf Adamkovič Personal site

Up: NP-complete   [Top][Contents]

History

  1. Bootstrapped with SAT by Cook (1971).
  2. Proved and extended to 21 problems by Karp (1972).

[Both seminal papers yielded Turing Awards.]

The bootstrapping is due to

the Cook–Levin5 theorem,

or just Cook’s theorem.

Footnotes

(5)

Levin co-discovered NP-completeness in Soviet Russia.

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