Exact Exponential Algorithms

Most complexity courses end with a sobering verdict: if a problem is NP-hard, no algorithm is known that solves it in polynomial time. But they often stop there, leaving the impression that all you can do is try every possibility — brute force.

That's wrong. A whole field, exact exponential algorithms, has spent decades shaving the base of the exponent. Brute force for a problem on n objects might need $2^{n}$ steps. A cleverer algorithm might need only 1.$4^{n}$, or 1.$33^{n}$, or even lower. Each decimal point you shave off the base translates into enormous practical gains.

Consider 3-coloring: given a graph of n vertices, decide if you can color them with three colors so no two adjacent vertices share a color. The naive search inspects all $3^{n}$ ≈ 1.$73^{n}$ colorings. A smarter algorithm (Beigel & Eppstein, 2005) runs in $O(1.33^{n})$ — on 100 vertices that is roughly $10^{22}$ times faster. The problem is still NP-complete (proven by Karp in 1972), but the best algorithm is not brute force.

The same story plays out across dozens of NP-hard problems: TSP solved in $O(2^{n} \cdot n^{2})$ instead of $O(n! \cdot n)$ by Held & Karp (1962), SAT solved in $O(1.33^{n})$ by Monien & Speckenmeyer (1985), and hundreds of others catalogued in Exact Exponential Algorithms (Fomin & Kratsch, 2010). The field asks: what is the tightest possible base?

The demo below simulates solving a graph 3-colorability problem on n vertices. The brute-force approach tries all $3^{n}$ colorings (equivalent to $2^{n}$ after pruning symmetry, shown as the red bar). The optimized algorithm uses branch-and-reduce: it picks an uncolored vertex with the highest degree and tries its legal color options, pruning branches early — reducing the effective base to roughly 1.$33^{n}$.

Drag the slider to change n and watch the step counts diverge.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>n = <span id="nval">14</span> {{vertices}}
    <input type="range" id="slider" min="5" max="30" value="14">
  </label>
  <button id="run" type="button">{{run_btn}}</button>
</div>
<div class="bars" id="bars">
  <div class="bar-row">
    <span class="label">{{label_brute}}</span>
    <div class="track"><div class="fill red" id="bar-brute"></div></div>
    <span class="count" id="cnt-brute">—</span>
  </div>
  <div class="bar-row">
    <span class="label">{{label_opt}}</span>
    <div class="track"><div class="fill blue" id="bar-opt"></div></div>
    <span class="count" id="cnt-opt">—</span>
  </div>
