---
title: P, NP, and Reductions
module: Intractability
moduleNumber: 12
lessonNumber: 1
order: 1201
summary: |
  Most problems we have met so far have fast algorithms. A vast and important
  family seemingly does not. This lesson builds the vocabulary for that
  divide: decision problems, the class $\mathsf{P}$ of problems we can solve
  quickly, the class $\mathsf{NP}$ of problems whose solutions we can _check_
  quickly, and polynomial-time reductions, the tool that lets us compare the
  difficulty of two problems without solving either.
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: 'Partition Equal Subset Sum'
    slug: partition-equal-subset-sum
    difficulty: Medium
  - title: 'Partition to K Equal Sum Subsets'
    slug: partition-to-k-equal-sum-subsets
    difficulty: Medium
  - title: 'Satisfiability of Equality Equations'
    slug: satisfiability-of-equality-equations
    difficulty: Medium
---

Nearly every problem so far in this course has a fast algorithm: sorting in
$O(n\log n)$, shortest paths in near-linear time, spanning trees almost for
free. It is tempting to believe that every problem yields to a clever enough
algorithm, but this is not so. There is a large, practical family of
problems (scheduling, routing, packing, constraint satisfaction) for which,
after more than half a century of effort, _nobody_ has found an algorithm
that is fast on every instance, and for which we have strong reasons to
suspect none exists.

The theory of **intractability** is how we make that suspicion precise. Its
central insight, due to Cook, Levin, and Karp, is that thousands of
these problems are equivalent to one another. Solve any
one of them quickly and you solve them all; prove any one of them
hard and you have proved them all hard. This lesson assembles the three ideas
needed to state that claim: decision problems, the classes $\mathsf{P}$ and
$\mathsf{NP}$, and reductions.

## Decision problems

To classify difficulty cleanly we restrict attention to problems with a
yes-or-no answer. A **decision problem** asks, of each input, a single
question whose answer is **yes** or **no**.

> **Definition (Decision problem).** A decision problem is a function from inputs (encoded as finite strings)
> to $\{\text{yes}, \text{no}\}$. Equivalently, it is the _language_ $L$ of all
> inputs whose answer is **yes**; "solving" the problem means deciding, for a
> given string $x$, whether $x \in L$.

This seems like a severe restriction; surely we usually want to _find_ a
shortest tour, not merely learn whether a short one exists. But the two are
rarely far apart. The optimization problem "find the cheapest tour" has a
decision twin: "is there a tour of cost at most $k$?" If we can answer the
decision question quickly for every $k$, a binary search over $k$ determines
the optimal cost, and a little more work recovers the tour itself. Decision
problems lose almost nothing and gain a clean theory, so they are the objects
we classify.

$$
% caption: An optimization problem reduces to its decision twin by binary search over the
%          threshold $k$.
\begin{tikzpicture}[>=Stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->, thick] (0,0) -- (10,0);
  \node[anchor=north] at (0,-0.15) {$\text{lo}$};
  \node[anchor=north] at (10,-0.15) {$\text{hi}$};
  \foreach \x in {2.2, 4.0} {
    \node[circle, draw, fill=red!18, inner sep=1.6pt] at (\x,0) {};
  }
  \foreach \x in {6.4, 8.2} {
    \node[circle, draw=acc, fill=acc!15, inner sep=1.6pt] at (\x,0) {};
  }
  \node[circle, draw, fill=acc!15, draw=acc, very thick, inner sep=1.6pt] (opt) at (5.2,0) {};
  \node[anchor=south, font=\scriptsize] at (2.2,0.12) {no};
  \node[anchor=south, font=\scriptsize] at (4.0,0.12) {no};
  \node[anchor=west, font=\footnotesize, text=acc, fill=white, inner sep=1pt] at (5.45,0.12) {\texttt{OPT}};
  \node[anchor=south, font=\scriptsize] at (6.4,0.12) {yes};
  \node[anchor=south, font=\scriptsize] at (8.2,0.12) {yes};
  \node[anchor=north, align=center, font=\scriptsize] at (5.2,-0.55)
    {threshold where answer to\\"cost at most k?" changes};
  \draw[->, acc] (4.0,0.7) to[bend right=20] (5.2,0.32);
  \draw[->, acc] (6.4,0.7) to[bend left=20] (5.2,0.32);
  \node[anchor=south, font=\scriptsize, text=acc] at (5.2,0.78) {binary search};
