Exact Exponential Algorithms
Every other page in this module bought speed by
giving
something up — optimality, generality, determinism. Sometimes you can afford none of that.
You need the provably optimal tour, the exact number of colourings, the true
minimum — on a general input, deterministically. Then the only hinge left to loosen is
polynomial time itself: accept an exponential algorithm, but make the exponential as
gentle as humanly possible.
This is not surrender to brute force — it is a craft. The gap between the naive
n! of "try every permutation" and a tuned 2^n or
1.2^n is not a constant factor; it is the difference between instances you
can never solve and instances you solve before the coffee cools. Exact exponential algorithms are the
science of shrinking the base and the exponent.
$2^n$ is not $n!$ — the gulf is everything
"They're both exponential, who cares about the base?" — a costly instinct. Watch what actually happens
as n grows. Held–Karp will solve TSP in roughly 2^n
steps; naive permutation search takes n!:
| n | 2^n (subset DP) | n! (all tours) | Ratio n!/2^n |
|---|
| 10 | 1,024 | 3,628,800 | ≈ 3.5 thousand |
| 15 | 32,768 | 1.3 × 10¹² | ≈ 40 million |
| 20 | 1.05 × 10⁶ | 2.4 × 10¹⁸ | ≈ 2.3 × 10¹² |
| 25 | 3.4 × 10⁷ | 1.55 × 10²⁵ | ≈ 4.6 × 10¹⁷ |
| 30 | 1.07 × 10⁹ | 2.65 × 10³² | ≈ 2.5 × 10²³ |
At n = 30, 2^n is a billion — a second or two —
while n! exceeds the number of atoms in a galaxy. Both are "exponential" and
both are hopeless as n \to \infty, but for the finite instances on your desk
the base and even the polynomial factor decide whether the problem is solved or abandoned. Shaving
2^n to 1.9^n can double the reachable
n.
Held–Karp: dynamic programming over subsets
The naive TSP tries all n! orderings. The
dynamic-programming
insight is that a partial tour only needs to remember which cities have been visited and
where it currently is — not the order it visited them. That collapses n!
histories into 2^n \cdot n states.
Let C(S, j) = the cost of the cheapest path that starts at city
1, visits exactly the set S, and ends at
j \in S. Then
C(S, j) = \min_{i \in S \setminus \{j\}} \Big( C(S \setminus \{j\},\, i) + d(i, j) \Big),
with 2^n subsets S, n
choices of endpoint j, and an O(n) minimisation
each — total O(2^n n^2) time and O(2^n n) space.
// Held–Karp TSP: O(2^n · n^2) time using bitmask subsets.
function heldKarp(d: number[][]): number {
const n = d.length;
const C = Array.from({ length: 1 << n }, () => new Array<number>(n).fill(Infinity));
C[1][0] = 0; // start at city 0, set = {0}
for (let S = 1; S < (1 << n); S++) {
if (!(S & 1)) continue; // subsets must contain city 0
for (let j = 0; j < n; j++) {
if (!(S & (1 << j)) || C[S][j] === Infinity) continue;
for (let k = 0; k < n; k++) { // extend the path to a new city k
if (S & (1 << k)) continue;
const T = S | (1 << k);
C[T][k] = Math.min(C[T][k], C[S][j] + d[j][k]);
}
}
}
const full = (1 << n) - 1;
let best = Infinity;
for (let j = 1; j < n; j++) best = Math.min(best, C[full][j] + d[j][0]);
return best; // exact optimum
}
Exponential space is the catch — 2^n n table entries — so Held–Karp is
practical to roughly n \approx 20. The same subset-DP idea solves graph
colouring, Hamiltonicity, and Steiner tree in 2^n-ish time.
Three more ways to tame the exponential
- Branch and bound. Explore the search tree of choices, but at each node compute a
cheap bound on the best completion; if the bound is worse than the best solution found so
far, prune the whole subtree. Worst case still exponential, but pruning routinely turns
gigantic trees into tractable ones — this is how real TSP and integer-programming solvers reach
tens of thousands of cities.
- Inclusion–exclusion. Count (or detect) structures by summing over subsets with
alternating signs. Counting Hamiltonian paths, or the chromatic polynomial's evaluations, drops
from super-exponential to O^*(2^n) — often a one-line formula replacing a
search.
- Measure and conquer. A sharper way to analyse branching algorithms:
instead of measuring progress by raw instance size, assign carefully chosen weights to vertices (by
degree, say) so the recurrence solves to a smaller base. The same algorithm, re-analysed,
provably runs in 1.22^n instead of a naive 1.4^n
— the cleverness is in the accounting, not the code.
(The O^* notation hides polynomial factors, keeping attention on the
exponential base — the thing that actually decides feasibility.)
Asymptotically, yes: 2^n and n! both blow past any
polynomial, and neither scales to n = 10^6. But "intractable in the limit" and
"unsolvable in practice" are different claims. Enormous swaths of real optimisation live at
n = 30 to 60, where a 1.2^n
exact algorithm finishes in seconds and a 2^n one in hours — while
n! was never on the table. Complexity theory studies the tail; engineering
lives in the body of the distribution. Lowering the base of the exponential is one of the most
practically valuable things an algorithm designer can do, even though it changes nothing about
\text{P} versus \text{NP}.
It is tempting to reach for Held–Karp whenever n is "smallish," but its
O(2^n n) space bites long before its time does. At
n = 25 the table has \approx 8 \times 10^8 entries
— gigabytes — and at n = 30 it simply won't fit in memory, even though
2^{30} \approx 10^9 time steps would be fine. Past that wall, a
polynomial-space method — branch-and-bound, or divide-and-conquer over subsets — is the right
tool even if its time is a bit worse. With exact exponential algorithms, always check the space bound,
not just the time bound; memory is usually what kills you first.