An algorithm that counts the solutions of any 3-SAT formula in subexponential time: that is the claim of "The Exponential Time Hypothesis is False", a preprint credited only to OpenAI and released on October 26, 2026. If it survives scrutiny, one of the assumptions underpinning much of the last 25 years of complexity theory is gone. It was produced by an unreleased internal model, and a group of independent researchers is already going through it.
What the paper claims
The Exponential Time Hypothesis (ETH) held that deciding 3-SAT on n variables takes 2^Ω(n) time in the worst case: no trick can make the exponent grow less than linearly. The paper gives a deterministic algorithm that exactly counts the satisfying assignments of a k-CNF formula, for any fixed k, in polynomial space and with an exponent on the order of n / (log n)^(1/2+o(1)). Checking whether the count is above zero decides satisfiability, so the exponent is no longer linear in n.
The paper lists what falls with it: ETH, its strong version (SETH), Gap-ETH, NSETH and the counting variant (#ETH). It also derives subexponential algorithms for counting graph colorings, independent sets and perfect matchings.
How it stacks up against the best known
| Problem | Best prior result cited in the paper | OpenAI's claim |
|---|---|---|
| 3-SAT, deterministic | O(1.32793^n), Liu (2018) | 2^o(n) |
| 3-SAT, randomized | O*(1.307^n), Jiang and Cai preprint (2026) | 2^o(n), and deterministic |
| Counting 3-SAT solutions | O*(1.637^n), Kutzkov (2026) | 2^o(n) |
Every previous algorithm was exponential with a base somewhat below 2. The new one changes the shape of the exponent. The technique is algebraic: it splits the variables into groups and replaces clauses with low-degree polynomials that share a few "measurements", so each group's contribution multiplies independently.
Why an engineer should care
It will not speed up your SAT solver or your resource scheduler any time soon. This is an asymptotic result, with hidden constants that depend on k, and the gain in the exponent is a factor on the order of the square root of log n.
What does change is the map of what we believe is impossible. For years SETH has been the reason to say that edit distance, longest common subsequence, Fréchet distance and regular-expression matching cannot be solved much faster than the usual quadratic algorithms. The paper notes that some of those bounds survive because they rest on weaker assumptions, such as the Orthogonal Vectors Conjecture, but others lose their footing. On the cryptography side, Appendix C shows that constant-locality versions of Goldreich's candidate one-way functions can be inverted in 2^o(n) time, while stressing that this does not break them against polynomial-time attackers.
For anyone building with AI, the headline is a different one: a model has produced a proof that, if confirmed, settles a central conjecture in theoretical computer science. It sits in the openai/math repository, which already holds 721 manuscripts in 373 families, generated after posing roughly 4,000 problems to the model at an average of three hours of compute per result.
The caveat that matters
This is a preprint with no peer review. OpenAI asked a group led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams, three central figures in ETH research, to examine and explain the proof, and released the materials immediately at the group's request. The repository's track record argues for patience: on October 7, 2026 it withdrew three manuscripts over a sign error and revised 14 others. The same October 26 release also adds a harmonic-analysis result covering the Kakeya conjectures.