When cleverness runs out
A university registrar has 400 exams and 12 time slots. Two exams that share a student cannot be in the same slot. Is there a timetable? A delivery company has 60 stops for one van. What is the shortest route that visits them all and comes home? A chip designer has a circuit with a million gates and wants to know whether any input can make two supposedly equivalent outputs differ.
Each of these looks like the problems you solved earlier in this level, and you might expect another clever greedy rule or dynamic programme to crack it. For these three, nobody has ever found one, despite more than fifty years of effort by many of the best minds in the field. Better still, we can prove that they stand or fall together: a fast algorithm for any one of them would give fast algorithms for all of them and for thousands of other problems. That web of equivalences is the theory of NP-completeness, and knowing it is a practical skill. When you recognise that your problem is NP-hard, you stop searching for a perfect fast algorithm that probably does not exist and reach for the tools that work: special structure, approximation, heuristics, and solvers.
This lesson gives the engineer's version of the theory. Lumenary Math's Computational complexity lesson gives the mathematician's, with Turing machines and full proofs, and Computability covers the problems no algorithm can solve at all, however much time it is given.
Decision problems, P and NP
Complexity theory classifies problems, not programs, and it is cleanest for yes-or-no questions.
Definition— decision problem
A decision problem is a question with a yes-or-no answer about an input written as a string of symbols. Its size is the length of that string. Examples: "Is this number prime?" "Can this graph be coloured with 3 colours so that adjacent vertices differ?" "Is there a tour through these cities of total length at most ?"
Optimisation problems ("what is the shortest tour?") have decision versions ("is there a tour of length at most ?"), and the two are usually equally hard: with a decision procedure you can binary-search for the optimal .
Definition— P
P is the class of decision problems that some algorithm solves in time for a constant : polynomial time.
Sorting, shortest paths, minimum spanning trees, matching, primality testing and linear programming are all in P. Polynomial time is the theory's stand-in for "efficient". It is a coarse stand-in, since is not efficient, but it is robust: it does not depend on the programming language or machine model, and the polynomial-time algorithms people actually find almost always have small exponents.
Definition— NP
NP is the class of decision problems for which every yes-instance has a certificate (a proposed solution) of polynomial length that a polynomial-time verifier can check. If the answer is no, no certificate fools the verifier.
For 3-colouring, the certificate is a colouring: check each edge's endpoints differ, linear time. For the travelling salesperson's decision version, it is a tour: check that it visits every city once and add up its length. For SAT, the satisfiability problem for Boolean formulas, it is an assignment of true or false to each variable: evaluate the formula. NP is the class of problems whose solutions are easy to check, whether or not they are easy to find. (The name means "nondeterministic polynomial time", from an equivalent definition with a machine that may guess; it does not mean "not polynomial".) Every problem in P is in NP, since the verifier can ignore the certificate and solve the problem itself, so . Whether the inclusion is strict is the P versus NP question.
from itertools import product
# A formula in conjunctive normal form (CNF): a list of clauses, each a list of literals.
# Literal 3 means "x3 is true" and -3 means "x3 is false" (the DIMACS convention SAT solvers use).
# The formula is true when every clause contains at least one true literal.
formula = [[-1, -3, -4], [-2, 3, 4], [-1, -3, 5], [2, -4, 5], [1, -2, -3], [1, 2, 4],
[1, 3, -4], [-2, 4, -5], [-1, 2, 3], [2, -3, -5], [3, -4, -5]]
def satisfies(clauses, assignment):
"""The verifier: does the assignment {variable: bool} make every clause true? Linear time."""
return all(any(assignment[abs(lit)] == (lit > 0) for lit in clause) for clause in clauses)
certificate = {1: True, 2: True, 3: False, 4: True, 5: False}
print("the certificate checks out:", satisfies(formula, certificate))
# Without a certificate: try all 2^n assignments.
n, tried = 5, 0
for values in product([False, True], repeat=n):
tried += 1
assignment = dict(zip(range(1, n + 1), values))
if satisfies(formula, assignment):
print(f"search found {assignment} after {tried} of {2 ** n} assignments")
break
for n in (20, 50, 100, 300):
print(f"n = {n:>3}: checking one assignment ~ {n} steps; trying all of them ~ 2^{n} = {2 ** n:.1e}")Checking grows linearly; blind search grows as . At the search space is larger than the number of atoms in the observable universe (roughly ). The question is whether something fundamentally better than blind search always exists.
Reductions and NP-completeness
How can we say a problem is hard when we cannot prove that it needs exponential time? By comparison. A reduction shows that one problem is no harder than another.
Definition— polynomial-time reduction
Problem reduces to problem , written , if there is a polynomial-time function that turns any instance of into an instance of with the same answer: is a yes-instance of exactly when is a yes-instance of .
If and has a polynomial-time algorithm, so does : transform, then solve. Read the other way: if is hard, must be at least as hard. The direction matters. To show your new problem is hard, you reduce a known hard problem to , not to it. Reducing your problem to SAT shows only that SAT is powerful enough to express it, which is useful in practice (it means you can use a SAT solver) but says nothing about hardness.
Definition— NP-hard, NP-complete
A problem is NP-hard if every problem in NP reduces to it. It is NP-complete if it is NP-hard and in NP.
Theorem— Cook–Levin (1971)
SAT is NP-complete.
The idea of the proof is that a verifier's computation, step by step, is itself a Boolean circuit of polynomial size; a formula can say "this computation is a valid run that accepts", and the formula is satisfiable exactly when some certificate makes the verifier accept. Stephen Cook published it in 1971 and Leonid Levin found it independently in the Soviet Union. A year later Richard Karp showed, by chains of reductions, that 21 problems from across combinatorics and operations research were NP-complete too, including graph colouring, clique, vertex cover, Hamiltonian cycle and knapsack. Since then thousands more have joined the list. Once one problem is known NP-complete, each new one needs only a single reduction from any of them.
A note on what "complete" buys: if any NP-complete problem has a polynomial-time algorithm, then every problem in NP does, and P = NP. If any one of them provably needs super-polynomial time, they all do.
Hard problems and their easy cousins
Hardness is fragile, and that is good news for engineers. Small changes to a problem can move it into P:
| Hard (NP-complete) | Easy relative (in P) |
|---|---|
| 3-colouring a graph | 2-colouring: a graph is 2-colourable exactly when it is bipartite; breadth-first search decides it in linear time |
| 3-SAT: clauses of three literals | 2-SAT: clauses of two literals, solved in linear time via strongly connected components |
| Travelling salesperson: visit every vertex once | Shortest path between two vertices; Euler tour: use every edge once |
| Longest simple path | Shortest path (with non-negative weights) |
| Vertex cover in a general graph | Vertex cover in a bipartite graph (via maximum matching) or a tree (dynamic programming) |
A reduction you can run: colouring as satisfiability
Reductions also run towards SAT in everyday engineering, because SAT solvers are so good. Here is the reduction from -colouring to SAT. For each region and colour , introduce a variable meaning "region gets colour ". Then write three kinds of clause: every region gets at least one colour (); no region gets two ( for each pair of colours); neighbours differ ( for each border and each colour). For regions, borders and colours that is clauses, polynomial in the input. The code below builds the formula for the map of South America and hands it to a minimal SAT solver.
from itertools import combinations
borders = {
"Argentina": ["Bolivia", "Brazil", "Chile", "Paraguay", "Uruguay"],
"Bolivia": ["Brazil", "Chile", "Paraguay", "Peru"],
"Brazil": ["Colombia", "French Guiana", "Guyana", "Paraguay", "Peru", "Suriname", "Uruguay", "Venezuela"],
"Chile": ["Peru"],
"Colombia": ["Ecuador", "Peru", "Venezuela"],
"Ecuador": ["Peru"],
"Guyana": ["Suriname", "Venezuela"],
"Suriname": ["French Guiana"],
}
regions = sorted(set(borders) | {b for bs in borders.values() for b in bs})
edges = [(u, v) for u in borders for v in borders[u]]
def colouring_to_cnf(regions, edges, k):
"""The reduction: a CNF formula that is satisfiable exactly when the map is k-colourable."""
var = {(r, c): i * k + c + 1 for i, r in enumerate(regions) for c in range(k)} # x[r, c]
clauses = []
for r in regions:
clauses.append([var[r, c] for c in range(k)]) # at least one colour
for c1, c2 in combinations(range(k), 2):
clauses.append([-var[r, c1], -var[r, c2]]) # at most one colour
for u, v in edges:
for c in range(k):
clauses.append([-var[u, c], -var[v, c]]) # neighbours differ
return clauses, var
def dpll(clauses, assignment=None, stats=None):
"""A minimal DPLL SAT solver: unit propagation, then branch. Returns a model or None."""
assignment = dict(assignment or {})
stats = stats if stats is not None else {"branches": 0}
while True: # unit propagation
simplified, unit = [], None
for clause in clauses:
if any(assignment.get(abs(l)) == (l > 0) for l in clause):
continue # clause already satisfied
rest = [l for l in clause if abs(l) not in assignment]
if not rest:
return None # every literal false: conflict
if len(rest) == 1:
unit = rest[0]
simplified.append(rest)
clauses = simplified
if unit is None:
break
assignment[abs(unit)] = unit > 0 # a one-literal clause forces its literal
if not clauses:
return assignment
stats["branches"] += 1
lit = clauses[0][0] # branch on the first open literal
for value in (lit > 0, lit < 0):
model = dpll(clauses, {**assignment, abs(lit): value}, stats)
if model is not None:
return model
return None
for k in (3, 4):
clauses, var = colouring_to_cnf(regions, edges, k)
stats = {"branches": 0}
model = dpll(clauses, stats=stats)
print(f"{k} colours: {len(var)} variables, {len(clauses)} clauses, {stats['branches']} branches ->",
"unsatisfiable" if model is None else "satisfiable")
if model:
colour = {r: c for (r, c), x in var.items() if model.get(x)}
assert all(colour[u] != colour[v] for u, v in edges)
names = ["red", "green", "blue", "gold"]
print(" ", ", ".join(f"{r}: {names[colour[r]]}" for r in regions))Three colours are impossible, and the reason is visible on the map: Argentina, Bolivia, Brazil and Paraguay all border one another, so they need four different colours. The solver found that out in a handful of branches, because unit propagation (when a clause has one undecided literal left, that literal is forced) does most of the reasoning. That is the DPLL algorithm of the early 1960s. Modern solvers add conflict-driven clause learning: every time they hit a contradiction, they work out which earlier decisions caused it and add a new clause that forbids that combination forever.
What P versus NP would mean
The Clay Mathematics Institute lists P versus NP among its seven Millennium Prize Problems, with a million-dollar prize for a proof either way. Most researchers believe , for reasons that are evidence rather than proof: decades of failed attempts at fast algorithms for thousands of NP-complete problems from unrelated fields, and the intuition that recognising a good solution should be easier than producing one. Known proof techniques have also been shown unable to settle the question on their own (the "relativisation" and "natural proofs" barriers), which is part of why it is so hard.
If P = NP with a practical algorithm, the world would change. Any problem whose answers can be checked quickly could be solved quickly: optimal schedules, routes and chip layouts; and, since a proof is a certificate a computer can check, finding proofs of theorems of reasonable length would become a mechanical search. Most of today's public-key cryptography would fall, because recovering a secret key from public information is a search problem whose answer is easy to check (see Applied cryptography).
But P = NP might not be practical. A proof could give an algorithm running in time, or show only that an algorithm exists without constructing it.
If P ≠ NP, as expected, nothing changes in practice: we will have confirmed that no algorithm solves every instance of an NP-complete problem in polynomial time. It would not mean that every instance is hard, that good approximations are impossible, or that cryptography is secure; the security of specific systems rests on specific problems, such as factoring, that are not known to be NP-complete.
Kurt Gödel asked a version of the question in a 1956 letter to John von Neumann, wondering how many steps a machine would need to decide whether a statement has a proof of a given length. The question was formalised only in the early 1970s.
Coping: what engineers actually do
NP-hardness is a statement about the worst case over all inputs, assuming P ≠ NP. Your inputs are not all inputs, and you may not need the exact optimum. That leaves a lot of room.
1. Look for structure
Real instances often have properties that put them in an easy special case. Assigning lectures with fixed start and end times to rooms is colouring an interval graph, which a greedy sweep solves optimally. Many graphs from road networks or circuits have small treewidth, which makes dynamic programming feasible. Sometimes a natural parameter is small: deciding whether a graph has a vertex cover of size at most takes about steps by branching (some endpoint of each edge must be in the cover, so try each), which is fast for even when the graph has millions of edges. This is parameterised complexity: the exponential part depends only on the parameter.
2. Accept an approximation, with a guarantee
An approximation algorithm runs in polynomial time and returns a solution within a proven factor of optimal.
Definition— vertex cover
A vertex cover of a graph is a set of vertices that touches every edge: for each edge , or . Finding a smallest one is NP-hard.
The algorithm: go through the edges; whenever an edge has neither endpoint in yet, add both endpoints.
Theorem— The matching algorithm is a 2-approximation for vertex cover
The set it returns is a vertex cover, and , where OPT is the size of a smallest vertex cover.
Proof
It is a cover: every edge is examined, and after its turn at least one of its endpoints is in ; later steps only add vertices. It is small: let be the set of edges whose endpoints were added. No two edges of share a vertex, because once an edge's endpoints are in , any later edge touching them is skipped. Any vertex cover, the optimal one included, must contain an endpoint of each edge in , and since these edges are disjoint those endpoints are all different. So , and .
∎
The proof has the shape of almost every approximation argument: find a lower bound on the optimum (here, the size of any matching) that you can compute, and compare your answer with the bound rather than with the unknown optimum. The same algorithm can be read as rounding a linear program: write vertex cover as an integer linear program (minimise subject to for every edge, ), relax to , solve it in polynomial time, and take every vertex with . That also gives a factor of 2, and it is a pattern you will meet in real optimisation work.
How good can approximation get? It depends sharply on the problem. For travelling salesperson with distances that obey the triangle inequality, doubling a minimum spanning tree (from Spanning trees) gives a factor of 2, and Christofides' algorithm of 1976 gives 1.5; in 2021 Karlin, Klein and Oveis Gharan finally improved on 1.5, by a minuscule amount. For TSP with arbitrary distances, no constant factor is achievable at all unless P = NP. For vertex cover, nobody knows how to beat 2 by any constant, and under a widely studied conjecture (the Unique Games Conjecture) nobody can.
3. Use heuristics and local search
A heuristic is a method that usually works well but comes with no guarantee. Nearest-neighbour builds a tour by always going to the closest unvisited city; 2-opt then repeatedly reverses a segment of the tour whenever that shortens it, stopping at a local optimum. Simulated annealing, tabu search and genetic algorithms are more elaborate ways of escaping local optima.
import random
from itertools import combinations
def matching_cover(edges):
"""The 2-approximation: take both ends of any edge not yet covered."""
cover = set()
for u, v in edges:
if u not in cover and v not in cover:
cover |= {u, v}
return cover
def greedy_degree_cover(n, edges):
"""A natural heuristic with no constant-factor guarantee: repeatedly take the busiest vertex."""
remaining, cover = set(edges), set()
while remaining:
degree = {}
for u, v in remaining:
degree[u] = degree.get(u, 0) + 1
degree[v] = degree.get(v, 0) + 1
best = max(sorted(degree), key=degree.get)
cover.add(best)
remaining = {e for e in remaining if best not in e}
return cover
def optimum_cover_size(n, edges):
"""The exact answer by brute force, smallest subsets first: exponential, fine for n <= 16."""
for size in range(n + 1):
for subset in combinations(range(n), size):
s = set(subset)
if all(u in s or v in s for u, v in edges):
return size
rng = random.Random(42)
worst = 0
print(" n edges optimum matching greedy")
for trial in range(8):
n = rng.randint(10, 14)
edges = [(u, v) for u, v in combinations(range(n), 2) if rng.random() < 0.3]
rng.shuffle(edges)
opt = optimum_cover_size(n, edges)
m, g = len(matching_cover(edges)), len(greedy_degree_cover(n, edges))
worst = max(worst, m / opt)
print(f"{n:2} {len(edges):6} {opt:8} {m:9} {g:7}")
print(f"worst matching ratio seen: {worst:.2f} (the theorem promises at most 2)")Look at the columns. The algorithm with the guarantee is noticeably worse on these random graphs than the greedy heuristic without one, which hits the optimum every time here. This is common: a worst-case guarantee protects you against the worst input, while a heuristic is tuned for typical ones. (Greedy-by-degree can be forced to be a logarithmic factor away from optimal on specially built graphs.) In practice engineers often run both, and use the guarantee's lower bound, , to tell how close the heuristic's answer must be.
4. Solve it exactly anyway, cleverly
Exponential does not mean hopeless. The Held–Karp dynamic programme solves TSP in time instead of trying all tours, the subset version of the ideas in Dynamic programming. Branch and bound explores a search tree but prunes any branch whose lower bound already exceeds the best solution found.
import math, random
rng = random.Random(7)
n = 12
pts = [(rng.uniform(0, 100), rng.uniform(0, 100)) for _ in range(n)]
d = [[math.dist(p, q) for q in pts] for p in pts]
def length(tour):
return sum(d[tour[i]][tour[(i + 1) % len(tour)]] for i in range(len(tour)))
def nearest_neighbour(start=0):
tour, left = [start], set(range(n)) - {start}
while left:
nxt = min(left, key=lambda j: d[tour[-1]][j])
tour.append(nxt)
left.remove(nxt)
return tour
def two_opt(tour):
"""Local search: reverse a segment whenever that shortens the tour; stop at a local optimum."""
tour, improved = tour[:], True
while improved:
improved = False
for i in range(1, n - 1):
for j in range(i + 1, n):
a, b, c, e = tour[i - 1], tour[i], tour[j], tour[(j + 1) % n]
if d[a][c] + d[b][e] < d[a][b] + d[c][e] - 1e-12:
tour[i:j + 1] = reversed(tour[i:j + 1])
improved = True
return tour
def held_karp():
"""Exact dynamic programme over subsets: O(n^2 2^n) time instead of (n-1)! tours."""
best = {(1, 0): 0.0} # (visited cities as a bitmask, last city) -> shortest path from city 0
for mask in range(1, 1 << n):
if not mask & 1:
continue
for last in range(n):
if (mask, last) not in best:
continue
for nxt in range(n):
if mask & (1 << nxt):
continue
key = (mask | (1 << nxt), nxt)
cand = best[mask, last] + d[last][nxt]
if cand < best.get(key, math.inf):
best[key] = cand
full = (1 << n) - 1
return min(best[full, last] + d[last][0] for last in range(1, n))
nn = nearest_neighbour()
opt2 = two_opt(nn)
exact = held_karp()
print(f"nearest neighbour: {length(nn):6.1f} ({length(nn) / exact - 1:+.1%} vs optimum)")
print(f"after 2-opt: {length(opt2):6.1f} ({length(opt2) / exact - 1:+.1%} vs optimum)")
print(f"optimum (Held-Karp): {exact:6.1f}")
print(f"brute force would check {math.factorial(n - 1) // 2:,} distinct tours")On this instance 2-opt happens to reach the optimum; on larger ones it typically lands within a few per cent. The state of the art combines everything: the Concorde solver, using linear-programming bounds and branch-and-cut, has found and proved optimal a tour through 85,900 points arising from a chip-manufacturing problem.
5. Hand it to a solver
For most engineers, coping means modelling. You describe the problem in a solver's language and let decades of engineering do the search.
- SAT solvers (MiniSat, CaDiCaL, Kissat and others, compared yearly at the SAT Competition) routinely solve industrial formulas with millions of clauses. They verify hardware designs, find bugs in software by bounded model checking, schedule, and resolve package dependencies: libsolv, which several Linux distributions' package managers use, is a SAT-based resolver.
- Integer linear programming (ILP) solvers (HiGHS and SCIP, which are open source, and commercial ones such as Gurobi and CPLEX) minimise a linear objective subject to linear constraints with integer variables. Airline crew scheduling, vehicle routing, power-grid planning and chip floor-planning are solved this way every day.
- Constraint programming tools, such as the CP-SAT solver in Google's OR-Tools, combine both styles.
The skill is in the model: choosing variables and constraints so that the solver's propagation and bounds are strong. A worst case that is exponential in theory may never appear in your data.
Optional Christian reflection · Knowing your limits
A reflection from the Christian tradition that inspires Lumenary Academy. It is not part of the mathematics and you are welcome to skip it.
There is a kind of freedom in an impossibility result. An engineer who has proved her scheduling problem NP-hard has not failed; she has learned the shape of the ground she stands on, and can now spend her effort where it will bear fruit, on good-enough answers, honest bounds and the structure of the real data. Many traditions, Christianity among them, treat knowing one's limits as the beginning of wisdom rather than its end. The mathematics here is the same for every reader; what you make of a limit is your own.
Common misconceptions
Misconception
"NP stands for non-polynomial." It stands for nondeterministic polynomial. Every problem in P is also in NP. "NP-hard" is the phrase for "at least as hard as everything in NP".
Misconception
"NP-complete means it cannot be solved in practice." It means no known algorithm is polynomial on every input. SAT solvers handle huge real formulas; Concorde solves TSP instances with tens of thousands of cities exactly. Conversely, a small but nasty instance can defeat any solver.
Misconception
"To show my problem is hard, I reduce it to SAT." That is backwards: it shows SAT can express your problem. To show hardness, reduce a known NP-hard problem to yours.
Misconception
"Quantum computers will solve NP-complete problems." No efficient quantum algorithm for any NP-complete problem is known, and most researchers believe none exists. Grover's search gives only a square-root speed-up over brute force, which turns into : still exponential.
Misconception
"An exponential algorithm is always worse than a polynomial one." Asymptotically, yes. For the sizes you actually have, beats until is in the tens of thousands. Measure on real inputs.
Exercises
1. Hard problems: P, NP and coping
Warm-upHumanWhich of these are decision problems in the sense of the lesson? Select all that apply.
2. Hard problems: P, NP and coping
CoreHumanAssume only what is currently known (P versus NP is open). Which statements are true? Select all that apply.
3. Hard problems: P, NP and coping
CoreHumanYou suspect that your new problem EXAM-SLOTS (assigning exams to time slots with constraints) is NP-hard. Which argument proves it?
4. Hard problems: P, NP and coping
Warm-upComputationalWrite the NP verifier for SAT. satisfies(clauses, assignment) receives a CNF formula as a list of clauses, each a list of nonzero integers (3 means , -3 means ), and a dictionary mapping each variable number to True or False. Return True exactly when every clause contains at least one literal made true by the assignment. An empty clause can never be satisfied; an empty formula (no clauses) is always satisfied.
5. Hard problems: P, NP and coping
CoreHumanUsing the lesson's reduction from -colouring to SAT (at least one colour per vertex, at most one colour per vertex, neighbours differ), how many clauses does the formula have for a graph with 5 vertices and 7 edges when ?
6. Hard problems: P, NP and coping
Warm-upHumanYou run the lesson's matching algorithm for vertex cover on a large graph, and it returns a cover of 18 vertices. What is the smallest the optimal vertex cover could possibly be?
7. Hard problems: P, NP and coping
CoreComputationalImplement approx_vertex_cover(edges), the 2-approximation from the lesson. edges is a list of pairs (u, v). Return a set of vertices that covers every edge and has at most twice as many vertices as the smallest cover. (The tests compare against a brute-force optimum on small random graphs.)
8. Hard problems: P, NP and coping
StretchComputationalCoping by parameter: write has_cover(edges, k) that returns True exactly when the graph has a vertex cover of at most k vertices. Use the branching idea from the lesson: if there are no edges, the answer is yes; if k == 0 and edges remain, no; otherwise pick any edge (u, v); one of u or v must be in the cover, so try both (remove every edge touching the chosen vertex and recurse with k - 1). This takes time, fast for small k even on big graphs.
Further reading and resources
- P vs NP · Clay Mathematics InstituteThe Millennium Prize problem statement and Stephen Cook's official description.
- The complexity of theorem-proving procedures · Stephen A. Cook · 1971The paper that showed SAT is NP-complete.
- Reducibility among combinatorial problems · Richard M. Karp · 1972Twenty-one natural problems shown NP-complete by reductions.
- A (slightly) improved approximation algorithm for metric TSP · Anna R. Karlin, Nathan Klein and Shayan Oveis Gharan · 2021
- Concorde TSP solverThe exact solver behind the largest solved TSP instances, with the story of the 85,900-city tour.
- The international SAT CompetitionWhere SAT solvers are compared every year, with benchmark sets and solver sources.
- HiGHSAn open-source solver for linear and mixed-integer programming.
- Google OR-ToolsOpen-source routing, scheduling and constraint-programming tools, including the CP-SAT solver.