The Exponential Time Hypothesis

Everyone has heard of P vs NP: the question of whether problems like 3-SAT — "can these logical clauses all be made true at once?" — have a fast, polynomial-time algorithm. Almost everyone believes the answer is no. But that belief, even if proven, would leave a surprising amount unsaid.

Suppose 3-SAT really has no polynomial algorithm. How slow is it, exactly? Does it need $2^{n}$ steps, where n is the number of variables? Or might there be a clever method running in $2^{\sqrt{n}}$, or $2^{n/100}$, that is still technically exponential but vastly faster in practice?

P vs NP cannot tell these apart. The Exponential Time Hypothesis (ETH), proposed by Russell Impagliazzo and Ramamohan Paturi in 1999–2001, is a bolder bet that fills the gap: 3-SAT doesn't just lack a fast algorithm — it genuinely requires exponential time. That sharper claim turns out to unlock tight, concrete limits all across computer science.

Here is a tiny 3-SAT instance: a handful of clauses, each demanding that at least one of three literals be true. The only sure way to settle satisfiability is to try assignments of true/false to the variables. Drag the slider to change how many variables n there are, and the solver tries every combination.

<p class="hint">{{hint}}</p>
<div class="ctl">
  <label>{{label_n}} <input id="n" type="range" min="2" max="20" value="8"></label>
  <span class="val" id="nval">8</span>
</div>
<div class="btns">
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="meter"><div class="bar" id="bar"></div></div>
<div class="chart" id="chart"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.ctl { display: flex; align-items: center; gap: .6rem; margin: .3rem 0; font-size: .9rem; }
.ctl input[type=range] { flex: 1; max-width: 260px; }
.val { font: 700 16px ui-monospace, monospace; color: #1d3557; min-width: 2ch; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin: .4rem 0; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.meter { height: 10px; background: #e8eef3; border-radius: 6px; overflow: hidden; margin: .3rem 0 .8rem; }
.bar { height: 100%; width: 0; background: #e63946; transition: width .25s; }
.chart { display: flex; align-items: flex-end; gap: 4px; height: 130px; border-bottom: 2px solid #cdd9e3; padding-bottom: 2px; }
.col { flex: 1; min-width: 6px; background: #1d3557; border-radius: 3px 3px 0 0; position: relative; }
.col span { position: absolute; top: -16px; left: 50%; transform: translateX(-50%);
            font: 600 10px ui-monospace, monospace; color: #1d3557; white-space: nowrap; }

// Code not found

Watch the counter. Each extra variable doubles the number of assignments to check: n variables means up to $2^{n}$ tries. Add ten variables and the work grows by a factor of a thousand; add twenty and it's a million. The ETH says this wall is real — that for 3-SAT, no algorithm can sneak the exponent below a positive constant times n.

The Exponential Time Hypothesis is a conjecture — still open, and strictly stronger than P != NP. Here is what it actually says.

• The statement. ETH asserts that 3-SAT cannot be solved in $2^{o}$(n) time, where n is the number of variables. In words: there is some constant c > 0 such that every algorithm needs at least $2^{c \cdot n}$ steps. The clean "delta" version defines $s_{3}$ as the smallest such exponent and conjectures $s_{3}$ > 0.
• Stronger than P vs NP. If P = NP, the ETH is false. But the ETH could be false even while P != NP — there might be a sub-exponential-but-still-superpolynomial algorithm. So ETH implies P != NP, not the other way around. Proving or refuting it remains open.
• The Sparsification Lemma (Impagliazzo, Paturi, Zane, 2001) is the technical engine: it lets hardness measured in the number of variables transfer to the number of clauses, making the hypothesis robust and usable.
• SETH, the strong version. The Strong Exponential Time Hypothesis goes further: as the clause width k grows, the best exponent $s_{k}$ approaches 1, i.e. general SAT essentially needs the full $2^{n}$ with no constant-factor savings in the exponent. SETH is bolder and even more uncertain.

The punchline is that ETH is not a vague "it's hard" — it is a sharp, falsifiable number that, assuming it holds, lets us prove matching upper and lower bounds. It is to P vs NP what a speed limit is to "the road isn't infinitely fast."

A hypothesis is only as good as what it explains, and the ETH explains a great deal. Conditioned on it, complexity theorists derive exact difficulty thresholds that P vs NP alone cannot reach:

• Tight lower bounds. Assuming ETH, many famous NP-hard problems — graph coloring, Hamiltonian path, vertex cover — provably have no $2^{o}$(n) algorithm, matching their best-known solvers.
• Parameterized complexity. ETH rules out $n^{o}$(k)-time algorithms for problems like k-Clique, explaining why the parameter k must sit in the exponent.
• Fine-grained complexity. SETH yields lower bounds on everyday polynomial problems: under SETH, computing edit distance or the longest common subsequence in truly sub-quadratic time is impossible — a striking link from a logic conjecture to string algorithms.
• A unifying assumption. Like cryptography leaning on factoring being hard, a swath of modern complexity rests on ETH/SETH, so a single breakthrough would ripple everywhere.

In short, the ETH turns "we couldn't find anything faster" into "nothing faster can exist — if the hypothesis holds." That conditional honesty is exactly what makes it powerful.

P vs NP asks whether a road is fast. The Exponential Time Hypothesis asks how slow it really is — and dares to name the speed limit: 3-SAT needs time exponential in its variables, no clever $2^{o}$(n) shortcut allowed. It remains unproven, an open conjecture stronger than P != NP, yet it has become one of the most productive assumptions in the field.

The doubling you watched in the demo is its whole spirit: every variable is another factor of two, and the ETH bets that no algorithm ever tames that growth into something sub-exponential. If it is true — as nearly everyone suspects — then much of what feels slow really is slow, exactly and provably, and the guesses computers are forced into trace straight back to the same wall behind P vs NP.