</div>
<div class="result" id="result"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: 1rem; flex-wrap: wrap; margin-bottom: 1rem; }
label { font-size: .95rem; display: flex; align-items: center; gap: .5rem; }
input[type=range] { width: 160px; cursor: pointer; }
button { font: 600 14px system-ui; padding: .45rem 1rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:hover { background: #16294a; }
.bars { display: flex; flex-direction: column; gap: .7rem; margin-bottom: .9rem; }
.bar-row { display: grid; grid-template-columns: 140px 1fr 90px; align-items: center; gap: .5rem; }
.label { font-size: .82rem; color: #333; white-space: nowrap; }
.track { height: 22px; background: #e8eef3; border-radius: 6px; overflow: hidden; position: relative; }
.fill { height: 100%; border-radius: 6px; width: 0; transition: width .5s ease; }
.fill.red { background: #e63946; }
.fill.blue { background: #1d7ebc; }
.count { font: 700 .8rem ui-monospace, monospace; color: #333; text-align: right; white-space: nowrap; }
.result { font-size: .9rem; min-height: 1.4em; color: #0a7d33; font-weight: 600; }
.result.bad { color: #c92f3c; }

// Code not found

At small n the difference is modest. By n = 30 the brute-force count is in the billions while the optimized count stays in the thousands. This is the entire point of the field: the answer is the same (exact), but the work is orders of magnitude less.

Why does any of this work? Three main techniques drive the base below $2^{n}$:

1. Branch and reduce. The algorithm picks the "best" object (e.g. the vertex of highest degree), branches on the small number of choices for it (color 1, 2, or 3), and immediately prunes the search space using local rules. Each branch reduces n by more than one because the choice forces its neighbors. The recurrence T(n) = T(n-1) + T(n-2) + T(n-3) solves to roughly 1.$33^{n}$.

2. Dynamic programming over subsets. Held & Karp's TSP algorithm stores, for every subset S of cities and every city v ∈ S, the shortest path visiting exactly S and ending at v. The table has $2^{n}$ · n entries and each is computed in $O(n)$ time — giving $O(2^{n} \cdot n^{2})$ instead of the $O(n! \cdot n)$ brute force. The exponential base stays at 2, but compared to n! this is an astronomical improvement.

3. Measure and conquer. Assign each variable or vertex a weight that captures how much of the problem it "represents." When a branch reduces the weight by more than expected, the recurrence collapses to a smaller base. This technique underlies many of the record-breaking algorithms in the field.

The status of these problems:

• 3-coloring: NP-complete (Karp, 1972). Best exact algorithm: $O(1.33^{n})$ (Beigel & Eppstein, 2005).
• SAT: NP-complete (Cook, 1971). Best known exact: $O(1.33^{n})$ for 3-SAT (Monien & Speckenmeyer, 1985; improved by Paturi et al.).
• TSP: NP-hard. Held-Karp ($O(2^{n} \cdot n^{2})$, 1962) remains the asymptotically best known exact algorithm.
• Independent Set: NP-complete. Best exact: $O(1.2^{n})$ (Robson, 1986; refined by Fomin et al.).

None of these problems are believed to have polynomial algorithms, but the gap between the naive brute force and the best known exact algorithm can span many orders of magnitude. See also the related P vs NP problem and the Exponential Time Hypothesis.

You might wonder: if it's still exponential, who cares? In practice the difference between $2^{n}$ and 1.$33^{n}$ is the difference between impossible and feasible:

• Logistics and routing: TSP instances with dozens of cities arise daily in delivery planning, semiconductor chip testing, and DNA sequencing. Held-Karp's $O(2^{n} \cdot n^{2})$ makes exact solutions for n ≤ 25 routine on modern hardware.
• Bioinformatics: exact graph coloring underlies register allocation in compilers and frequency assignment in wireless networks. For small problem kernels extracted by preprocessing, exact algorithms run in practice.
• Drug discovery: finding maximum cliques (closely related to independent set) helps identify binding patterns in molecular graphs. Record-breaking exact algorithms have been used on graphs with thousands of vertices by exploiting sparsity.
• Parameterized complexity: exact exponential algorithms feed into the theory of fixed-parameter tractability — rewriting the exponential in terms of a small parameter (tree-width, vertex cover number) rather than the full input size. See the article on graph coloring for a related discussion.
• Proving lower bounds: the Exponential Time Hypothesis (ETH) conjectures that 3-SAT cannot be solved in $2^{o}$(n) time. If true, this would explain why decades of effort haven't broken the 1.$33^{n}$ barrier — and it implies hardness for a cascade of other problems.

Exact exponential algorithms reveal a beautiful truth: NP-hard does not mean structureless. Every technique — branch and reduce, subset DP, measure and conquer — exploits some hidden regularity to prune the search and push the base below 2.

The field is still alive and competitive. Record bases keep falling for problem after problem. And the central open question — whether some problems have a true 2^Ω(n) lower bound (as the ETH predicts) — remains unresolved.

Next time you hear "it's exponential, so it's hopeless," remember: the gap between $2^{n}$ and 1.$33^{n}$ is the difference between the age of the universe and a few hours of computing. That gap is what exact exponential algorithms are all about — and understanding it is understanding the very texture of P vs NP.