Rudolf Adamkovič Personal site


NP-complete

a.k.a.

Define

A complexity class of every decision problem that is

equivalent to all NP problems under polynomial reduction;

Symbolically,

\[\begin{equation*}
  L \in \mathrm{NPC}
  \> \iff \>
  \big( L \in \mathrm{NP} \big)
  \land
  \big( \forall L' \! \in \mathrm{NP}, \>\> L' \leq_p L \big).
\end{equation*}
\]

Intuit

These are the hardest problems in NP because:

  1. By definition, all NP problems reduce to these.
  2. So, they are at least as hard as every problem in NP.
  3. So, they are the hardest problems in NP.

Dig

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

[Both seminal papers yielded Turing Awards.]

The SAT bootstrapping is dubbed

Cook–Levin11 theorem,

or just Cook’s theorem.


Footnotes

(9)

A BibTeX entry:

@InProceedings{cook-1971,
  author       = {Cook, Stephen A.},
  title        = {The complexity of theorem-proving procedures},
  booktitle    = {Proceedings of the Third Annual {ACM} Symposium on Theory of
                  Computing},
  year         = 1971,
  series       = {STOC '71},
  pages        = {151–158},
  address      = {New York, NY, USA},
  publisher    = {Association for Computing Machinery},
  isbn         = 9781450374644,
  doi          = {10.1145/800157.805047},
  numpages     = 8,
  location     = {Shaker Heights, Ohio, USA}
}
(10)

A BibTeX entry:

@InProceedings{karp-1972,
  author       = {Karp, Richard M.},
  title        = {Reducibility among Combinatorial Problems},
  booktitle    = {Symposium on the Complexity of Computer Computations},
  year         = 1972,
  doi          = {10.1007/978-1-4684-2001-2_9}
}
(11)

Levin co-discovered NP-completeness in Soviet Russia.



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