OpenAI's ETH disproof explained: how an AI says it beat brute-force 3-SAT

For 27 years, computer scientists have treated one assumption as solid ground: the classic logic puzzle 3-SAT can't be solved much faster than an exponential-time search. On 26 October 2026, OpenAI said one of its internal models had knocked that assumption over. It published a 60-plus-page proof called "The Exponential Time Hypothesis is False" and a machine-checked Lean version. If it holds, it will rank among the most consequential results an AI system has produced so far. It doesn't speed up any software you use. What it changes is what researchers can claim is impossible.

The plain-English version

Picture a huge panel of light switches, each either on or off, plus a long list of rules like "switch 4 on, OR switch 17 off, OR switch 230 on." Your job is to find a setting of all the switches that satisfies every rule at once, or prove none exists. That is 3-SAT: each rule mentions at most three switches. It turns up everywhere, from chip design to scheduling, and many other hard problems can be translated into it.

The obvious method is to try every setting. With n switches there are 2ⁿ settings, so each extra switch doubles the work. With 300 switches, brute force already needs more steps than there are atoms in the observable universe. Clever methods do better, but every known method still doubled its work every few switches. The growth rate was smaller, but it was still exponential.

In 1999, Russell Impagliazzo and Ramamohan Paturi turned that pattern into a conjecture, the Exponential Time Hypothesis (ETH): no method, however clever, gets rid of the exponential growth. Researchers then built on it heavily. Hundreds of papers have the form "problem X can't be solved faster than this, unless ETH is false." ETH served as a floor that many results stood on.

OpenAI's claim is that the floor isn't there. Its model found a method that counts every valid setting of the switches, not just one, and whose work grows more slowly than any exponential. The method doesn't search smarter. It turns the counting question into algebra, warps the problem until it splits into many small independent pieces, solves the pieces, and then mathematically "unwarps" the answer.

A good analogy is a census. Counting a country's population door to door takes forever. But if you knew that each region interacts with the others only through a few numbers, such as how many people commute across each border, you could count each region on its own for every possible value of those numbers and multiply the results together. The proof's main achievement is making any 3-SAT problem look like that kind of country.

Three things to keep straight. First, it is only "faster" for astronomically large problems, so real solvers don't change. Second, it does not show P = NP, the famous million-dollar question. The new method is still far slower than "efficient" in the technical sense. Third, nobody outside OpenAI has confirmed it yet. Two of ETH's original proposers are among the people now organizing the review.

How it actually works

The problem. The paper states its main theorem for counting. For a formula with n variables and m clauses, it computes #F, the exact number of satisfying assignments. If the count is more than zero, the formula is satisfiable. The abstract claims time $(n+m)^{O_k(1)}\,2^{n/(\log n)^{1/2+o(1)}}$ and polynomial memory, for every fixed clause width k ≥ 2.

The old way. The best algorithms the paper surveys are all clever forms of search. Schöning's random walk solves 3-SAT in about (4/3)ⁿ steps. Descendants of the PPSZ algorithm get down to about 1.307ⁿ (randomized; a 2026 preprint by Jiang and Cai), and the best deterministic algorithm cited, Liu's mix of branching and derandomized local search, runs in 1.32793ⁿ. For counting, the best cited 3-SAT bound is 1.637ⁿ. Every one of these is cⁿ for a constant c. ETH said that pattern can't be beaten: the base c can shrink, but it never reaches 1.

The new idea, as a walkthrough.

1. Make the formula tame. A standard 2001 tool, the sparsification lemma, splits any 3-SAT formula into many sparse formulas. Copying variables then makes each variable appear in at most three clauses. Every satisfying assignment ends up in exactly one piece, so the counts add up.

2. Turn counting into a polynomial. Each clause becomes a small polynomial that equals 1 when the clause is satisfied and 0 when it isn't (for "a OR NOT b OR c" it is $1-(1-X_a)X_b(1-X_c)$). Multiplying all of them and summing over every 0/1 assignment gives exactly #F. That sum still has 2ⁿ terms, so nothing is gained yet.

