NP-Completeness and Reductions

The classes

Class	Definition
P	solvable in polynomial time
NP	a solution can be verified in polynomial time
NP-hard	at least as hard as every problem in NP (via polynomial reduction)
NP-complete	in NP and NP-hard
co-NP	the complement is in NP
PSPACE	solvable in polynomial space
p	counting the solutions

$\mathrm{P}\subseteq \mathrm{NP}\subseteq \mathrm{PSPACE}$, and whether $\mathrm{P}=\mathrm{NP}$ is the central open question. See Complexity Theory.

Reductions

$A{\le }_{p}B$ (”$A$ reduces to $B$”) means: a polynomial-time transformation maps instances of $A$ to instances of $B$ with the same yes/no answer.

If $A$ is NP-hard and $A{\le }_{p}B$, then $B$ is NP-hard.

Note the direction — to prove $B$ is hard, reduce a known hard problem to $B$, not the other way round. Reversing this is the classic error.

The reduction map

                      SAT  (Cook-Levin: the first NP-complete problem)
                       |
                     3-SAT
        /         /    |     \            \
  3-COLORING  CLIQUE  SUBSET-SUM   HAMILTONIAN-CYCLE   ...
      |          |         |               |
  planar 3-col  IND-SET  PARTITION        TSP
                  |         |
             VERTEX-COVER  KNAPSACK

Karp’s 21 problems (1972) established the core of this map. To show a new problem is NP-hard, reduce from the closest one on it.

The problems to recognise

Problem	Status
SAT, 3-SAT	NP-complete
2-SAT	P — see 2-SAT
Clique, independent set, vertex cover	NP-complete
Vertex cover / independent set on bipartite graphs	P (König)
Graph 3-colouring	NP-complete
2-colouring (bipartiteness)	P
Hamiltonian path/cycle	NP-complete
Eulerian path/circuit	P
TSP	NP-hard
Subset sum, partition, knapsack	NP-complete (weakly — pseudo-poly DP exists)
Bin packing, makespan	NP-hard
Set cover, dominating set	NP-complete
Steiner tree	NP-hard
Shortest path, MST, max flow, matching	P
Longest path (general graph)	NP-hard
Longest path in a DAG	P
Integer programming	NP-hard
Linear programming	P
Graph isomorphism	quasipolynomial; not known to be either
Factoring	in NP ∩ co-NP; not known to be NP-complete

The pairs are the useful part: each row where a tiny change flips the difficulty is a pattern worth memorising. Hamiltonian vs Eulerian, 2-SAT vs 3-SAT, 2-colouring vs 3-colouring, DAG longest path vs general longest path, LP vs ILP.

Weak vs strong NP-hardness

	Weakly NP-hard	Strongly NP-hard
Pseudo-polynomial algorithm	exists	does not (unless P=NP)
FPTAS	possible	impossible
Examples	subset sum, knapsack, partition	TSP, bin packing, 3-partition, clique

Knapsack’s $O(nW)$ DP is polynomial in the value of $W$ but exponential in its number of bits — that is exactly what “weakly NP-hard” means, and it is why an FPTAS exists for knapsack but not for TSP.

What to do when you recognise NP-hardness

Stop looking for a polynomial exact algorithm. Then check the constraints — they tell you the intended approach:

Constraint	Approach
$n\le 20$	bitmask DP
$n\le 45$	meet in the middle
$n\le 100$, sparse or structured	branch and bound
Small parameter $k$	FPT algorithm
Bounded values ($\sum w\le 10^6$)	pseudo-polynomial DP
The graph is a tree	tree DP — most NP-hard graph problems are easy on trees
The graph is bipartite	matching/flow
The graph is planar	separator-based, or a specialised algorithm
The graph has small treewidth	DP over a tree decomposition
Scored/marathon problem	heuristics

“Restricted to trees” is the most common escape hatch in contests. Independent set, dominating set, vertex cover, colouring and Steiner tree are all NP-hard in general and all linear-time on trees.

Beyond NP

Class	Typical problem
#P-complete	counting perfect matchings (the permanent), counting SAT solutions
PSPACE-complete	generalised games (Go, chess on $n\times n$), QBF
EXPTIME-complete	some two-player games with full generality
Undecidable	halting problem, Post correspondence

Counting is often strictly harder than deciding: finding a perfect matching is polynomial, counting them is p-complete. If a problem asks for a count where the decision version is already interesting, be alert.

See also: Complexity Theory · Parameterized Complexity · Approximation Algorithms