OpenAI says its model refuted the Exponential Time Hypothesis, and ETH's own authors will check the work
Quotable summary
On 26 October 2026, OpenAI said an internal model produced a proof that the Exponential Time Hypothesis (ETH) is false. ETH is a 1999-era conjecture that 3-SAT needs exponential time in the worst case, and hundreds of hardness results in computer science rest on it. The claimed result is a deterministic, polynomial-space algorithm that exactly counts the satisfying assignments of any fixed-width k-CNF formula in subexponential time, roughly 2^(n/(log n)^(1/2+o(1))). OpenAI says the model found the disproof on 16 October and formalized it in Lean on 17 October. The paper and Lean proof are now public on GitHub. A group led by Russell Impagliazzo and Ramamohan Paturi (UC San Diego), two of ETH’s original proposers, and Ryan Williams (MIT) will run an open, independent examination. In their words, their involvement “should not be taken as certification of the claim.” Translation: either a machine just knocked out a pillar of complexity theory, or the field is about to have a very instructive month. Nobody should call it settled yet.
What changed
| Item | Detail |
|---|---|
| Announcement | OpenAI, “Working with academic communities to build scientific understanding,” 26 Oct 2026 |
| Claim | ETH is false (the paper also says it refutes #ETH, SETH, Gap-ETH and NSETH) |
| Method (per paper) | Deterministic algorithm for exact counting of k-CNF solutions, for every fixed k ≥ 2 |
| Stated bound | Time (n+m)^O_k(1) · 2^(n/(log n)^(1/2+o(1))), space poly_k(n, m) |
| Timeline (OpenAI) | Natural-language disproof 16 Oct; Lean formalization 17 Oct; public 26 Oct |
| Artifacts | Paper PDF and Lean proof in the openai/math GitHub repo |
| Shepherds | Impagliazzo, Paturi (UCSD) and Williams (MIT); no NDAs, unpaid, independent (OpenAI; Williams) |
| Group’s asks | All raw data made public, plus an OpenAI-funded conference; OpenAI says it agreed to both |
| Status | Unverified by the community; open examination just starting |
The other two claims in the same release
| Field | OpenAI claim | Release approach |
|---|---|---|
| Harmonic analysis | Proof of Sogge’s local smoothing conjecture in every dimension, which would also resolve the Kakeya and Stein restriction conjectures in all dimensions | AI write-up and Lean proof released publicly |
| Physics | Rigorous existence proof for 4D interacting quantum field theories including QCD and a unified completion of the Standard Model, with pure Yang–Mills existence as a subproblem | Group led by David Gross (with Douglas, Jaffe, Klebanov, Nekrasov) is withholding the AI artifacts and will write the work up itself |
Why it matters
- If it holds, a lot of theorems need a rewrite. OpenAI notes that ETH underpins conditional hardness results in graph theory, computational biology, databases and computational geometry. Those results don’t become false, but they lose their foundation. The paper itself cautions that the speedup is for fixed clause width and doesn’t automatically give subexponential algorithms for every NP problem.
- This is not P = NP. A subexponential bound like 2^(n/√log n) is still far from polynomial. The claim says exponential time isn’t necessary for 3-SAT. It doesn’t say SAT is easy. These are asymptotic worst-case bounds, not measured running times.
- Lean helps, but it isn’t the whole answer. A machine-checked proof sharply cuts the risk of logical errors. Experts still have to confirm that the formal statement matches the real conjecture and that no definitions were quietly bent. That’s why the shepherds call their role examination, not endorsement.
- The release process is part of the story. OpenAI is testing three disclosure models in one day: dump everything publicly (math), public artifacts plus an expert group (CS), and expert-controlled release (physics). It also says it seeks no academic credit. The ETH group’s open letter asks how credit should work when AI finds results first, and that question will outlast this paper.
FAQ
What is the Exponential Time Hypothesis? Proposed by Impagliazzo and Paturi (with Francis Zane in related work) around 1999–2001, ETH says 3-SAT on n variables can’t be solved in 2^(o(n)) time in the worst case. Researchers use it as a standard assumption to prove that many other problems are hard.
Has the ETH refutation been verified? Not by the community. OpenAI says the proof checks in Lean. The independent examination led by Impagliazzo, Paturi and Williams is just beginning, and they’ve said their involvement isn’t certification.
Does this break cryptography? Nothing in the release claims that. Practical cryptography doesn’t rest on ETH directly, and the claimed bound is still super-polynomial. Watch the examination before drawing security conclusions.
Where can I read the proof? OpenAI published the natural-language paper (“The Exponential Time Hypothesis Is False,” dated 25 Oct 2026) and the Lean formalization in its public openai/math GitHub repository.
Sources
| Source | Role | Link |
|---|---|---|
| OpenAI | Primary: announcement, timelines, shepherd groups, principles | OpenAI — Working with academic communities to build scientific understanding |
| OpenAI (GitHub) | Primary: ETH paper PDF (abstract, bound, scope) | openai/math — The Exponential Time Hypothesis Is False (paper) |
| alphaXiv | Secondary: paper listing and summary | alphaXiv — The Exponential Time Hypothesis Is False |
| The Next Web | Secondary: shepherds’ open-letter quotes, no-NDA/unpaid detail | The Next Web — OpenAI says its AI model has disproved the ETH |