3. Deform it with a dial. Each variable inside each clause is replaced by a linear combination of variables whose coefficients are polynomials in a new dial T. At T = 0 the replacement is just the original variable, so the deformed sum H(T) equals #F at T = 0.

4. Choose the deformation so the problem splits at other dial settings. At T = 1, 2, …, Q, the variables fall into small groups. Each deformed clause depends only on its own group plus a handful of integer measurements (fixed linear combinations) of the other groups. Fix all the measurement values and the giant sum factors into a product of small per-group sums. The algorithm loops over every possible measurement tuple. That loop is still exponential, but only in a tiny fraction of n.

5. Unwarp. H is a polynomial in T, so its values and first several derivatives at T = 1…Q pin it down completely, including its value at T = 0. This is Hermite interpolation. A separate inclusion–exclusion trick computes the derivatives with the same splitting machinery.

Why it beats every cⁿ. The running time multiplies three exponential costs: the number of measurement tuples, brute force inside a single group, and the number of derivative "probes" needed for interpolation. The paper tunes four parameters: the number of groups r, the number of points Q, the polynomial degree R, and the measurement budget. With those settings, each cost is 2 raised to n divided by something that grows with log n. Each extra variable adds a slightly smaller exponent than the one before, which is exactly what ETH ruled out.

The deep dive

The design condition

Write each clause occurrence's replacement as $\langle \vec P_{e,v}(T), \vec X\rangle$ with $\vec P_{e,v}(0)=\vec e_v$ and $\deg \vec P_{e,v}\le R$. Define

At each evaluation point t, the paper requires an (r, τ, D)-design. The variables are partitioned into groups $S_1,\dots,S_r$ of size at most 2n/r, each clause is assigned to one group, and each group carries an integer measurement matrix $C_g$, with at most 2τn rows in total and row ℓ₁-norm at most D. These must satisfy the condition that $\vec P_{e,v}(t)|_{S_h}$ lies in the row space of $C_h$ for every group h other than the clause's own. With $\vec y$ fixed, each $\Phi_e$ then reads only its own group, and

which costs about $(2D+1)^{2\tau n}\cdot 2^{2n/r}$ up to polynomial factors, with memory polynomial because groups are scanned one at a time.

Getting derivatives for free-ish

Values at Q points aren't enough, because deg H ≤ 3nR is much larger than Q. The algorithm therefore gets $J=\lfloor 3nR/Q\rfloor+1$ Taylor coefficients of $H(t+z)$ at each point. It separates the shift $\Delta\vec P(z)=\vec P(t+z)-\vec P(t)$ into a fresh formal vector $\vec X$. Every entry of $\Delta\vec P$ is divisible by z, so the coefficient of $z^j$ has degree at most j in $\vec X$. Multilinearizing and applying inclusion–exclusion over subsets $U\subseteq E$ with $|E|\le q$ expresses $H(t+z) \bmod z^J$ through sums in which $\vec X$ is fixed to an indicator vector $1_U$. Those sums are again separable by the design. This step costs about $\sum_{j\le q}\binom{n}{j}2^j\le (q+1)(2en/q)^q$, which is subexponential only because $R/Q\to 0$.

The core construction: low degree from commuting swaps

This is the novel part, and the one human reviewers will test hardest. The difficulty is that at each of the Q points a clause has to "see" only its assigned group, and the group assignments differ from point to point. Interpolating a different linear form at each point would cost degree Q. The proof instead works on auxiliary coordinates $B=([r]\times[r])^Q$, where each index records (variable's group, clause's group) at every point, so that $|B| = r^{2Q}$. It then builds a matrix

