---

NP-complete

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

• Synonyms
• Intuition
• History