---
title: NP-Completeness
module: Intractability
moduleNumber: 12
lessonNumber: 2
order: 1202
summary: |
  Some problems in $\mathsf{NP}$ are universally hardest: every other problem
  in $\mathsf{NP}$ reduces to them. This lesson defines $\mathsf{NP}$-hard and
  $\mathsf{NP}$-complete, states the Cook–Levin theorem that anchors the
  theory on **SAT**, walks the web of reductions that grows from it, and gives
  the four-step recipe for proving a brand-new problem $\mathsf{NP}$-complete.
topics: [NP-Completeness]
sources:
  - book: CLRS
    ref: "Ch. 34 — NP-Completeness"
  - book: Skiena
    ref: "§11 — NP-Completeness"
  - book: Erickson
    ref: "Ch. 12 — NP-Hardness"
practice:
  - title: 'Flower Planting With No Adjacent'
    slug: flower-planting-with-no-adjacent
    difficulty: Medium
  - title: 'N-Queens'
    slug: n-queens
    difficulty: Hard
  - title: 'Sudoku Solver'
    slug: sudoku-solver
    difficulty: Hard
  - title: 'Find the Shortest Superstring'
    slug: find-the-shortest-superstring
    difficulty: Hard
---

The previous lesson left us with a claim: inside $\mathsf{NP}$
there are problems that are _universally hardest_, and they decide the
$\mathsf{P}$ versus $\mathsf{NP}$ question. This lesson makes that claim
precise. We define what it means to be hardest, identify the first such problem
(**SAT**, via the Cook–Levin theorem), and then show how a single starting
problem yields many more equally hard problems through [reductions](/algorithms/intractability/p-np-reductions). Finally
we state the four-step recipe for proving a new problem
$\mathsf{NP}$-complete.

## NP-hard and NP-complete

Recall that $A \le_P B$ means "$A$ is no harder than $B$." Now imagine a
problem $B$ that _every_ problem in $\mathsf{NP}$ is no harder than. Such a $B$
is at least as hard as everything in $\mathsf{NP}$, a ceiling on the whole
class.

> **Definition ($\mathsf{NP}$-hard and $\mathsf{NP}$-complete).** A problem $B$ is $\mathsf{NP}$-hard if $A \le_P B$ for _every_ problem $A
> \in \mathsf{NP}$.
>
> A problem $B$ is $\mathsf{NP}$-complete if it is $\mathsf{NP}$-hard _and_
> $B \in \mathsf{NP}$.

The distinction matters. $\mathsf{NP}$-hardness is a pure _lower bound_: $B$ is
as hard as anything in $\mathsf{NP}$, but $B$ need not itself be in
$\mathsf{NP}$; it could be far harder, even undecidable. $\mathsf{NP}$-complete
problems are the ones that are hardest _and still belong to_ $\mathsf{NP}$:
they sit exactly at the frontier. They are the hardest
problems whose solutions we can still efficiently check.[^clrs-nphard]

$$
% caption: $\mathsf{NP}$-complete is the intersection of $\mathsf{NP}$ and
%          $\mathsf{NP}$-hard; some $\mathsf{NP}$-hard problems lie outside $\mathsf{NP}$.
\begin{tikzpicture}[font=\small]
  \definecolor{acc}{HTML}{2348F2}
  % NP ellipse (left)
  \draw[thick] (0,0) ellipse (2.5 and 1.7);
  \node[anchor=south] at (-1.0,0.95) {$\mathsf{NP}$};
  % NP-hard ellipse (right), overlapping
  \draw[thick] (3.0,0) ellipse (2.5 and 1.7);
  \node[anchor=south] at (4.0,0.95) {$\mathsf{NP}$-hard};
  % P region inside NP only
  \draw[draw=acc, fill=acc!15] (-1.5,-0.2) ellipse (0.75 and 0.5);
  \node[font=\scriptsize] at (-1.5,-0.2) {$\mathsf{P}$};
  % intersection label
  \node[align=center, font=\scriptsize, fill=acc!15, draw=acc, very thick,
        inner sep=2pt] at (1.5,0)
    {$\mathsf{NP}$-\\complete};
  % outside-NP hard example
  \node[font=\scriptsize, align=center] at (4.3,-0.55) {halting\\(undecidable)};
