Impagliazzo and Paturi’s 1999 bet: 3-SAT needs truly exponential time. The strong version, the sparsification lemma, and what follows
P ≠ NP says 3-SAT has no polynomial-time algorithm. Russell Impagliazzo and Ramamohan Paturi made a sharper bet in 1999: no algorithm for 3-SAT runs in subexponential time — not 2^(√n), not 2^(n/log n). Some 2^(δn) with δ > 0 is unavoidable. It is still a hypothesis, unproved, but a remarkably productive one.
Sweep across the chart to compare the best algorithms for each clause width k, then switch between the ETH and SETH worlds to see what each hypothesis would forbid.
A bound 2^(r·n) is plotted at height r: 1 is brute force, 0 is subexponential. The solid lines are proved algorithms (Schöning 1999; PPSZ with Hertli’s 2011 analysis), so they are upper bounds on the true exponent s_k. Rose shading is what a hypothesis would forbid — the true s_k lies between the shading and the lowest line. The blue column is 2-SAT, which is in P.
For each k, let s_k be the infimum of all δ such that k-SAT on n variables can be solved in time 2^(δn) times a polynomial. Brute force shows s_k ≤ 1, and 2-SAT is in P, so s₂ = 0. The Exponential Time Hypothesis, formulated by Impagliazzo and Paturi (1999; journal version 2001), is the statement s₃ > 0: equivalently, 3-SAT cannot be solved in time 2^(o(n)). The Strong Exponential Time Hypothesis, from the same paper and named later (for example by Calabro, Impagliazzo and Paturi in 2009), says that s_k tends to 1: for every ε > 0 there is a k such that k-SAT cannot be solved in time 2^((1−ε)n). SETH implies ETH.
What is proved about the sequence is modest. It is nondecreasing, and Impagliazzo and Paturi showed that if ETH holds, s_k increases infinitely often — wider clauses really do get harder. The algorithms on the chart are upper bounds: Schöning’s random walk gives (2 − 2/k)ⁿ, and PPSZ does a little better, about 1.307ⁿ for 3-SAT. Both save a fraction of the exponent that shrinks like 1/k. That pattern is the evidence behind SETH; it is not a proof, and some researchers doubt SETH while believing ETH.
Why call it a hypothesis rather than try to prove it? ETH implies P ≠ NP — a 2^(o(n)) lower bound rules out polynomial time in particular — so proving ETH is at least as hard as the most famous open problem in the field. Its value is as a precise quantitative assumption: from it follow lower bounds that match the best algorithms surprisingly often, as the last demo shows. Daniel Lokshtanov, Dániel Marx and Saket Saurabh surveyed the method in “Lower bounds based on the Exponential Time Hypothesis” (2011).
Press Step to branch on the highlighted sunflower, or Play to grow the whole tree. Then lower the thresholds: the leaves get sparser, but there are more of them.
Each disc is a formula, labelled with its clause count; pink edges add the heart as a clause, blue edges replace the sunflower by its petals. In the clause list the heart is pink and the petals blue. Leaves are green if they have solutions, grey if not, rose if they contain a unit clause and its negation. Hollow discs are waiting to branch. Our threshold rule is a small-scale version of IPZ’s: it bounds every leaf by 2n·θ₂/3 + n·θ₁ + 2n clauses. At n = 12 the leaf count is large compared with 2ⁿ; the lemma’s 2^(εn) is an asymptotic guarantee, with constants that only pay off for much larger n.
Impagliazzo, Paturi and Francis Zane proved in 2001 that for every k and every ε > 0, a k-CNF formula on n variables can be written as the OR of at most 2^(εn) k-CNF formulas, each with at most c(k, ε)·n clauses, and these can be listed in time 2^(εn) times a polynomial. The engine is the one in the demo: find many clauses sharing a common part, the heart, and branch. Either the heart is true, and all those clauses collapse into one shorter clause, or it is false, and each clause shrinks to its petal. Both branches only add consequences, so no solution is lost and none is invented. The idea echoes the Erdős–Rado sunflower lemma (1960): any family of more than k!·(p − 1)^k sets of size k contains p sets with a common core and otherwise disjoint petals.
Why it matters: reductions from 3-SAT usually build an instance whose size grows with the number of clauses m, not the number of variables n, and m can be as large as n³. A 2^(o(N)) algorithm for the target would then only give 2^(o(m)) for 3-SAT, which says nothing about n. After sparsification m = O(n), so ETH can be stated equivalently in m: 3-SAT has no 2^(o(m)) algorithm. Any reduction of size O(n + m) then carries the 2^(o(·)) lower bound across. The same lemma shows that ETH for k-SAT, for any fixed k ≥ 3, are all equivalent statements.
The demo’s version is small-scale: it uses two thresholds, θ₁ for one-literal petals and θ₂ for two-literal petals, and only removes subsumed clauses. The real lemma chooses thresholds that grow quickly with the petal size, which is what makes the number of leaves 2^(εn) for large n. At n = 12 that guarantee has not kicked in, but the invariant — the original solutions are exactly the union of the leaves’ — is checked live on every run.
Click a problem to follow the chain of reductions from 3-SAT and compare the lower bound it inherits with the best known algorithm. Then press “If ETH were false”.
Arrows are reductions, coloured by how much they enlarge the instance; the highlighted path carries the lower bound from 3-SAT to the selected problem. In the chart, log₂ of the running time is plotted against size, so 2^(cN) is a straight line and 2^(c√N) a square-root curve. The dashed rose line is the shape ETH forbids going below — its constant is unknown, so its slope is illustrative — and amber is the best known algorithm (its constant drawn schematically). “If ETH were false” removes the foundation: bounds equivalent to ETH become false, the rest become open questions, and every algorithm still stands.
Under ETH, 3-Colouring, Independent Set, Vertex Cover, Clique, Hamiltonian Cycle and Dominating Set on N vertices have no 2^(o(N)) algorithm, and Subset Sum on n numbers has no 2^(o(n)) algorithm. The best known algorithms are exponential too — 3-Colouring in O(1.3289ᴺ) (Beigel and Eppstein, 2005), Subset Sum in 2^(n/2) by meet in the middle (Horowitz and Sahni, 1974) — so the bounds match up to the base of the exponential. Without ETH we cannot even rule out 2^(√N) for any of them.
Planar graphs show the “square-root phenomenon”. Reducing to a planar problem replaces every crossing with a gadget, and a drawing can have quadratically many crossings, so the lower bound weakens to 2^(o(√N)). And that is exactly right: the planar separator theorem of Richard Lipton and Robert Tarjan (1979, with applications in 1980) splits a planar graph with a separator of O(√N) vertices, giving 2^(O(√N)) algorithms. For parameterized problems the same reasoning gives finer answers: Jianer Chen, Xiuzhen Huang, Iyad Kanj and Ge Xia showed in 2006 that, under ETH, k-Clique has no f(k)·n^(o(k)) algorithm, while Nešetřil and Poljak’s 1985 method finds one in n^(ωk/3), using fast matrix multiplication.
In October 2026 two AI labs posted claimed refutations of ETH: OpenAI (“The Exponential Time Hypothesis is False”) and Anthropic (“A 2^(o(n)) Time Algorithm for 3-SAT”, written by Claude). Both describe deterministic algorithms that count the satisfying assignments of k-CNF formulas in time roughly 2^(O(n·log log n/√log n)), both come with Lean formalizations, and neither has been peer reviewed; an independent working group led by Impagliazzo, Paturi and Ryan Williams is examining OpenAI’s. The claims are unverified and under review. If they hold, ETH and SETH are both false and every derived lower bound above loses its foundation — though not one of the algorithms changes. See also: A Claimed Refutation.
Spot a mistake or have an idea?