On 26 October 2026 OpenAI published a preprint titled "The Exponential Time Hypothesis is False" in its public math repository, alongside two other claimed results, and named the people who will check it. The paper, dated 17 October and revised on the 25th, gives a deterministic algorithm that exactly counts the satisfying assignments of a k-CNF formula in subexponential time and polynomial space. Because a count of zero also decides satisfiability, the 3-SAT case refutes the Exponential Time Hypothesis. The verification group is led by Russell Impagliazzo and Ramamohan Paturi, two of the authors of the hypothesis, and by Ryan Williams at MIT.
The claim is narrow. Its consequences reach a large part of complexity theory. ETH is the assumption behind a large fraction of conditional hardness results in fine-grained and parameterized complexity, and the paper says it refutes ETH, SETH, Gap-ETH, NSETH and #ETH in one move. OpenAI's own repository describes the manuscripts as "raw research data, rather than polished academic papers," and the company says it defers to the math community on credit and precedence. The shepherds have not yet published a verdict.

The release
The algorithm in Theorem 1.1 takes a k-CNF with n variables and m clauses, for any fixed k ≥ 2, and returns the exact number of satisfying assignments in (n+m)^{O_k(1)} 2^{O_k(n log log n / log n)} bit operations using (n+m)^{O_k(1)} bits of space. For inputs of bounded density, m ≤ Dn, the exponent improves to O_{k,D}(n / log n). The abstract states the headline form, 2^{n/(log n)^{1/2+o(1)}}.
Two details decide how much of that is verified. The first is the Lean development. The repository's formalization note for this result covers a deterministic machine that counts assignments of a canonically encoded k-CNF in (L+1)^{O_k(1)} 2^{O_k(n (log log n)^2 / √log n)}, where L is the encoding length, visiting at most (L+1)^{O_k(1)} tape cells. That exponent is weaker than the paper's n/√log n, and it is proven for canonical encodings rather than arbitrary input formats. Both forms are subexponential, so both refute ETH, but the formalized statement is not the sharpest one in the paper.
The second is the base rate of the repository. It holds 721 manuscripts in 373 families, of which about 42% of top-line results have accompanying Lean formalizations, and the README says outright that not everything has one and that "some of the unformalized results could have issues." The same repository's changelog for 7 October records three withdrawals after a sign error in a stabilization-trace argument, and revisions to fourteen other manuscripts for proof repairs and corrected statements. A submission in this collection is evidence, not a result, until someone outside has read it.
ETH and its relatives
ETH was formulated by Impagliazzo and Paturi around 1999 and published in 2001: 3-SAT on n variables requires 2^{Ω(n)} time in the worst case. The sparsification lemma extends the claim to k-SAT for every fixed k and to sparse formulas, which is what made it usable as a reduction base. SETH sharpens it: for every ε > 0 there is a fixed k such that k-SAT cannot be solved in 2^{(1-ε)n} time. Gap-ETH adds a promise gap, NSETH restricts the question to nondeterministic algorithms for unsatisfiability, and #ETH states the same lower bound for exact counting.
The hypothesis earned its place by explaining why so many unrelated problems seemed stuck at their best known running times. Under SETH, edit distance, longest common subsequence, dynamic time warping, Fréchet distance and regular-expression matching have no polynomial-factor speedups over quadratic algorithms; graph diameter approximation and dynamic reachability inherit bounds; and under ETH, Clique and Dominating Set are hard in the parameter of treewidth. Those results are implications, so a false ETH does not make them false. It makes them unsupported, and it turns each one into a search for the algorithm that the hypothesis said could not exist.
The counting algorithm
The construction starts with a 3-CNF in which every variable occurs in at most three clauses. The product of the clause polynomials has degree at most 3n, so the exact count can be recovered by interpolation from sums over small groups of variables. The difficulty is that the sums share variables and do not factor. The paper introduces linear substitutions that depend polynomially on an interpolation parameter, so that after fixing a few integer linear measurements the sum does factor, and it controls the number of measurements through the rank of a matrix I − M₀ while keeping the substitution degrees small. The Taylor coefficients at the interpolation points are then computed by fast summation and the count is recovered by Hermite interpolation. Arbitrary k-CNFs are handled by sparsification and variable copying, and the parity tests that police the sparsification step come from a Tanner code built on an expander.
The algorithm is deterministic and uses polynomial space, which matters as much as the time bound. The paper's four working sections follow the pipeline that produces it: Section 3 builds the fast counting algorithm on shared linear summaries, Section 4 constructs low-degree replacement forms, Section 5 counts common zeros of sparse polynomial equations, and Section 6 reduces #k-SAT to that counting problem. The two constraints that hold the construction together are the rank of I − M₀, which bounds how many linear measurements have to be fixed before the sum factors, and the sparsity of M₀'s nonzero entries, which keeps the substitution degree low enough for a handful of Taylor coefficients to determine the count. Prior exact counters for k-SAT ran in 2^{n−Ω(n/k)}; Wahlström's #2-SAT algorithm ran in O*(1.2377^n) and a #3-SAT counter in O*(1.637^n), all exponential. The new bound is 2^{o(n)} for every fixed k, and the paper draws three consequences beyond SAT. Counting independent sets and proper q-colorings on a graph with v vertices becomes deterministic 2^{o(v)} time, and counting perfect matchings becomes 2^{o(v+e)}. Max-k-SAT gets subexponential-time approximation schemes within εm clauses. And a circuit lower bound falls out: there is a language in E^NP whose circuits need more than c·n log n non-input gates for infinitely many n, with fan-in at most two and unrestricted fan-out.
Hypotheses that fall
The refutation of ETH, SETH, Gap-ETH and NSETH is stated in Section 1.1.1 and follows from the same object: an exact counter decides satisfiability, and deciding satisfiability also decides the Gap-ETH promise problem and the unsatisfiability question that NSETH is about. Because the algorithm works for every fixed clause width, and 2^{n/log n} is o(2^{εn}) for any fixed ε, SETH's quantifier order does not save it.
The fine-grained consequences are the part of theoretical computer science that will feel this first. A conditional lower bound is a theorem of the form "if SETH holds, problem P has no O(n^{2−δ}) algorithm." Thousands of such theorems now rest on a false premise. Many of them will still be true for other reasons, and the paper is explicit about which hypotheses survive: the Orthogonal Vectors Conjecture still implies the lower bounds for longest common subsequence and regular-expression matching, and the assumption that unrestricted CNF-SAT, with width growing in n, has no 2^{(1−δ)n} algorithm still supports the Fréchet distance, diameter approximation and treewidth results. The fixed-width algorithm does not touch those.
There is a second limit, and the paper states it plainly. Bounds of the form 2^{o(n)} do not transfer under general polynomial-time reductions, because a reduction can blow n up to n^{O(1)} and turn 2^{o(n)} into 2^{n^{o(1)}}. So the result does not give subexponential algorithms for NP-complete problems in general, and it says nothing about CircuitSAT, where the input is a circuit rather than a formula of fixed width.
Surviving assumptions
P versus NP is untouched. A 2^{n/log n} algorithm is subexponential and still superpolynomial, so ETH being false removes a strong route to P ≠ NP without providing a route to P = NP. Cryptography is untouched for a different reason: the result is a worst-case statement about Boolean formulas, while the security of a signature scheme or a key exchange is an average-case statement about specific algebraic problems. A faster worst-case counter for k-CNF does not invert a lattice problem.
Practical SAT solving is untouched, and the arithmetic shows why. At n = 10^6 variables, n/√(log n) is about 270,000, so the exponent is still 2^{270,000}. Even at n = 1,000 the exponent is around 380. The algorithm is a statement about asymptotics; it changes no solver's behaviour on any instance that fits in memory. The same arithmetic rules out the obvious follow-on hope that factoring could be routed through 3-SAT and beaten: the resulting bound is worse than the number field sieve.
What does change is the status of a research programme. A graduate student quoted in the comment thread under Scott Aaronson's post described rewriting a paper that contained an ETH-based lower bound on the day of the announcement. That is the shape of the disruption: a generation of impossibility claims lost its premise at once, without any machine getting faster.
The verification gap
Three things have to happen before the field can treat this as established. The Lean development has to build and its comparator statement has to match the intended theorem; the paper's Sections 3 through 6, which carry the algebraic construction, have to be read by people who can check the rank and degree bounds; and the exponent has to survive the transition from the formalized canonical-encoding version to the statement in the abstract.
None of that is unusual for a result of this size, and the arrangement is more transparent than the October 6 release, when hundreds of manuscripts appeared without named reviewers. It is still not peer review. The advisory panel OpenAI assembled for mathematics, AGMAI, recommended the day before this announcement that AI companies stop giving selected people early access to output, citing unequal access, borrowed reputation and biased selection. The company released the material immediately at the shepherds' request, which addresses the access question and leaves the verification question where it was.
The formalization rate is the number I would watch. If I had to pick a single claim to test first, it would be the rank bound in Section 4, because the exponent in Theorem 1.1 is a function of it and an error there would move the running time without breaking any of the surrounding algebra. If the ETH family's Lean development compiles against the sharp exponent rather than the weaker one, the case is close to closed, because a machine-checked proof of a subexponential counter is not a matter of expert taste. If it does not, the paper joins a long queue of manuscripts whose status depends on how much of the argument a human reader can reconstruct, and the repository's own history of withdrawals is the relevant prior.
The paper was revised on 25 October, eight days after its first date, and the repository keeps earlier versions accessible and records corrections as new versions. OpenAI also published an open letter asking the community three questions: what expectations should govern early access to AI-generated results, how credit should recognise the work of checking and explaining them, and how to support students while research methods change.
References
- The Exponential Time Hypothesis is False (OpenAI Math Release, PDF)
- Lean formalization scope for result family 378
- OpenAI Math Release repository README
- Repository history and corrections
- OpenAI announces three big science discoveries (The Verge)
- Podcasts about the Topic: Part II, with comment thread (Shtetl-Optimized)
Loading comments…