title: "NP-Completeness"

NP-Completeness

Definition. A language $B$ is NP-hard if $A \leq_{\mathsf{P}} B$ for every $A \in \mathsf{NP}$, and NP-complete if in addition $B \in \mathsf{NP}$.

An NP-complete problem is a hardest problem in $\mathsf{NP}$: if any one of them is in $\mathsf{P}$ then $\mathsf{P} = \mathsf{NP}$, so they stand or fall together. $SAT$ was the first, by the Cook-Levin theorem, which reduces every language in $\mathsf{NP}$ to it by encoding a machine's computation as a table and asserting its validity with a formula. Every later proof reuses that: to show $C$ is NP-complete, show $C \in \mathsf{NP}$ with a certificate and reduce one known NP-complete problem to it, as in Lecture 11. NP-hardness alone does not imply membership in $\mathsf{NP}$, and an NP-completeness proof shows no algorithm is impossible, only that a fast one would settle P versus NP.