\end{tikzpicture}
$$

::impl{algo="optimization_to_decision"}

A word on **encoding** and **size**. An input is a string of bits; the _size_
of an instance is the length of that string. We always assume a "reasonable"
encoding (integers in binary, graphs as adjacency lists) because an
artificially bloated encoding (say, integers in unary) could make a slow
algorithm look fast. With reasonable encodings fixed, ["polynomial in the input
size"](/algorithms/foundations/asymptotic-analysis) is a stable, machine-independent notion.

## The class P

Some decision problems have algorithms whose running time is bounded by a
polynomial in the input size. These are the problems we regard as _tractable_.

> **Definition (The class $\mathsf{P}$).** $\mathsf{P}$ is the class of decision problems solvable by an algorithm that
> runs in time $O(n^k)$ for some constant $k$, where $n$ is the input size.

Why polynomial, and not, say, "$n^2$ or better"? Because polynomials are
**closed** under the operations we constantly perform: addition,
multiplication, and especially _composition_. If a polynomial-time algorithm
calls a polynomial-time subroutine a polynomial number of times, the whole
thing is still polynomial. This closure is what makes $\mathsf{P}$ stable: it
does not depend on the particular machine model, the programming language, or
whether we count $n^2$ as "fast." Everything we have called efficient so far
(sorting, shortest paths, matching, linear programming) lives in $\mathsf{P}$.
The class is our formal stand-in for "feasible."[^clrs-p]

## The class NP

Now consider a problem like **Hamiltonian Cycle**: given a graph $G$, is there
a cycle that visits every vertex exactly once? We know of no polynomial-time
algorithm to _decide_ this. But notice an asymmetry. If a benevolent oracle
hands us a cycle and claims it is Hamiltonian, we can _check_ the claim in
linear time: walk the cycle, confirm it visits each vertex once and uses real
edges. Finding the cycle seems hard; **verifying** a proposed cycle is easy.

This is the defining feature of the class $\mathsf{NP}$: a problem is in
$\mathsf{NP}$ if every **yes**-instance has a short proof, a **certificate**,
that can be checked quickly.

> **Definition (The class $\mathsf{NP}$).** $\mathsf{NP}$ is the class of decision problems for which there exists a
> polynomial-time **verifier** $V$ with the following property. For every input
> $x$:
>
> - if the answer is **yes**, then there exists a certificate $y$ of length
>   polynomial in $|x|$ such that $V(x, y)$ accepts;
> - if the answer is **no**, then for _every_ string $y$, $V(x, y)$ rejects.

The two bullets restate the [completeness](/algorithms/foundations/what-is-an-algorithm)
and [soundness](/algorithms/foundations/what-is-an-algorithm) of the verifier,
read as a decision procedure for "does $x$ have an accepting certificate?" The
first says $V$ is **complete**: every genuine **yes** is witnessed by _some_
certificate it accepts (no false negatives). The second says $V$ is **sound**:
no certificate can fool it into accepting a **no**-instance (no false
positives). A verifier missing either guarantee fails to define the language.

The name $\mathsf{NP}$ stands for **nondeterministic polynomial time**: one can
equivalently picture a machine that _guesses_ the certificate $y$ and then
verifies it. The verifier definition avoids speaking of magical guessing; it
asks only that correct **yes**-answers come with checkable evidence.[^clrs-np]

Three points deserve emphasis.

- The certificate must be **short** (polynomial length) and the check must be
  **fast** (polynomial time). For Hamiltonian Cycle the certificate is the
  cycle; for **SAT** (is a boolean formula satisfiable?) it is a satisfying
  assignment; for $\textsc{Subset-Sum}$ it is the subset that hits the target.
- The asymmetry between **yes** and **no** is real. $\mathsf{NP}$ guarantees a
  certificate only for **yes**-instances. The problem of certifying a **no**
  ("there is _no_ Hamiltonian cycle") need not be in $\mathsf{NP}$; that
  belongs to a companion class, $\mathsf{co\text{-}NP}$.
- Every problem in $\mathsf{P}$ is in $\mathsf{NP}$. If we can _solve_ a problem
  in polynomial time, we can ignore any offered certificate and just decide the
  answer directly; an empty certificate suffices. So $\mathsf{P} \subseteq
  \mathsf{NP}$.

$$
% caption: A verifier $V$ accepts $(x,y)$ when the certificate $y$ proves $x$ is a
%          yes-instance; no $y$ works otherwise.
\begin{tikzpicture}[>=Stealth, font=\small,
    box/.style={draw, rectangle, minimum height=12mm,
                minimum width=20mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node (x) at (0,1.2) {input $x$};
  \node (y) at (0,-0.6) {certi\/f\/icate $y$};
  \node[box] (v) at (3.6,0.3) {veri\/f\/ier $V$\\poly-time};
  \node[box, draw=acc, align=center] (out) at (8.4,1.1)
    {some $y$ accepts\\so {\color{acc}yes}};
  \node[box, draw=red!75!black, align=center] (no) at (8.4,-0.7)
    {\emph{every} $y$ rejects\\so {\color{red!75!black}no}};
  \draw[->] (x) -- (v.160);
  \draw[->] (y) -- (v.200);
  \draw[->, acc] (v.20) -- (out);
  \draw[->, red!75!black] (v.340) -- (no);
  \node[anchor=north, font=\scriptsize] at (3.6,-0.5)
    {len($y$) = poly(len($x$))};
\end{tikzpicture}
$$

::impl{algo="np_verifiers"}

## Reductions: comparing difficulty

We want to say "problem $B$ is at least as hard as problem $A$" without knowing
how hard either one actually is. The device that makes this possible is a
**reduction**: a way to convert any instance of $A$ into an instance of $B$
that has the same answer, so that an algorithm for $B$ becomes an algorithm for
$A$.

> **Definition (Polynomial-time reduction).** Let $A$ and $B$ be decision problems. A polynomial-time reduction from
> $A$ to $B$, written $A \le_P B$, is a function $f$ computable in polynomial
> time such that for every input $x$,
> $$ x \text{ is a yes-instance of } A \iff f(x) \text{ is a yes-instance of } B. $$

That biconditional is the core of every reduction proof, and it splits into the
same two obligations we ask of any decision procedure. The forward direction
($\Rightarrow$) is **completeness**: every **yes**-instance of $A$ maps to a
**yes**-instance of $B$, so no true case is lost in translation. The backward
direction ($\Leftarrow$) is **soundness**: a **yes** out of $B$ can only have
come from a **yes** of $A$, equivalently **no**-instances map to
**no**-instances, so the reduction never manufactures a false **yes**. Proving a
reduction correct _always_ means discharging these two directions, and we will
name them as such throughout. Read $A \le_P B$ as "$A$ is no
harder than $B$."[^clrs-reduce] Picture this as a
**transform–solve–transform pipeline**: take the input, _transform_ it into an
input for the other problem, hand that to a _solver_ for $B$, then _transform_
the solver's output back into an answer for $A$. The solver for $B$ is used as a
black-box subroutine, and we never look inside it.

$$
% caption: Transform-solve-transform pipeline turning a solver for $B$ into a solver for
%          $A$.
\begin{tikzpicture}[
    box/.style={draw, rectangle, minimum height=14mm,
                minimum width=26mm, font=\small, align=center},
    >=Stealth]
  % dashed enclosing box (the assembled solver for A), drawn first
  \draw[dashed] (-0.5,-1.0) rectangle (12.5,1.6);
  \node[font=\small] at (6.0,-1.4) {a solver for $A$};
  % pipeline of fixed-coordinate boxes
  \node[font=\small]            (x)   at (-2.0,0.3) {input $x$ for $A$};
  \node[box]                    (tin) at ( 1.7,0.3) {transform\\input};
  \node[box]                    (solv)at ( 6.0,0.3) {solver\\for $B$};
  \node[box]                    (tout)at (10.3,0.3) {transform\\output};
  \node[font=\small]            (ans) at (13.8,0.3) {answer for $A$};
  \draw[->] (x)    -- (tin);
  \draw[->] (tin)  -- node[above,font=\scriptsize]{$f(x)$} (solv);
  \draw[->] (solv) -- (tout);
  \draw[->] (tout) -- (ans);
\end{tikzpicture}
$$

The dashed box is the point: a fast solver for $B$, wrapped in the fast
transformers on either side, _is_ a fast solver for $A$. For a **decision**
problem the right-hand transformer is trivial (pass the yes/no answer through
unchanged), and the pipeline collapses to the textbook definition above: apply
$f$, ask the $B$-question, report the answer. For a **search** problem (the
warm-up below) the right-hand transformer does real work, turning $B$'s witness
back into a witness for $A$. Either way, the diagram encodes the two ways every
reduction is used, which are mirror images of each other.

- **Upper bound (tractability flows forward).** If $A \le_P B$ and $B \in
  \mathsf{P}$, then $A \in \mathsf{P}$. Tractability of the harder problem
  extends to the easier one: run $f$, then the fast solver for $B$; the
  composition of two polynomials is a polynomial.
- **Lower bound (hardness flows backward).** If $A \le_P B$ and $A$ is _known
  to be hard_, then $B$ is hard too. For if $B$ had a fast algorithm, the
  pipeline above would give $A$ one as well, a contradiction.

The second direction is the basis of the theory of intractability. To show a
new problem $B$ is hard, we reduce a known-hard problem $A$ _to_ it. The
direction is a notorious source of error: we reduce **from** the hard problem
**to** the new one. Getting the arrow backwards proves nothing.

$$
% caption: The two uses of $A \le_P B$: tractability flows forward, hardness flows
%          backward.
\begin{tikzpicture}[>=Stealth, font=\small,
    p/.style={draw, minimum height=9mm, minimum width=18mm}]
  \definecolor{acc}{HTML}{2348F2}
  \node[p] (a) at (0,0) {$A$ (known hard)};
  \node[p] (b) at (6.4,0) {$B$ (new)};
  \draw[->, thick] (a) -- node[above, font=\scriptsize]{$f$ maps instances} (b);
  \node[font=\footnotesize, anchor=south] at (3.2,0.55) {\texttt{A} $\le_P$ \texttt{B}};
  % forward: good news
  \draw[->, acc, thick] (5.6,-1.1) -- node[below, font=\footnotesize, text=acc]{\texttt{B in P}\, so \,\texttt{A in P}} (0.8,-1.1);
  % backward: bad news
  \draw[->, red!75!black, thick] (0.8,-1.9) -- node[below, font=\scriptsize, text=red!75!black]{$A$ hard, so $B$ hard} (5.6,-1.9);
  \node[font=\scriptsize, text=acc, anchor=east] at (-0.2,-1.1) {tractabilit\/y};
  \node[font=\scriptsize, text=red!75!black, anchor=west] at (6.6,-1.9) {hardness};
\end{tikzpicture}
$$

Two structural facts make $\le_P$ behave like an ordering of difficulty.

- **Reflexivity is trivial**; the load-bearing fact is that **transitivity holds**: if $A
  \le_P B$ and $B \le_P C$, then $A \le_P C$, since we just compose the two
  translators, and a polynomial of a polynomial is still a polynomial. Chains
  of reductions are the raw material of the next lesson's "reduction web."

## A warm-up reduction: matching reduces to flow

Reductions are not a tool reserved for hardness arguments; we have already been
using them to design algorithms. The cleanest example, motivating the whole
idea, is [**bipartite matching**](/algorithms/graphs/network-flow). We are given a set
of tasks $t_1,\dots,t_m$, a set of workers $w_1,\dots,w_n$, and a compatibility
table, where $A[i,j]$ is **true** when task $t_i$ can be done by worker $w_j$. A
**matching** assigns tasks to workers so that no task and no worker is used
twice; we want a matching of maximum cardinality. There is a slogan worth
remembering here:

> **Remark (Modeling tip).** Whenever a graph problem asks for paths or assignments subject to a
> per-edge or per-vertex _budget constraint_ (here, "each task and each worker
> used at most once"), consider routing it through **max-flow** as a subroutine.

We do not write a matching algorithm from scratch. Instead we reduce
$\textsc{Bipartite-Matching}$ to $\textsc{Max-Flow}$, a problem we already know
how to solve, and reuse that solver. This is the pipeline of the previous
section made concrete, and because matching is a _search_ problem, the output
transformer is no longer trivial.

**Transform the input.** Build a flow network: add a **source** $s$ and a
**sink** $t$. Direct an edge $s \to t_i$ for every task, an edge $w_j \to t$ for
every worker, and an edge $t_i \to w_j$ whenever $A[i,j]$ is **true**. Give
_every_ edge capacity $1$. The unit capacities out of $s$ and into $t$ encode
the budget constraints: each task and each worker can carry at most one
unit.

$$
% caption: Flow network reducing bipartite matching to max-flow with unit-capacity edges.
\begin{tikzpicture}[>=Stealth, node distance=10mm,
    v/.style={circle, draw, inner sep=1.6pt, font=\small},
    vnode/.style={circle, draw, minimum width=10mm, font=\small}]
  \node[vnode] (s) at (0,1.5) {$s$};
  \node[v] (t1) at (3,3.0) {$t_1$};
  \node[v] (t2) at (3,1.5) {$t_2$};
  \node[v] (t3) at (3,0.0) {$t_3$};
  \node[v] (w1) at (6,3.0) {$w_1$};
  \node[v] (w2) at (6,1.5) {$w_2$};
  \node[v] (w3) at (6,0.0) {$w_3$};
  \node[vnode] (t) at (9,1.5) {$t$};
  % source to tasks
  \draw[->] (s) -- (t1);
  \draw[->] (s) -- (t2);
  \draw[->] (s) -- (t3);
  % compatibility edges (from table A)
  \draw[->] (t1) -- (w1);
  \draw[->] (t1) -- (w2);
  \draw[->] (t2) -- (w2);
  \draw[->] (t3) -- (w2);
  \draw[->] (t3) -- (w3);
  % workers to sink
  \draw[->] (w1) -- (t);
  \draw[->] (w2) -- (t);
  \draw[->] (w3) -- (t);
  \node[font=\scriptsize] at (1.2,2.55) {cap. $1$};
  \node[font=\scriptsize] at (7.8,2.55) {cap. $1$};
\end{tikzpicture}
$$

**Solve with the black box.** Run any max-flow algorithm (Ford–Fulkerson or
Edmonds–Karp) and let $f^\ast$ be the maximum flow. The value $|f^\ast|$ is the size
of the largest matching.

**Transform the output.** A flow value is just a number; the _matching_ is
recovered by reading off which compatibility edges $t_i \to w_j$ carry one unit
of flow. Those edges are the assignment.

Two claims make the reduction correct, and it's worth separating
them.

> **Proof (correctness).**
> - _Completeness (easy direction)._ If some $k$ tasks **can** be assigned, then pushing one
>   unit along each chosen $s \to t_i \to w_j \to t$ path gives a flow of value
>   $k$. So the max flow is at least as large as the best matching.
> - _Soundness (less easy direction)._ If the max flow value **is** $k$, then $k$ tasks can
>   be assigned. This needs the **integrality theorem**: when every edge capacity
>   is an integer, some maximum flow is **integral** (every $f_{uv} \in
>   \mathbb{Z}$) and Ford–Fulkerson actually finds such a flow. With unit
>   capacities, integral means each edge carries $0$ or $1$, and an integral flow
>   decomposes into a collection of edge-disjoint $s$–$t$ **path flows**. Each
>   path uses one task and one worker, so the paths _are_ a matching of size $k$.
>
> Both directions give $|f^\ast| = $ (size of maximum matching). $\qed$

So the reduction is valid. The transform–solve–transform diagram now does real work: build
the network ($f$), call the flow solver ($B$), decompose the integral flow into
paths (the output transformer). We obtained a matching algorithm without
writing one, purely because $\textsc{Bipartite-Matching} \le_P \textsc{Max-Flow}$.

::impl{algo="matching_to_flow"}

## A small reduction between decision problems

The matching reduction reused an _easy_ solver to solve another easy problem.
The reductions that drive intractability go the other way, relating two
_decision_ problems with no known fast solver, but the mechanism is identical.
Here is a textbook example. $\textsc{Independent-Set}$ asks:
given a graph $G$ and integer $k$, is there a set of $k$ vertices no two of
which are adjacent? **Clique** asks: is there a set of $k$ vertices that are
_all_ pairwise adjacent? These are the same question asked of complementary
graphs.

Given an instance $(G, k)$ of $\textsc{Independent-Set}$, build the **complement**
graph $\bar G$ on the same vertices, where $uv$ is an edge of $\bar G$ exactly
when it is _not_ an edge of $G$. A set $S$ is independent in $G$ (no edges
inside it) precisely when $S$ is a clique in $\bar G$ (all edges inside it).
So
$$ (G, k) \in \textbf{Independent-Set} \iff (\bar G, k) \in \textbf{Clique}. $$
Constructing $\bar G$ takes time polynomial in the size of $G$, so this is a
valid reduction $\textbf{Independent-Set} \le_P \textbf{Clique}$, and, since
complementation is its own inverse, the reverse reduction holds too. The two
problems are equivalent in difficulty: a fast algorithm for either yields one
for the other.[^erickson-reduce]

$$
% caption: A size-$3$ independent set in $G$ is a size-$3$ clique in the complement
%          $\bar G$ on the same vertices.
\begin{tikzpicture}[>=Stealth, font=\small,
    v/.style={circle, draw, inner sep=1.7pt, minimum size=5mm},
    sel/.style={circle, draw=acc, fill=acc!15, very thick, inner sep=1.7pt, minimum size=5mm}]
  \definecolor{acc}{HTML}{2348F2}
  % G on the left
  \begin{scope}[shift={(0,0)}]
    \node[sel] (a) at (90:1.3) {$1$};
    \node[v]   (b) at (162:1.3) {$2$};
    \node[sel] (c) at (234:1.3) {$3$};
    \node[v]   (d) at (306:1.3) {$4$};
    \node[sel] (e) at (18:1.3) {$5$};
    \draw (a)--(b); \draw (b)--(c); \draw (c)--(d); \draw (d)--(e);
    \node at (0,-2.1) {$G$: 1,3,5 \texttt{independent}};
  \end{scope}
  % complement on the right
  \begin{scope}[shift={(5.6,0)}]
    \node[sel] (a) at (90:1.3) {$1$};
    \node[v]   (b) at (162:1.3) {$2$};
    \node[sel] (c) at (234:1.3) {$3$};
    \node[v]   (d) at (306:1.3) {$4$};
    \node[sel] (e) at (18:1.3) {$5$};
    % complement edges: all non-edges of G
    \draw (a)--(c); \draw (a)--(d); \draw (a)--(e);
    \draw (b)--(d); \draw (b)--(e); \draw (c)--(e);
    \node at (0,-2.1) {comp. $G$: 1,3,5 clique};
  \end{scope}
  \draw[<->, acc, thick] (1.7,0) -- node[above, font=\footnotesize, text=acc]{\texttt{complement}} (3.9,0);
\end{tikzpicture}
$$

::impl{algo="independent_set_to_clique"}

## The P versus NP question

We now have two classes with $\mathsf{P} \subseteq \mathsf{NP}$. Problems in
$\mathsf{P}$ can be _solved_ quickly; problems in $\mathsf{NP}$ can at least
have their solutions _checked_ quickly. The defining open question of
theoretical computer science is whether checking is genuinely easier than
solving.

> **Question ($\mathsf{P} \overset{?}{=} \mathsf{NP}$).** Is every problem whose solutions
> can be verified in polynomial time also _solvable_ in polynomial time?

Almost everyone believes the answer is **no**: that $\mathsf{P} \ne
\mathsf{NP}$, and that finding a needle is fundamentally harder than
recognizing one once found. But no proof is known in either direction, and the
question carries a million-dollar Clay Millennium Prize.[^skiena-pnp] What makes it more
than a curiosity is the next lesson's discovery: there are problems in
$\mathsf{NP}$, the [**$\mathsf{NP}$-complete**](/algorithms/intractability/np-completeness) problems, that are _universally
hardest_. Every problem in $\mathsf{NP}$ reduces to each of them. A
polynomial-time algorithm for even one would collapse $\mathsf{P}$ and
$\mathsf{NP}$ into a single class; a proof that even one requires
super-polynomial time would settle the question the other way.

$$
% caption: Conjectured world with P and NP-complete as disjoint regions inside NP.
\begin{tikzpicture}[>=Stealth]
  \definecolor{acc}{HTML}{2348F2}
  \draw[thick] (-3.6,-1.9) rectangle (3.6,1.9);
  \node[anchor=north west] at (-3.45,1.78) {$\mathsf{NP}$};
  \draw[draw=acc, fill=acc!15] (-1.35,0) ellipse (1.95 and 1.35);
  \node at (-1.35,0) {$\mathsf{P}$};
  \draw[draw=red!75!black, fill=red!18] (2.15,0) ellipse (0.95 and 1.35);
  \node[align=center] at (2.15,0) {$\mathsf{NP}$-\\complete};
\end{tikzpicture}
$$

The sketch shows the _conjectured_ world: $\mathsf{P}$ and the
$\mathsf{NP}$-complete problems sit as disjoint regions inside $\mathsf{NP}$. If
$\mathsf{P} = \mathsf{NP}$, all three regions coincide and the entire picture
collapses to a single region. We do not know which world we live in, but we will
see that the two regions, if separate, can never overlap.

## Why the question is still open, and NP in practice

The textbooks state $\mathsf{P} \ne \mathsf{NP}$ as a conjecture and move on, but
it is worth knowing _why_ half a century of effort has not settled it — the failure
is structured, not random. Every general proof technique tried so far runs into a
formal **barrier** that provably cannot separate the classes:

- **Relativization** (Baker–Gill–Solovay, 1975): there exist oracles $A$ with
  $\mathsf{P}^A = \mathsf{NP}^A$ and others with $\mathsf{P}^B \ne \mathsf{NP}^B$.
  Any proof that "relativizes" — treats the machine as a black box, as diagonal
  arguments do — must give the same answer relative to every oracle, so it cannot
  decide the unrelativized question.[^bgs]
- **Natural proofs** (Razborov–Rudich, 1997): the circuit-complexity arguments that
  were the great hope of the 1980s share a common "largeness + constructivity"
  shape, and any proof of that shape would, paradoxically, break the very
  pseudorandom generators that cryptography assumes exist.[^rr]

A separating proof must therefore be _non-relativizing_ and _non-natural_ — it must
exploit the specific structure of computation in a way no known method does.

In practice, there is another consideration the theory does not capture: $\mathsf{NP}$
-completeness is a **worst-case** statement, and the worst case is often not the
case you have. Modern **SAT solvers** (CDCL: conflict-driven clause learning) and
**MILP solvers** routinely dispatch industrial instances with millions of
variables — hardware verification, planning, scheduling — that are formally
$\mathsf{NP}$-complete.[^sat] The hardness is real but concentrated on carefully
constructed adversarial inputs; typical structured instances have enough exploitable
regularity that heuristic search finds an answer fast. The lesson to carry into the
rest of the module is that "$\mathsf{NP}$-complete" is a reason to _stop looking for
a guaranteed-polynomial exact algorithm_, not a verdict that every instance is
unsolvable — the reason the next lessons turn to approximation, parameter
bounds, and heuristics.

## Takeaways

- We study **decision problems** (yes/no answers); optimization problems reduce
  to them by binary search, so little is lost.
- $\mathsf{P}$ is the class of problems **solvable** in polynomial time;
  $\mathsf{NP}$ is the class of problems whose **yes**-answers admit a short,
  polynomial-time **checkable** certificate. Always $\mathsf{P} \subseteq
  \mathsf{NP}$.
- A **polynomial-time reduction** $A \le_P B$ is a **transform–solve–transform**
  pipeline: transform the input, call a black-box solver for $B$, transform its
  output back. It means "$A$ is no harder than $B$": tractability flows forward
  ($B$ easy $\Rightarrow A$ easy), hardness flows backward ($A$ hard
  $\Rightarrow B$ hard). To prove $B$ hard, reduce a known hard problem **to**
  $B$.
- Reductions also _build_ algorithms: $\textsc{Bipartite-Matching} \le_P
  \textsc{Max-Flow}$ solves matching by routing it through a flow solver, with
  the integrality theorem guaranteeing the flow decomposes back into a matching.
- Reductions **compose**, so $\le_P$ chains, building a web of equivalent
  difficulty.
- Whether $\mathsf{P} = \mathsf{NP}$, that is, whether checking is as easy as
  solving, is the central open question, and the hardest problems in $\mathsf{NP}$
  decide it.

[^clrs-p]: **CLRS**, Ch. 34 — NP-Completeness (§34.1): the class $\mathsf{P}$ of polynomial-time-solvable decision problems and its closure-based robustness.
[^clrs-np]: **CLRS**, Ch. 34 — NP-Completeness (§34.2): the class $\mathsf{NP}$ defined via a polynomial-time verifier and short certificates.
[^clrs-reduce]: **CLRS**, Ch. 34 — NP-Completeness (§34.3): polynomial-time reductions $A \le_P B$ as a measure of relative difficulty.
[^erickson-reduce]: **Erickson**, Ch. 12 — NP-Hardness: the Independent-Set / Clique equivalence via graph complementation.
[^skiena-pnp]: **Skiena**, §11 — NP-Completeness: the $\mathsf{P} \overset{?}{=} \mathsf{NP}$ question and the belief that verifying is easier than solving.
[^bgs]: Theodore Baker, John Gill, and Robert Solovay, "Relativizations of the P =? NP Question," _SIAM Journal on Computing_ 4(4), 1975 — oracles under which the two classes coincide and differ, ruling out relativizing proofs.
[^rr]: Alexander Razborov and Steven Rudich, "Natural Proofs," _Journal of Computer and System Sciences_ 55(1), 1997 — the natural-proofs barrier against a large class of circuit lower-bound arguments.
[^sat]: João Marques-Silva, Inês Lynce, and Sharad Malik, "Conflict-Driven Clause Learning SAT Solvers," in _Handbook of Satisfiability_ (2nd ed.), 2021 — the CDCL architecture behind SAT solvers that dispatch large industrial NP-complete instances.