---
title: "P, NP, and Reductions — What You Actually Need"
summary: The definitions in contest language, how a reduction is written, and what "NP-complete" does and does not forbid.
difficulty: core
tags: [complexity, reductions]
see: [complexity/npc-graphs, complexity/escape, appendix/notation]
---

:::definition label="Three classes, in the words that matter"
- **P**: decidable in time polynomial in the input length.
- **NP**: every *yes* instance has a certificate verifiable in polynomial time. (Vertex cover: the certificate is the set itself; check size and coverage in $O(n+m)$.)
- **NP-complete**: in NP, and every NP problem reduces to it. If any NP-complete problem is in P, then P = NP.
:::

:::note title="What the definition does not say"
It does not say a problem is slow for the given $n$. "Vertex cover with $n \le 20$" is trivial; "with $n \le 10^5$ and the graph is a tree" is a 6-line DP (@trees/properties). NP-completeness is a statement about *uniform* algorithms across all inputs. A contest problem is never "solve NP-complete instances fast" — it is "solve this NP-complete problem under a promise, or exactly because $n$ is small, or approximately".
:::

## Reductions, mechanically
To show $B$ is NP-hard: pick a known NP-complete $A$, and give a polynomial map $f$ with
$$x \in A \iff f(x) \in B .$$
Direction matters: you reduce the *known-hard* problem to the *new* one. Then a fast algorithm for $B$ would give one for $A$.

:::example title="Independent set ⇄ vertex cover (the cleanest pair)"
$S$ is an independent set $\iff$ $V \setminus S$ is a vertex cover. So $\alpha(G) + \tau(G) = n$, and an algorithm for either solves the other with the same running time — a reduction that is one line and also a theorem. Note it converts *maximisation* to *minimisation*, which is why the "minimum" version is the one usually stated as complete.
:::

:::example title="3-SAT → 2-SAT is impossible (unless P = NP), and what you can do instead"
A reduction must keep the problem class: 2-SAT is in P (@special/twosat), so no polynomial reduction from 3-SAT to it exists unless P = NP. If a problem looks like 3-SAT but each variable appears in at most 2 clauses, that is a *promise* you can exploit: the constraint graph has max degree 2, so it is paths and cycles and can be solved by DP — the typical shape of a "3-SAT that is actually easy" problem.
:::

:::props title="Four habits that make reduction-writing fast"
1. Prove membership in NP *first*: if you cannot state the certificate, you are aiming at the wrong class (NP-hard vs FP vs search),
2. choose the source problem by **structure match**: numbers → Subset Sum / Partition; sets and conflicts → Independent Set / Clique; assignment → 3-SAT; ordering → Betweenness; partition into groups → 3-D Matching,
3. keep the construction *local*: gadgets of constant size, with the "iff" checked in both directions for each gadget,
4. finish by stating what the reduction *forbids*: "hence no polynomial exact algorithm unless P = NP" — and then immediately ask which escape route the constraints suggest (@complexity/escape).
:::

:::warning title="Two confusions that cost real points"
- **NP-hard vs NP-complete**: optimisation versions (minimum vertex cover) are NP-hard but not decision problems, so they are not "NP-complete" strictly speaking. Say "NP-hard" and be safe.
- **decision vs search**: a decision oracle for "$\tau(G) \le k$?" gives the actual set with $n$ extra queries (binary search then greedy inclusion), so algorithmically the two are equivalent up to a factor $n$. Knowing this saves you from "but my problem asks for the set" panic.
:::

:::exercise title="Three reductions to write out in full"
1. Clique $\le_m$ Independent Set via the complement graph — state the gadget and both directions of the equivalence.
2. Explain why the identity $\alpha(G) + \tau(G) = n$ turns a *maximisation* into a *minimisation*, and why the analogous statement for matchings ($\nu(G) \le \tau(G)$, with equality only for bipartite graphs per @matching/konig) gives you an algorithm on bipartite graphs but not on general ones.
3. Subset Sum $\le_m$ "partition a tree's edge weights so both halves have equal sum" — build the tree as a star and note what the reduction costs in bits.
:::