---

NP-complete

a.k.a.

• NP-complete class
• nondeterministic polynomial-time complete class

Define

… as a complexity class with every problem \(L\) where

1. \(L\) is in NP,

   \[L \in \mathrm{NP},
   \]

2. every other problem \(L'\) in NP reduces to \(L\) in polynomial time,

   \[\forall L' \! \in \mathrm{NP}, \>\> L' \leq_P L.
   \]

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 quantitatively hardest problems in NP because:

1. By definition, all NP problems reduce to them.
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)⁵.
2. Proved and extended to 21 problems by Karp (1972) ⁶.

[Both seminal papers yielded Turing Awards.]

The SAT bootstrapping is dubbed

or just Cook’s theorem.

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

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