Exponential Time Hypothesis: Watch the Blow-Up

Introduction

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.

Watch the Blow-Up

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">A random <b>3-SAT</b> instance with <span id="nlabel">8</span> variables.
    Brute force is the only sure method: try every true/false assignment and check the
    clauses. Each extra variable <b>doubles</b> the work — the curve you build below is
    the Exponential Time Hypothesis made visible.</p>
<div class="ctl">
  <label>Variables 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">Brute-force solve</button>
  <button id="reset" type="button" class="ghost">Clear chart</button>
</div>
<div class="status" id="status">Pick n, then brute-force solve.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Exponential Time Hypothesis demo. We brute-force 3-SAT: the only sure way to
// decide satisfiability is to try all 2^n assignments. The number of assignments
// checked is therefore (worst case) 2^n, doubling with every added variable.
// ETH (Impagliazzo-Paturi, 2001) conjectures no algorithm beats 2^(c*n) for some c>0.
function makeClauses(n){
  // A small random 3-SAT formula over n variables: ~4n clauses of 3 literals each.
  const m = Math.max(3, Math.round(4 * n)), cl = [];
  for(let i=0;i<m;i++){ const c=[]; while(c.length<3){
    const v = Math.floor(Math.random()*n), lit = (v+1)*(Math.random()<0.5?1:-1);
    if(!c.includes(lit) && !c.includes(-lit)) c.push(lit); } cl.push(c); }
  return cl;
}
// Evaluate a CNF formula under an assignment encoded as the bits of `mask`.
function satisfies(clauses, mask){
  for(const c of clauses){ let ok=false;
    for(const lit of c){ const v=Math.abs(lit)-1, val=(mask>>v)&1;
      if((lit>0 && val===1) || (lit<0 && val===0)){ ok=true; break; } }
    if(!ok) return false; }
  return true;
}
// Brute force: scan masks 0..2^n-1, count how many we examined before deciding.
function bruteForce(n, clauses){
  const total = Math.pow(2,n); let checked=0, sat=false, witness=-1;
  for(let mask=0; mask<total; mask++){ checked++;
    if(satisfies(clauses, mask)){ sat=true; witness=mask; break; } }
  return { checked, total, sat, witness };
}

const results = []; // {n, checked}
const $ = id => document.getElementById(id);
function setStatus(t,cls){ const s=$('status'); s.textContent=t; s.className='status '+cls; }

function drawChart(){
  const c=$('chart'); c.innerHTML='';
  if(!results.length) return;
  const max = Math.max(...results.map(r=>r.checked));
  for(const r of results){
    const col=document.createElement('div'); col.className='col';
    const h = Math.max(4, Math.round(120 * r.checked / max));
    col.style.height = h+'px';
    const lab=document.createElement('span'); lab.textContent = 'n='+r.n;
    col.appendChild(lab); c.appendChild(col);
  }
}

$('n').addEventListener('input', e=>{ const v=e.target.value; $('nval').textContent=v; $('nlabel').textContent=v; });
$('solve').addEventListener('click', ()=>{
  const n = parseInt($('n').value,10);
  const clauses = makeClauses(n);
  const r = bruteForce(n, clauses);
  $('bar').style.width = Math.min(100, 100 * r.checked / r.total) + '%';
  const verdict = r.sat ? 'SATISFIABLE' : 'UNSATISFIABLE';
  setStatus(fmt('n=%n%: checked %checked% of %total% assignments — %verdict%.', { n: n, checked: r.checked.toLocaleString(), total: r.total.toLocaleString(), verdict: verdict }), r.sat?'ok':'bad');
  results.push({ n, checked: r.checked });
  results.sort((a,b)=>a.n-b.n);
  drawChart();
  console.log('n='+n, 'assignments tried:', r.checked, '/ 2^'+n+'='+r.total, verdict);
});
$('reset').addEventListener('click', ()=>{ results.length=0; drawChart(); $('bar').style.width='0';
  setStatus('Pick n, then brute-force solve.',''); });

