exact exponential algorithms
Some problems are NP-hard, so (unless P = NP) every algorithm that solves them EXACTLY, on every input, must take exponential time in the worst case. Many responses give up exactness — approximation, heuristics, randomization. Exact exponential algorithms refuse to: they insist on the provably correct, optimal answer, and instead fight to make the unavoidable exponential as slow-growing as possible. The goal is not to escape exponential time but to shrink its base — turning a hopeless 2^n into a merely difficult 1.3^n, which can be the difference between solving n = 40 and solving n = 100.
The baseline for many problems is brute force: try all 2^n subsets, all n! orderings. Exact exponential algorithms beat this base through cleverness while keeping correctness. Three signature techniques: (1) Dynamic programming over subsets — the Held-Karp algorithm solves the Traveling Salesman Problem in O(2^n * n^2) instead of O(n!), by remembering, for each subset of cities and each endpoint, the best path visiting exactly that subset; 2^n is astronomically smaller than n! for large n. (2) Branch-and-reduce — branch on a choice, but use reduction rules so each branch shrinks the instance a lot, provably bringing the base below 2 (independent set can be solved in about 1.2^n). (3) Inclusion-exclusion and meet-in-the-middle, which split the search to take a square root off the exponent (turning 2^n into roughly 2^(n/2) by solving two halves and combining). Each keeps an exact guarantee while lowering the growth constant.
Exact exponential algorithms matter because sometimes you genuinely need the optimum, not an approximation — verifying hardware, solving small but critical scheduling or routing instances, or proving a combinatorial fact — and the inputs, while NP-hard in general, are small enough that a smaller base makes them feasible. They also deepen our understanding of where exponential cost truly comes from. The honest caveats: these are still exponential, so they help only on modest n (dropping the base from 2 to 1.3 buys you maybe 2-3x more input, not unlimited scaling); a smaller base does not make the problem polynomial; and lowering the base often costs large polynomial factors or memory (Held-Karp needs 2^n memory), so the practical win must be weighed case by case.
Traveling Salesman by Held-Karp: instead of testing all n! tours, build a table dp[S][j] = shortest path starting at city 1, visiting exactly the set S, ending at city j. Fill it by trying each possible previous city. This runs in O(2^n * n^2) time and 2^n memory — for n = 20, 2^20 (about a million) is easy, whereas 20! (about 2.4 * 10^18) is impossible. Same exact answer, vastly smaller base.
Keep exactness; shrink the exponential base (n! -> 2^n, or 2^n -> 1.3^n). Feasible only for modest n.
These stay EXPONENTIAL — a smaller base (2 down to 1.3) does not make the problem polynomial; it just extends the feasible n by a constant factor. Lowering the base often costs heavy memory (Held-Karp uses 2^n space) or large polynomial factors, so the practical benefit is real but bounded.