Blog · November 6, 2026

What if exponential isn’t inevitable?

OpenAI reports a refutation of the Exponential Time Hypothesis. What the paper claims, what would fall with it, and how it relates to my work.

An exponential tree of 3-SAT assignments collapsing into a much smaller one, labelled 2 to the n becoming 2 to the little-o of n: subexponential time.

Early in the morning after the announcement, a friend from academia, now an assistant professor, woke me up with this message:

“Omer, did you hear that OpenAI announced last night that it has disproved the Exponential Time Hypothesis?”

I had to read it twice. This is an extraordinary announcement to take in, and it has direct implications for research I spent years working on. So I want to write down what is being claimed, what it would change, and what still has to happen before anyone treats it as settled.

SAT, k-SAT and CNF-SAT

A Boolean formula is built from variables x₁, …, x_n, each either true (1) or false (0). A literal is a variable or its negation, x or ¬x. A clause is an OR (∨) of literals, and a formula in conjunctive normal form (CNF) is an AND (∧) of clauses. An assignment satisfies the formula if every clause contains at least one true literal.

CNF-SAT asks whether a given CNF formula has a satisfying assignment. k-SAT is the same question when every clause has at most k literals. 2-SAT can be solved in polynomial time, while 3-SAT is the canonical NP-complete problem (Cook, 1971). The counting version, #SAT, asks how many satisfying assignments there are. Here is a small 3-CNF formula with n = 4 variables and two clauses:

F = (x_{1} \lor \neg x_{2} \lor x_{3}) \land (\neg x_{1} \lor x_{2} \lor x_{4})

The first clause is false only when x₁ = 0, x₂ = 1 and x₃ = 0. The second is false only when x₁ = 1, x₂ = 0 and x₄ = 0. Each of these leaves one variable free, so each rules out 2 of the 16 assignments, and the two pairs do not overlap. So F is satisfiable, for example by x₁ = x₂ = 1, and it has #F = 16 − 4 = 12 satisfying assignments.

x₁x₂ \ x₃x₄	00	01	10	11
00	✓	✓	✓	✓
01	✗ clause 1	✗ clause 1	✓	✓
10	✗ clause 2	✓	✗ clause 2	✓
11	✓	✓	✓	✓

All 16 assignments of F, with x₁x₂ along the rows and x₃x₄ along the columns. The four marked cells break a clause; the other 12 satisfy F.

With n variables there are 2ⁿ assignments, so checking them all takes about 2ⁿ steps. The whole question is how much better one can do.

What ETH says

The Exponential Time Hypothesis (ETH) was formulated by Russell Impagliazzo and Ramamohan Paturi more than 25 years ago. It says, roughly, that solving 3-SAT requires exponential time in the worst case. In symbols, 3-SAT on n variables needs time 2^Ω(n): there is a constant δ > 0 such that no algorithm decides every 3-CNF formula on n variables in time 2^δn.

Trying all 2ⁿ assignments is the obvious algorithm, and decades of clever work have brought the base down. The paper itself lists where things stood: about (1.307)ⁿ for randomized algorithms and (1.328)ⁿ for deterministic ones. Those are big improvements over 2ⁿ, but they are still exponential: (1.307)ⁿ = 2^0.386n, which is 2^δn with δ ≈ 0.386. ETH is the bet that some δ > 0 can never be beaten.

The Strong Exponential Time Hypothesis (SETH) makes a sharper bet. As the clause width k grows, k-SAT needs time close to 2ⁿ: for every ε > 0 there is a k for which k-SAT cannot be solved in time 2^(1−ε)n. SETH implies ETH, so if ETH is false, SETH is false too.

What OpenAI claims

OpenAI reports a disproof produced by one of its internal models, accompanied by a Lean formalization. Lean is a proof assistant: a language in which a proof is written out in full formal detail, so that a computer can check every step. The paper, The Exponential Time Hypothesis is False (dated October 17, revised October 25), gives a deterministic algorithm that does more than decide satisfiability. For every fixed k, it counts the satisfying assignments of any k-CNF formula with n variables and m clauses, in polynomial space and in time

{(n + m)}^{O (1)} \cdot 2^{E (n)}

where the exponent is

E (n) = O (\frac{n \log \log n}{\sqrt{\log n}})