where $\Pi_s$ swaps the pair at position s. $V_0$ already respects every group assignment, and multiplying by a polynomial f of degree at most R−1 can undo at most R−1 swaps. So each nonzero entry of $M_0$ "crosses groups" at no more than R−1 points, and a factor $\prod_{s\in E}(1-T/s)$ of the same degree removes those crossings. In the shared eigenbasis, a basis vector with j "−1" choices satisfies $M_0\psi=(-1)^j f(j)\psi$. Setting $f(j)=(-1)^j$ on a window of R integers around the binomial mean of $j\sim\mathrm{Bin}(Q,\tfrac{r-1}{2r})$ makes $M_0$ fix almost every basis direction. The few directions outside the window become the rows of the measurement matrix C, and their fraction is bounded by $2e^{-R^2/(8Q)}$. That explains $R\approx\sqrt{\log n}$ and $Q\approx \log n/\log\log n$: R must be large compared with $\sqrt Q$ so that the binomial tail is small, yet small compared with Q so that the Taylor data stays subexponential. Schedules mapping real variables and clauses to auxiliary labels are chosen by derandomized conditional expectations.

The paper names the closest antecedents itself: Williams's split-and-list algorithm, Björklund's interpolation-based counting, Björklund–Kaski–Williams's low-degree curves, Hasse-derivative recovery as in multiplicity codes, and the interpolation tricks of Alman–Williams matrix-rigidity work. It also says its "construction also interpolates (−1)^j on a short interval, now to obtain a polynomial in commuting permutation matrices." The building blocks are familiar to experts. The way they are combined appears to be new.

Bounds, and what Lean actually checks

All figures come from OpenAI's manuscript and scope note. None has been independently re-derived yet.

The Lean statement file is about 220 lines. It defines literals, clauses, CNFs and count directly, a unary/framed bit encoding of the formula, and a deterministic multi-tape PrimitiveMachine built on Mathlib's Turing.Tape. The time bound is stated with logarithms of n+16. The proof itself is spread over thousands of Lean files in the repository, and the comparator configuration permits only Lean's three standard axioms (propext, Quot.sound, Classical.choice). The trusted surface is therefore small enough that experts can read every definition. That is the right place to look for a mismatch, such as whether the space bound counts all visited cells (the scope note says it does) and whether the encoding is canonical and polynomial-length.

Consequences claimed in the paper

The paper says Theorem 1.1 refutes ETH, SETH, Gap-ETH, NSETH and #ETH, as well as the bounded-error randomized versions of ETH, SETH and Gap-ETH. It derives $2^{o(v)}$-time counting of independent sets and proper q-colorings, and $2^{o(v+e)}$ counting of perfect matchings. It also derives subexponential approximation schemes for Max-k-SAT, and a circuit lower bound of more than $c\,n\sqrt{\log n}$ gates, for infinitely many n, for some language in $E^{NP}$, which follows Williams's "fast algorithms imply lower bounds" programme. The paper is careful that $2^{o(n)}$ does not survive general polynomial reductions. Problems such as longest common subsequence, whose SETH-based lower bounds also follow from the Orthogonal Vectors Conjecture, are not automatically sped up.

Cost of discovery

OpenAI says the model found the natural-language disproof on 16 October and formalized it in Lean on 17 October; the manuscript is dated 17 October and revised 25 October. OpenAI has not named the model or disclosed the compute used, so we can't estimate how much it cost to find.

Why it matters

For everyday users: almost nothing changes directly. Your SAT-based tools, route planners and compilers won't get faster. As a rough illustration that ignores the hidden constants (our arithmetic, not the paper's), the manuscript's general exponent $n\log\log n/\sqrt{\log n}$ is still about 0.7n at a million variables. Existing algorithms already reach about 0.39n (1.307ⁿ). The theoretical advantage only appears at sizes no computer will ever handle, and the real constants are unknown.

For developers and builders: the practical result is a change in what you're allowed to call impossible. Statements like "no algorithm can beat X unless ETH fails" appeared in parameterized algorithms, databases, graph theory and computational geometry. Some of those bounds rest on weaker hypotheses that may still stand. Others now have nothing under them, and the paper explicitly "invites a renewed search" for faster algorithms where hardness relied on ETH or SETH.

