NP-complete, NP-hard & coping strategies

Reductions, the hardest problems in NP, the famous examples, and what to do when you hit one. · 12 min read

Reductions

A reduction transforms problem A into problem B in polynomial time so that an answer to B gives an answer to A. If A reduces to B, then B is at least as hard as A — a fast algorithm for B would give a fast algorithm for A. Reductions are how we compare hardness without solving anything.

NP-complete

A problem is NP-complete if it is in NP and every problem in NP reduces to it. These are the hardest problems in NP: solve one in polynomial time and you've solved all of NP (proving P = NP). Cook–Levin proved SAT (boolean satisfiability) is NP-complete; thousands of others were then shown NP-complete by reducing SAT (or a known NP-complete problem) to them.

Famous NP-complete problems: SAT / 3-SAT, the Travelling Salesman decision problem, graph colouring, vertex cover, independent set, clique, subset-sum, knapsack (decision), and Hamiltonian cycle.

NP-hard

NP-hard means "at least as hard as every problem in NP" — but without the requirement of being in NP itself. Every NP-complete problem is NP-hard; but NP-hard also includes problems that aren't even decision problems or aren't known to be in NP, such as the optimisation version of TSP ("find the shortest tour", which the Held-Karp DP solves only in exponential time) and the halting problem (which is undecidable, hence harder still).

How to cope with an NP-hard problem

Recognising a problem as NP-hard isn't defeat — it tells you to stop hunting for a fast exact general algorithm and pick a realistic strategy:

Exact but exponential — fine for small n: bitmask DP (Held-Karp TSP, O(2ⁿn²)), branch and bound, meet-in-the-middle.
Approximation algorithms — provably within a factor of optimal (e.g. a 2-approximation for metric TSP via an MST).
Heuristics / local search — greedy, simulated annealing, genetic algorithms: no guarantee, but good in practice.
Special cases / structure — many NP-hard problems are polynomial on trees, planar graphs, or bounded-width inputs.
Parameterised algorithms — fast when some parameter k (not n) is small: O(f(k)·nᶜ).
ILP / SAT solvers — modern solvers crush surprisingly large real instances despite worst-case hardness.