NP-complete
A complexity class with every problem \(L\) where
- \(L\) is in NP, \[L \in \mathrm{NP},\]
- 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*}