For companies: the bigger signal concerns AI research capability, not complexity theory. According to OpenAI, a model produced a deep, checkable result in a central field and had it formalized in Lean one day later. It came out alongside two other claims, a Kakeya/local-smoothing proof and quantum-field-theory existence results. Labs that can generate research faster than humans can check it will compete on verification and credibility as much as on discovery.

For the field: OpenAI calls its model outputs "a form of raw research data" and says it doesn't seek academic credit. Human "shepherds" are meant to turn that output into understanding. Ryan Williams, Impagliazzo and Paturi say they signed no NDAs, are unpaid, and asked OpenAI to release all raw data and to fund a community conference, and OpenAI agreed. Their warning that credit may go to whoever has the most powerful tools, and less to those who check and explain, points to a sociological shift that is starting now.

The second-order effect is on intuition. Complexity theorists' belief that P ≠ NP rests partly on decades of failed attempts at faster SAT algorithms. Scott Aaronson wrote that he nudged his personal probability for P = NP from 3% to 5%. In other words, he updated, but only a little.

What to be skeptical of

It is a claim, not a confirmed theorem. The reviewers' open letter says: "Our involvement should not be taken as certification of the claim." Expert review of a 60-page proof with novel machinery takes weeks or months.

Lean checks what was formalized, and that is not everything. The Lean result is the weaker $(\log\log n)^2$ bound. The sharper bounds in the paper are informal. More importantly, a proof assistant guarantees only that the formal statement follows from its axioms. Whether the Turing-machine model, the input encoding and the time accounting match "3-SAT in subexponential time" in the sense the community means is a human judgement. OpenAI's earlier record on this has problems: in its Navier–Stokes claim, readers found that Lean verified a weaker assertion than the one originally published. Our explainer on OpenAI's 722 maths manuscripts covers this gap in detail. That said, the ETH statement file is short and readable, which makes a mismatch easier to find if one exists.

Selective access. OpenAI picked the first reviewers, and it acknowledges that choosing them "creates asymmetry of information". The ETH materials are public. The AI-produced materials for the physics claim announced the same day are being held back for now, at the physics group's request.

Unknowns about the process. We don't know which model produced the proof, how many attempts failed, how much human steering was involved, or how much compute was used. "An AI disproved ETH" needs those numbers before it says anything precise about AI capability.

Don't overextend it. On Hacker News, several commenters pointed out that the 2^(cn) boundary is somewhat arbitrary and that polynomial reductions can wipe out subexponential gains. The result says nothing about cryptography or about practical solver performance.

What to watch next

• The Impagliazzo–Paturi–Williams examination. Watch for a public report, errata, or a human-written simplified proof. A clean human re-derivation would be the strongest confirmation.
• Independent Lean audits. Look for outside experts reviewing SubexponentialSAT.lean's definitions, and for the community proposal to port the result into complexitylib's standard machine model.
• Formalization of the sharper bound. Check whether the $n/\sqrt{\log n}$ (sparse) bound from Appendix D gets machine-checked too.
• The OpenAI-funded conference. Its date and programme will show how the field plans to re-audit ETH-based lower bounds.
• Follow-on algorithms. Watch for new subexponential results for problems whose hardness rested only on ETH or SETH, as the paper predicts, and for any improvement in the exponent.
• Model disclosure. See whether OpenAI names the model and publishes the discovery trajectory.

For context on how OpenAI's earlier AI-maths releases fared under scrutiny, see OpenAI's 722 maths papers explained and our explainer on Claude's quantum-circuit discoveries.

How this was made: researched and written by an AI model (Claude) from the primary sources listed above, then checked claim-by-claim against those sources in a separate AI fact-check pass. Spotted an error? Email [email protected] and we correct it publicly. Our process.