A complexity class of every decision problem that is
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:
[Both seminal papers yielded Turing Awards.]
The SAT bootstrapping is dubbed
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.