<p class="hint">A random <b>3-SAT</b> instance with <span id="nlabel">8</span> variables.
    Brute force is the only sure method: try every true/false assignment and check the
    clauses. Each extra variable <b>doubles</b> the work — the curve you build below is
    the Exponential Time Hypothesis made visible.</p>
<div class="ctl">
  <label>Variables 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">Brute-force solve</button>
  <button id="reset" type="button" class="ghost">Clear chart</button>
</div>
<div class="status" id="status">Pick n, then brute-force solve.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Exponential Time Hypothesis demo. We brute-force 3-SAT: the only sure way to
// decide satisfiability is to try all 2^n assignments. The number of assignments
// checked is therefore (worst case) 2^n, doubling with every added variable.
// ETH (Impagliazzo-Paturi, 2001) conjectures no algorithm beats 2^(c*n) for some c>0.
function makeClauses(n){
  // A small random 3-SAT formula over n variables: ~4n clauses of 3 literals each.
  const m = Math.max(3, Math.round(4 * n)), cl = [];
  for(let i=0;i<m;i++){ const c=[]; while(c.length<3){
    const v = Math.floor(Math.random()*n), lit = (v+1)*(Math.random()<0.5?1:-1);
    if(!c.includes(lit) && !c.includes(-lit)) c.push(lit); } cl.push(c); }
  return cl;
}
// Evaluate a CNF formula under an assignment encoded as the bits of `mask`.
function satisfies(clauses, mask){
  for(const c of clauses){ let ok=false;
    for(const lit of c){ const v=Math.abs(lit)-1, val=(mask>>v)&1;
      if((lit>0 && val===1) || (lit<0 && val===0)){ ok=true; break; } }
    if(!ok) return false; }
  return true;
}
// Brute force: scan masks 0..2^n-1, count how many we examined before deciding.
function bruteForce(n, clauses){
  const total = Math.pow(2,n); let checked=0, sat=false, witness=-1;
  for(let mask=0; mask<total; mask++){ checked++;
    if(satisfies(clauses, mask)){ sat=true; witness=mask; break; } }
  return { checked, total, sat, witness };
}

const results = []; // {n, checked}
const $ = id => document.getElementById(id);
function setStatus(t,cls){ const s=$('status'); s.textContent=t; s.className='status '+cls; }

function drawChart(){
  const c=$('chart'); c.innerHTML='';
  if(!results.length) return;
  const max = Math.max(...results.map(r=>r.checked));
  for(const r of results){
    const col=document.createElement('div'); col.className='col';
    const h = Math.max(4, Math.round(120 * r.checked / max));
    col.style.height = h+'px';
    const lab=document.createElement('span'); lab.textContent = 'n='+r.n;
    col.appendChild(lab); c.appendChild(col);
  }
}

$('n').addEventListener('input', e=>{ const v=e.target.value; $('nval').textContent=v; $('nlabel').textContent=v; });
$('solve').addEventListener('click', ()=>{
  const n = parseInt($('n').value,10);
  const clauses = makeClauses(n);
  const r = bruteForce(n, clauses);
  $('bar').style.width = Math.min(100, 100 * r.checked / r.total) + '%';
  const verdict = r.sat ? 'SATISFIABLE' : 'UNSATISFIABLE';
  setStatus(fmt('n=%n%: checked %checked% of %total% assignments — %verdict%.', { n: n, checked: r.checked.toLocaleString(), total: r.total.toLocaleString(), verdict: verdict }), r.sat?'ok':'bad');
  results.push({ n, checked: r.checked });
  results.sort((a,b)=>a.n-b.n);
  drawChart();
  console.log('n='+n, 'assignments tried:', r.checked, '/ 2^'+n+'='+r.total, verdict);
});
$('reset').addEventListener('click', ()=>{ results.length=0; drawChart(); $('bar').style.width='0';
  setStatus('Pick n, then brute-force solve.',''); });

Result

Console

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 Real Complexity

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."

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/exponential-time-hypothesis/Content licensed under CC BY-NC 4.0.

Cookies & privacy

The Exponential Time Hypothesis

Not just "no fast algorithm" — but exactly how slow