The constants hidden in the O depend on k. The first factor is polynomial in the size of the input. In the second, E(n)/n is, up to a constant, $\log \log n / \sqrt{\log n}$ , which goes to 0 as n grows. So E(n) = o(n) and the running time is 2^o(n): subexponential. Checking whether the count is positive decides satisfiability, so the paper states that it refutes ETH and SETH, and also their counting, gap and nondeterministic versions (#ETH, Gap-ETH and NSETH).

This is a statement about asymptotics, not a practical speedup. Working from the paper’s own parameters, Stefan Szeider computed that the algorithm does nothing but exhaustive search until the number of variables plus clauses exceeds 2¹³¹⁰⁷¹.

OpenAI is not alone. Around the same time, Anthropic released an independent refutation of its own, with a different proof, also formalized in Lean. Two separate proofs of the same surprising statement are a large part of why the community takes the claim seriously.

The repository is upfront that this is early. It describes its manuscripts as produced by an unnamed internal OpenAI model and as “best understood as a form of raw research data, rather than polished academic papers.” If the claim holds up, a foundational assumption falls.

Why it matters

Why does this matter so much to computer scientists? Because mathematical reductions connect 3-SAT to many other problems, which lets us translate its conjectured hardness into limits on how fast those problems can be solved. For decades, researchers have used ETH to establish conditional lower bounds for problems such as 3-coloring, maximum clique, maximum independent set and Hamiltonian cycle. Each of those results says, in effect, “this problem has no substantially faster algorithm, unless ETH is false.” That condition is now in question.

It is worth being careful about what does not follow. A lower bound moves from 3-SAT to another problem through a reduction from 3-SAT to that problem. A faster algorithm moves in the opposite direction, and a 2^o(n) running time does not survive general polynomial-time reductions: a reduction may turn n variables into n², and 2^o(n²) need not be 2^o(n). The paper says so itself: the result does not imply that every NP problem has a subexponential algorithm. Nor does it settle P versus NP, since 2^o(n) is still far from polynomial. Where a reduction does go the right way, the paper gets new algorithms, for example counting the independent sets or the proper q-colorings of a graph on v vertices in 2^o(v) time.

Inside P

The implications also reach problems we already solve in polynomial time. SETH is the assumption behind many conditional quadratic-time barriers: edit distance, longest common subsequence, Dynamic Time Warping (DTW) and Fréchet distance, which are fundamental ways of comparing strings, time series and curves. The typical statement is that none of them can be solved in time n^2−ε for any ε > 0 unless SETH is false.

Refuting SETH removes that basis, but it does not hand us faster algorithms for these problems. The paper points out that some of the barriers also follow from weaker assumptions that may still hold. The bound for longest common subsequence also follows from the Orthogonal Vectors Conjecture, which SETH implies but which could survive without it. The bound for Fréchet distance also follows from a hypothesis about CNF-SAT with unbounded clause width, which an algorithm for fixed k does not touch. So the first job is to work out which of these barriers still stand, and on what.

How it relates to my work

Some of my own research sits close to these questions. During my PhD with Prof. Micha Sharir, we improved algorithms for 3SUM and found a slightly subquadratic algorithm for Dynamic Time Warping: our speedup shaved logarithmic factors off its quadratic running time. Lowering the exponent itself would have contradicted SETH, so we did not try.

That is part of why this result fascinates me. Conditional lower bounds quietly guide research: they suggest where effort is unlikely to pay off, and many of us chose problems, and where to stop, with them in mind. If SETH falls, some of those signals deserve a second look, starting, for me, with whether the quadratic barrier for DTW still holds under a weaker assumption.

One detail I did not expect touches 3SUM directly. The paper also refutes NSETH, a hypothesis that had been used to argue that hardness for 3SUM and All-Pairs Shortest Paths cannot be derived from SAT through deterministic fine-grained reductions. With NSETH gone, that barrier no longer applies, and the question of how SAT, 3SUM and APSP relate is open again.

I am also drawn to the method itself. It uses classic tools of algebraic algorithm design (counting with polynomials, splitting a sum into independent pieces, interpolation), combined in a new way. That an AI model found this combination is the part I keep coming back to.

This also follows the recent Anthropic-linked breakthrough on truly subquadratic 3SUM and truly subcubic APSP, and OpenAI’s claimed proof of the Unique Games Conjecture, which the ETH paper already cites as the “Unique Games Theorem”. Each deserves a post of its own.

How the algorithm works

This part is more technical. If you would rather skip it, jump to What comes next. Here is the idea of the proof, following the overview in Section 2 of the paper.

Step 1: a polynomial that counts

Each clause e becomes a small polynomial, which we call Φ_e, that equals 1 when the clause is satisfied and 0 when it is not. For the first clause of our example:

(x_{1} \lor \neg x_{2} \lor x_{3}) \mapsto 1 - (1 - X_{1}) X_{2} (1 - X_{3})

It is 0 exactly when x₁ = 0, x₂ = 1 and x₃ = 0, the assignments that break the clause. Multiplying the clause polynomials gives 1 on a satisfying assignment and 0 otherwise, so the count is one big sum:

# F = \sum_{x \in {0, 1}^{n}} \prod_{e} Φ_{e} (x)

The sum still has 2ⁿ terms. The rest of the proof is about evaluating it faster.

Step 2: the case that would be easy

Suppose the variables could be split into groups S₁, …, S_r, with every clause using variables from a single group. Then the groups do not interact: count the satisfying assignments N_g inside each group by brute force, and multiply.

# F = \prod_{g = 1}^{r} N_{g}

Each group is searched on its own, which is far faster than trying all 2ⁿ assignments.

Every clause inside one group: #F = N₁ · N₂ · N₃.

Clauses that cross groups (dashed) tie the groups together, and the sum no longer factors.

Real formulas do not split like this, and the paper does not assume they do. The next step makes them behave as if they did.

Step 3: deform the formula, then measure

The paper introduces a new variable T. It is a single number, not a vector: think of it as a dial. Each input of each clause is replaced by a combination of all the variables, whose coefficients are polynomials in T. That list of coefficients, one per variable, is the vector. At T = 0 the combinations are the original variables, so the new sum, H(T), still gives the count there: H(0) = #F.

A toy version shows the idea at a single point, T = 2. Suppose our example clause is evaluated in one group, but x₂ lives in another group, and y is one of that group’s measurements (defined below). Replace the input X₂ by

(1 - T / 2) \cdot X_{2} + (T / 2) \cdot y

At T = 0 this is X₂, so nothing changes. At T = 2 it is y, so the clause no longer reads X₂ directly, only the measurement. The value changes, and that is fine: at T ≠ 0, H(t) is not a count of anything, just a number that is fast to compute. The paper does this for every clause and every point T = 1, …, Q at once, while keeping the coefficients polynomials of low degree. That construction, in its Section 4, is the hard part.

At the points T = 1, 2, …, Q, the combinations are chosen so that a clause sees the other groups only through a few measurements y_g: fixed combinations of each group’s variables with small integer coefficients. Fix the values of all the measurements, and the groups separate again:

H (t) = \sum_{y} \prod_{g = 1}^{r} B_{t, g} (y)

Here B_t,g(y) is a sum over the assignments of group g alone. The measurements take few possible values, so this is fast.

A clause is evaluated inside its assigned group, here S₂. It may still depend on S₁ and S₃, but only through their measurements y₁ and y₃, a few small integers each.

Step 4: interpolate back to T = 0

H(T) is a polynomial in T of known degree. Its values and first few derivatives at T = 1, …, Q pin it down completely, and with it the one value we cannot compute directly, H(0) = #F.

The filled points and their tangents at T = 1, …, Q stand for what the algorithm computes there: values and several derivatives. Together they determine H, and with it the one value we cannot compute directly: H(0) = #F.

The rest is balancing: the number of groups, of measurements and of points has to be chosen so that the total cost stays 2^o(n). The paper’s choices achieve this in polynomial space, and a sharper analysis in the paper brings the bound to the one quoted above, $E (n) = O (n \log \log n / \sqrt{\log n})$ . For the full argument, Section 2 of the paper is a readable overview.

What comes next

There is serious work ahead. Russell Impagliazzo, Ramamohan Paturi and Ryan Williams have been asked to organize an open, independent examination of the claim; Impagliazzo and Paturi helped formulate the hypothesis in the first place. In their open letter they write that their involvement “should not be taken as certification of the claim.”

In practice, the community is already treating the result as very likely correct. Researchers have re-checked both labs’ formal proofs with independent tools, connected them to a standard Turing-machine model, and written shorter proofs. On the examination blog, people are already posting consequences, from new parameterized algorithms to classical simulation of quantum circuits. What remains is mostly understanding: why the construction works, how far it extends, and which of the lower bounds built on ETH and SETH fall and which survive on weaker assumptions.

But I keep returning to that morning message. An assumption that helped shape decades of research may have fallen, and AI may have found the way through.

We are living through the most significant technological revolution in human history.

Sources

OpenAI’s announcement (openai.com)
The paper: The Exponential Time Hypothesis is False (PDF on GitHub)
The repository: github.com/openai/math
The community examination, organized by Impagliazzo, Paturi and Williams: ethdiscussion.blog
Omer Gold and Micha Sharir, Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier (ICALP 2017, TALG 2018)
Omer Gold and Micha Sharir, Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy (ESA 2017)