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*} \]

These are the *hardest* problems in NP because:

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

[Both seminal papers yielded Turing Awards.]

The SAT bootstrapping is dubbed

Cook–Levin^{11} theorem,

or just Cook’s theorem.

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} }

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} }

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.