\end{tikzpicture}
$$

Two consequences follow.

- **All $\mathsf{NP}$-complete problems stand or fall together.** Suppose $B$ is
  $\mathsf{NP}$-complete and someone finds a polynomial-time algorithm for $B$.
  Then for _any_ $A \in \mathsf{NP}$ we have $A \le_P B$, so $A$ is solvable in
  polynomial time too, every $A$ at once. Hence
  $$ \text{any } \mathsf{NP}\text{-complete problem} \in \mathsf{P} \;\Longrightarrow\; \mathsf{P} = \mathsf{NP}. $$
  Conversely, proving _any single_ $\mathsf{NP}$-complete problem requires
  super-polynomial time would prove $\mathsf{P} \ne \mathsf{NP}$. In this sense
  the thousands of known $\mathsf{NP}$-complete problems are a single problem
  in many guises.
- **Transitivity bootstraps the class.** If $C$ is $\mathsf{NP}$-complete and we
  show $C \le_P D$ for some $D \in \mathsf{NP}$, then $D$ is
  $\mathsf{NP}$-complete too: every $A \in \mathsf{NP}$ satisfies $A \le_P C
  \le_P D$, and $\le_P$ composes. This is how _one_
  $\mathsf{NP}$-complete problem yields many.

$$
% caption: Transitivity bootstrap: every $A\in\mathsf{NP}$ already reduces to the
%          known-complete $C$; one new reduction $C\le_P D$ extends the chain, so $D$
%          inherits hardness from the whole class.
\begin{tikzpicture}[>=Stealth, font=\small,
    p/.style={draw, minimum height=9mm, minimum width=20mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  % the whole class NP fans in to C
  \node (a1) at (0,1.5) {$A_1$};
  \node (a2) at (0,0.75) {$A_2$};
  \node[font=\scriptsize] (dots) at (0,0.1) {$\vdots$};
  \node (ak) at (0,-0.6) {$A_k$};
  \node[font=\footnotesize, anchor=east] at (-0.45,0.45) {every \texttt{A in NP}};
  \node[p, draw=acc, fill=acc!15] (c) at (4.2,0.45) {$C$\\(known complete)};
  \node[p, draw=acc, very thick] (d) at (8.6,0.45) {$D$\\(new, in NP)};
  \draw[->] (a1) -- (c.165);
  \draw[->] (a2) -- (c.178);
  \draw[->] (ak) -- (c.192);
  \draw[->, acc, thick] (c) -- node[above, font=\footnotesize]{\texttt{C} $\le_P$ \texttt{D}} (d);
  % the bootstrapped chain, as a flat leader beneath the row
  \draw[acc] (-0.4,-1.15) -- (8.6,-1.15);
  \draw[acc] (-0.4,-1.05) -- (-0.4,-1.25);
  \draw[acc] (8.6,-1.05) -- (8.6,-1.25);
  \node[below, font=\scriptsize, text=acc, align=center] at (4.1,-1.25)
    {so \texttt{A} $\le_P$ \texttt{C} $\le_P$ \texttt{D} for every $A$, so $D$ is NP-complete};
\end{tikzpicture}
$$

Transitivity spreads
$\mathsf{NP}$-completeness from one problem to the next, but it presupposes we
already have a _first_ $\mathsf{NP}$-complete problem to start from. Where does
the first one come from?

## The first one: Cook–Levin

The breakthrough, proved independently by Stephen Cook (1971) and Leonid Levin,
is that a natural problem is $\mathsf{NP}$-complete _from scratch_, without
reducing from anything, by reasoning directly about computation itself.

The problem is **boolean satisfiability**, or **SAT**.

> **Definition (SAT).** Given a boolean formula $\varphi$ over variables $x_1, \dots, x_n$
> using $\wedge$ (and), $\vee$ (or), and $\neg$ (not), is there an assignment of
> **true**/**false** to the variables that makes $\varphi$ evaluate to **true**?

> **Theorem (Cook–Levin).** **SAT** is $\mathsf{NP}$-complete.

> **Proof sketch.** That **SAT** is in $\mathsf{NP}$ is easy: a satisfying
> assignment is a certificate, and evaluating $\varphi$ on it takes linear time.
> The deep half is $\mathsf{NP}$-hardness: showing that _every_ $A \in
> \mathsf{NP}$ reduces to **SAT**, by encoding _computation as logic_. Any $A \in
> \mathsf{NP}$ has a polynomial-time verifier $V$. For an input $x$, the question
> "does some certificate make $V$ accept $x$?" is just a restatement of "is $A$'s
> answer **yes**?" Cook and Levin build, in polynomial time, a boolean formula
> $\varphi_x$ whose variables describe the verifier's entire step-by-step
> execution, with clauses that force the variables to obey the machine's rules.
> Then $\varphi_x$ is satisfiable **if and only if** some certificate makes $V$
> accept — the clauses are engineered so that a satisfying assignment is sound
> (it can only encode a genuinely accepting run) and complete (every accepting
> run yields one). So deciding **SAT** on $\varphi_x$ decides $A$ on $x$. Because
> this works for an _arbitrary_ problem in $\mathsf{NP}$, **SAT** is
> $\mathsf{NP}$-hard.[^clrs-cook] $\qed$

$$
% caption: Cook–Levin encodes a verifier's whole computation on $(x,y)$ as one formula
%          $F_x$, satisfiable iff some $y$ accepts.
\begin{tikzpicture}[>=Stealth, font=\small,
    box/.style={draw, rectangle, minimum height=13mm,
                minimum width=22mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (x)   at (0,0)    {input $x$\\(f\/ixed)};
  \node[box] (v)   at (3.6,0)  {veri\/f\/ier $V$\\runs poly steps};
  \node[box, draw=acc] (phi) at (8.0,0) {formula $F_x$\\(built in poly time)};
  \node[box] (sat) at (12.2,0) {SAT\\on $F_x$};
  \draw[->] (x) -- (v);
  \draw[->] (v) -- (phi);
  \draw[->, acc] (phi) -- (sat);
  % edge label lifted clear of both boxes, tied to the arrow by a short leader
  \node[font=\scriptsize, text=red!75!black] (enc) at (5.8,1.15) {encode as logic};
  \draw[->, red!75!black, shorten >=1pt] (enc.south) -- (5.8,0.16);
  \node[anchor=north, align=center, font=\scriptsize] at (3.6,-0.75)
    {variables = \texttt{tape}\\+ state at each step};
  \node[anchor=north, align=center, font=\scriptsize] at (8.0,-0.75)
    {clauses force\\legal transitions};
  \node[anchor=north, align=center, font=\scriptsize] at (12.2,-0.75)
    {satis\/f\/iable exactly when\\some $y$ accepts};
\end{tikzpicture}
$$

::impl{algo="sat"}

With one $\mathsf{NP}$-complete problem in hand, transitivity takes
over.

## The reduction web

Karp's 1972 paper reduced **SAT** to twenty-one other problems,
showing them all $\mathsf{NP}$-complete and launching the field.[^skiena-web] A convenient
intermediate is **3-SAT**, the special case of **SAT** in which the formula is in
_conjunctive normal form_ with exactly three literals per clause, a big AND of
small ORs such as $(x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee x_2 \vee
x_4)$. One can show $\textbf{SAT} \le_P \textbf{3-SAT}$, so **3-SAT** is itself
$\mathsf{NP}$-complete, and its rigid structure makes it the favorite
starting point for further reductions.

The $\textbf{SAT} \le_P \textbf{3-SAT}$ reduction is a small gadget worth seeing,
because it shows how a clause of the _wrong_ width is padded or split to exactly
three literals using fresh variables. A clause with one literal $(a)$ becomes
$(a \vee y_1 \vee y_2) \wedge (a \vee \neg y_1 \vee y_2) \wedge (a \vee y_1 \vee \neg y_2) \wedge (a \vee \neg y_1 \vee \neg y_2)$
with new variables $y_1, y_2$: the four clauses together force $a$ true regardless
of $y_1, y_2$. A long clause $(a_1 \vee a_2 \vee a_3 \vee a_4 \vee a_5)$ is
_chained_ with fresh variables $z_i$ into
$(a_1 \vee a_2 \vee z_1) \wedge (\neg z_1 \vee a_3 \vee z_2) \wedge (\neg z_2 \vee a_4 \vee a_5)$:
a satisfying assignment of the original picks some true $a_j$, and the $z_i$ can be
set to carry the "still unsatisfied" signal down the chain until that $a_j$
discharges it. Each new clause has exactly three literals, the blow-up is linear,
and satisfiability is preserved in both directions — a clean polynomial reduction.

From **3-SAT** the web branches out. A small portion:

$$
% caption: Reduction web of NP-complete problems branching out from SAT and 3-SAT.
\begin{tikzpicture}[>=Stealth,
    p/.style={draw, minimum height=10mm, inner sep=4pt}]
  \node (sat)  [p] at (0,0)      {\texttt{SAT}};
  \node (3sat) [p] at (2.7,0)    {\texttt{3-SAT}};
  \node (is)   [p] at (5.9,1.4)  {\texttt{Independent-Set}};
  \node (ss)   [p] at (5.9,-1.4) {\texttt{Subset-Sum}};
  \node (clq)  [p] at (9.9,2.6)  {\texttt{Clique}};
  \node (vc)   [p] at (9.9,1.4)  {\texttt{Vertex-Cover}};
  \node (ham)  [p] at (9.9,0.2)  {\texttt{Ham-Cycle}};
  \draw[->] (sat) -- (3sat);
  \draw[->] (3sat) -- (is);
  \draw[->] (3sat) -- (ss);
  \draw[->] (is) -- (clq);
  \draw[->] (is) -- (vc);
  \draw[->] (vc) -- (ham);
\end{tikzpicture}
$$

Every arrow $X \to Y$ is a reduction $X \le_P Y$; following arrows back to
**SAT** certifies each box as $\mathsf{NP}$-complete. (The arrows above record
one _route_ to each result, not the only one; many of these problems also
reduce to each other directly, as we saw with $\textsc{Independent-Set}$ and
**Clique** last lesson.)

### A worked reduction: 3-SAT to Independent-Set

Let us actually build one arrow, the classic $\textbf{3-SAT} \le_P
\textbf{Independent-Set}$. We are given a 3-CNF formula $\varphi$ with $m$
clauses and must produce a graph $G$ and integer $k$ such that $G$ has an
[independent set](/algorithms/graphs/representations-and-traversal) of size $k$ exactly when $\varphi$ is satisfiable.

**The construction.** For each clause, create a _triangle_ of three vertices,
one per literal. So clause $(x_1 \vee \neg x_2 \vee x_3)$ becomes three
mutually-connected vertices labeled $x_1$, $\neg x_2$, $x_3$. Then add a
**conflict edge** between any two vertices in different triangles that hold
_contradictory_ literals: one labeled $x_i$ and another labeled $\neg x_i$.
Finally set $k = m$, the number of clauses. This is clearly polynomial: $3m$
vertices and at most $O(m^2)$ edges. The construction is correct in both
directions.

> **Proof (correctness).** The two directions of the biconditional are the
> [soundness](/algorithms/foundations/what-is-an-algorithm) and
> [completeness](/algorithms/foundations/what-is-an-algorithm) of the reduction.
> _Soundness_ ($G$ has the set $\Rightarrow \varphi$ satisfiable): an independent
> set may pick _at most one_ vertex from each triangle (the three are mutually
> adjacent), so an independent set of size $k = m$ must pick _exactly one_
> literal from every clause. The conflict edges forbid choosing both $x_i$ and
> $\neg x_i$ anywhere, so the chosen literals are mutually consistent — they
> describe a partial truth assignment. Setting each chosen literal **true**
> satisfies one literal in every clause, hence satisfies $\varphi$; the
> **yes** for $G$ never arises from an unsatisfiable formula. _Completeness_
> ($\varphi$ satisfiable $\Rightarrow G$ has the set): a satisfying assignment
> picks, from each clause, one true literal; those $m$ vertices form an
> independent set, since two true literals can never be a variable and its
> negation, so every satisfiable formula does map to a **yes**. Therefore
> $$\varphi \text{ is satisfiable} \iff G \text{ has an independent set of size } m,$$
> which is what a valid reduction requires.[^erickson-gadget] $\qed$

$$
% caption: Clause triangles with dashed conflict edges for the 3-SAT to Independent-Set
%          reduction.
\begin{tikzpicture}[>=Stealth,
    v/.style={draw, circle, inner sep=1.5pt, minimum size=7mm, font=\small}]
  % clause 1 triangle
  \node[v] (a1) at (0,1.2) {$x_1$};
  \node[v] (a2) at (-0.8,0) {$\overline{x}_2$};
  \node[v] (a3) at (0.8,0) {$x_3$};
  \draw (a1)--(a2)--(a3)--(a1);
  % clause 2 triangle
  \node[v] (b1) at (4,1.2) {$\overline{x}_1$};
  \node[v] (b2) at (3.2,0) {$x_2$};
  \node[v] (b3) at (4.8,0) {$x_4$};
  \draw (b1)--(b2)--(b3)--(b1);
  % conflict edges
  \draw[dashed] (a1) to[bend left=10] (b1);
  \draw[dashed] (a2) to[bend right=18] (b2);
  \node[font=\small] at (2,1.9) {con\/f\/lict};
\end{tikzpicture}
$$

Solid edges are the per-clause triangles; dashed edges connect contradictory
literals ($x_1$ vs. $\neg x_1$, and $\neg x_2$ vs. $x_2$). Picking one
non-conflicting vertex per triangle amounts to a consistent satisfying choice.

**A fully worked instance.** Take the concrete formula
$$\varphi = (x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee x_2 \vee x_4).$$
It has $m = 2$ clauses, so the construction builds $3m = 6$ vertices in two
triangles and sets $k = 2$. The conflict edges join $x_1$ (clause 1) to
$\neg x_1$ (clause 2), and $\neg x_2$ (clause 1) to $x_2$ (clause 2) — the two
variable/negation collisions across the triangles. Now find a size-$2$ independent
set: pick $x_1$ from the first triangle and $x_2$ from the second. These two are
_not_ joined by a conflict edge (the conflicts are $x_1$–$\neg x_1$ and
$\neg x_2$–$x_2$, neither of which is the pair $\{x_1, x_2\}$), and they sit in
different triangles, so the two vertices are non-adjacent — an independent set of
size $2 = k$. Reading the chosen literals back as an assignment gives
$x_1 = \textbf{true}$, $x_2 = \textbf{true}$ (and $x_3, x_4$ free): the first
clause is satisfied by $x_1$, the second by $x_2$, so $\varphi$ is satisfiable. The
reduction turned a logic question into a graph question and back, exactly as the
correctness proof requires.

$$
% caption: Choosing $\{x_1, x_2\}$ — one vertex per triangle, no conflict edge between
%          them — is a size-$2$ independent set, i.e. a satisfying assignment.
\begin{tikzpicture}[>=Stealth, font=\small,
    v/.style={draw, circle, inner sep=1.5pt, minimum size=7mm},
    sel/.style={draw=acc, circle, fill=acc!15, very thick, inner sep=1.5pt, minimum size=7mm}]
  \definecolor{acc}{HTML}{2348F2}
  % clause 1 triangle: pick x_1
  \node[sel] (a1) at (0,1.2) {$x_1$};
  \node[v] (a2) at (-0.8,0) {$\overline{x}_2$};
  \node[v] (a3) at (0.8,0) {$x_3$};
  \draw (a1)--(a2)--(a3)--(a1);
  % clause 2 triangle: pick x_2
  \node[v] (b1) at (4,1.2) {$\overline{x}_1$};
  \node[sel] (b2) at (3.2,0) {$x_2$};
  \node[v] (b3) at (4.8,0) {$x_4$};
  \draw (b1)--(b2)--(b3)--(b1);
  % conflict edges (dashed)
  \draw[dashed] (a1) to[bend left=10] (b1);
  \draw[dashed] (a2) to[bend right=18] (b2);
  \node[font=\scriptsize] at (2,1.9) {con\/f\/lict};
  \node[anchor=north, align=center, font=\scriptsize, text=acc] at (2,-0.5)
    {chosen \texttt{x1,x2}: independent, so $x_1 = x_2 =$ true satis\/f\/ies the formula};
\end{tikzpicture}
$$

::impl{algo="three_sat_to_independent_set"}

## The recipe: proving a new problem NP-complete

Once a stockpile of $\mathsf{NP}$-complete problems exists, classifying a
_new_ problem $X$ follows a fixed procedure. To prove **$X$ is
$\mathsf{NP}$-complete**, carry out four steps.

1. **Show $X \in \mathsf{NP}$.** Describe a polynomial-size certificate for
   **yes**-instances and argue it can be checked in polynomial time. This is
   usually the easy step, but skipping it is a real error: an
   $\mathsf{NP}$-_hard_ problem outside $\mathsf{NP}$ is hard but not
   _complete_.
2. **Choose a known $\mathsf{NP}$-complete problem $Y$** to reduce _from_.
   Pick one whose structure resembles $X$ — **3-SAT** for logical or
   gadget-style constraints, $\textsc{Vertex-Cover}$ or $\textsc{Independent-Set}$ for graph
   selection, $\textsc{Subset-Sum}$ or $\textsc{Partition}$ for numeric targets,
   $\textsc{Hamiltonian-Cycle}$ for routing.
3. **Give a polynomial-time reduction $Y \le_P X$.** Construct, from an
   arbitrary instance of $Y$, an instance of $X$. This is the creative step of
   the proof. _Mind the direction:_ you transform $Y$'s instance into $X$'s, so
   that solving $X$ would solve $Y$. Reducing the wrong way ($X \le_P Y$) proves
   nothing about $X$'s hardness.
4. **Prove the reduction correct.** Establish the _if and only if_, which is
   exactly the **completeness** and **soundness** of the map. _Completeness:_ a
   **yes**-instance of $Y$ maps to a **yes**-instance of $X$ (no true case
   lost). _Soundness:_ conversely every **yes**-instance of $X$ comes only from
   a **yes**-instance of $Y$ (no false **yes** invented). Both directions are
   mandatory; dropping completeness lets false negatives slip through, dropping
   soundness lets false positives.

Steps 1 and 2 are bookkeeping; steps 3 and 4 are the substance.[^clrs-recipe] The
worked reduction above is this recipe applied with $Y = \textbf{3-SAT}$
and $X = \textbf{Independent-Set}$: the triangles-and-conflicts gadget is step
3, and the two-direction argument is step 4.

> **Remark (The direction, once more).** To prove $X$ hard, reduce a _hard_ problem
> **into** $X$. The mantra: _reduce from known-hard, to the new problem._ If you
> ever find yourself building an instance of a _known_ problem out of $X$, you
> have the arrow backwards.

## The tractability boundary and what "hard" costs

The reduction web draws a line, and the sharpest way to see where it falls is a
pair of problems that look nearly identical yet land on opposite sides. **2-SAT**,
the restriction of **SAT** to two literals per clause, is solvable in _linear_
time: build the implication graph (each clause $(a \vee b)$ becomes
$\neg a \Rightarrow b$ and $\neg b \Rightarrow a$), and the formula is satisfiable
exactly when no variable $x$ and its negation $\neg x$ share a strongly connected
component — one pass of the [SCC algorithm](/algorithms/graphs/topological-sort-and-scc),
worked out in full in the [2-SAT lesson](/algorithms/graphs/two-sat).
Add one literal per clause and **3-SAT** becomes $\mathsf{NP}$-complete. The jump
from $2$ to $3$ is the whole story, and it is not an accident: Schaefer's dichotomy
theorem (1978) proves that every boolean constraint-satisfaction problem is either
in $\mathsf{P}$ or $\mathsf{NP}$-complete, with _nothing_ in between, and it names
the exact conditions that put a problem in $\mathsf{P}$.[^schaefer]

Trace the linear-time test on $\psi = (x_1 \vee x_2) \wedge (\neg x_1 \vee x_2) \wedge (\neg x_2 \vee x_3)$.
Each clause $(a \vee b)$ contributes both implications $\neg a \Rightarrow b$ and
$\neg b \Rightarrow a$, giving six directed edges: from the first clause,
$\neg x_1 \Rightarrow x_2$ and $\neg x_2 \Rightarrow x_1$; from the second,
$x_1 \Rightarrow x_2$ and $\neg x_2 \Rightarrow \neg x_1$; from the third,
$x_2 \Rightarrow x_3$ and $\neg x_3 \Rightarrow \neg x_2$. Every path in this graph
forces truth values: following the edges out of $x_1$, we reach $x_2$ then $x_3$,
and no path ever leads from a literal to its own negation, so no variable shares an
SCC with its complement. The formula is satisfiable — indeed $x_1 = x_2 = x_3 = \textbf{true}$
works. Had we instead added the clauses $(\neg x_2) \wedge (x_2)$, the graph would
route $x_2 \Rightarrow \neg x_2 \Rightarrow x_2$, collapsing $x_2$ and $\neg x_2$
into one SCC and certifying unsatisfiability — all detected by a single SCC pass,
never any search.

$$
% caption: A knife-edge boundary: 2-SAT is linear-time, 3-SAT is NP-complete; Schaefer's
%          theorem says CSPs are always one or the other, never in between.
\begin{tikzpicture}[>=Stealth, font=\footnotesize,
    b/.style={draw, minimum height=8mm, minimum width=26mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \draw[black, thick, dashed] (2.3,-1.3) -- (2.3,1.5);
  \node[b, draw=acc, fill=acc!12] (two) at (0,0) {2-SAT\\linear time};
  \node[b] (three) at (4.6,0) {3-SAT\\NP-complete};
  \node[black] at (0,1.2) {tractable};
  \node[black] at (4.6,1.2) {intractable};
  \node[black, align=center] at (2.3,-1.75) {Schaefer: P or\\NP-complete, no gap};
\end{tikzpicture}
$$

Two deeper results sharpen "how hard." The **Exponential Time Hypothesis** (ETH),
conjectured by Impagliazzo and Paturi, says 3-SAT cannot be solved in $2^{o(n)}$
time — not merely that it is not polynomial, but that even sub-exponential time is
out of reach.[^eth] ETH is now the standard tool for proving that specific
problems need $2^{\Omega(n)}$ or $n^{\Omega(k)}$ time, giving fine-grained lower
bounds far below the crude $\mathsf{P}$-versus-$\mathsf{NP}$ divide. And the **PCP
theorem** (Arora–Safra and Arora–Lund–Motwani–Sudan–Szegedy, 1998) recharacterizes
$\mathsf{NP}$ so strongly that it makes _approximation_ itself hard: for many
problems, even finding a solution within some constant factor of optimal is
$\mathsf{NP}$-complete.[^pcp] That result leads to the
[approximation lesson](/algorithms/intractability/approximation-algorithms), where
we ask not "can we solve it exactly" but "how close can we provably get."

## Takeaways

- $X$ is **$\mathsf{NP}$-hard** if every problem in $\mathsf{NP}$ reduces to it
  (a lower bound); it is **$\mathsf{NP}$-complete** if it is also _in_
  $\mathsf{NP}$, hardest among the efficiently-checkable problems.
- All $\mathsf{NP}$-complete problems share one fate: a polynomial-time
  algorithm for **any** of them would prove $\mathsf{P} = \mathsf{NP}$ and solve
  them all.
- **Cook–Levin** anchors the theory: **SAT** is $\mathsf{NP}$-complete, proved
  directly by encoding any verifier's computation as a boolean formula. From it,
  **3-SAT** and a vast **reduction web** follow by transitivity.
- The $\textbf{3-SAT} \le_P \textbf{Independent-Set}$ reduction (a triangle per
  clause plus conflict edges, with $k = m$) is the model gadget reduction.
- To prove a new problem $\mathsf{NP}$-complete: **(1)** show membership in
  $\mathsf{NP}$, **(2)** pick a known $\mathsf{NP}$-complete $Y$, **(3)** reduce
  $Y \le_P X$ in polynomial time, **(4)** prove the equivalence both ways,
  always reducing _from_ the hard problem.

[^clrs-nphard]: **CLRS**, Ch. 34 — NP-Completeness (§34.1): the definitions of $\mathsf{NP}$-hard (a lower bound) and $\mathsf{NP}$-complete (hard and in $\mathsf{NP}$).
[^clrs-cook]: **CLRS**, Ch. 34 — NP-Completeness (§34.3): the Cook–Levin theorem that **SAT** is $\mathsf{NP}$-complete, proved by encoding a verifier's computation as a boolean formula.
[^skiena-web]: **Skiena**, §11 — NP-Completeness: Karp's 1972 reductions and the web of $\mathsf{NP}$-complete problems growing from satisfiability.
[^erickson-gadget]: **Erickson**, Ch. 12 — NP-Hardness: the gadget reduction $\textbf{3-SAT} \le_P \textbf{Independent-Set}$ (clause triangles plus conflict edges, $k = m$).
[^clrs-recipe]: **CLRS**, Ch. 34 — NP-Completeness (§34.4): the standard four-step recipe for proving a new problem $\mathsf{NP}$-complete.
[^schaefer]: Thomas J. Schaefer, "The Complexity of Satisfiability Problems," _STOC_ 1978 — every boolean CSP is either in $\mathsf{P}$ or $\mathsf{NP}$-complete, with the exact tractable cases characterized (2-SAT, Horn-SAT, affine, and duals).
[^eth]: Russell Impagliazzo and Ramamohan Paturi, "On the Complexity of $k$-SAT," _Journal of Computer and System Sciences_ 62(2), 2001 — the Exponential Time Hypothesis, that 3-SAT has no $2^{o(n)}$ algorithm.
[^pcp]: Sanjeev Arora and Shmuel Safra, "Probabilistic Checking of Proofs," and Arora, Lund, Motwani, Sudan, Szegedy, "Proof Verification and the Hardness of Approximation Problems," _Journal of the ACM_, 1998 — the PCP theorem and inapproximability.