- OpenAI says its model found a disproof of the Exponential Time Hypothesis on October 16 and formalized it in Lean a day later, giving an algorithm that counts k-SAT solutions in subexponential time.
- The same release claims the Kakeya and local smoothing conjectures in all dimensions and an existence proof for Yang-Mills and QCD, part of a Clay Millennium Prize problem.
- Russell Impagliazzo, Ramamohan Paturi and Ryan Williams will run an open review of the ETH claim and say their involvement “should not be taken as certification” of it.
An internal OpenAI model has produced a claimed disproof of the Exponential Time Hypothesis, the assumption that some of computing’s hardest problems can never be solved much faster than by brute force, and two of the three researchers who first proposed it have agreed to lead the public examination. OpenAI announced the result on October 26 alongside a proof of the Kakeya conjecture in every dimension and an existence proof for Yang-Mills theory and quantum chromodynamics, according to its research post. All three arrived with machine-checked proofs in Lean, and that detail moves the real bottleneck in AI-assisted science from checking an argument to understanding it.
OpenAI’s model claims a subexponential algorithm for counting k-SAT solutions
The Exponential Time Hypothesis, stated by Impagliazzo and Paturi in 1999, holds that 3-SAT, the problem of deciding whether a logical formula with n variables can be made true, needs time that grows exponentially in n. Hundreds of papers use it as a foundation: assume ETH, and a long list of other problems is provably hard.
OpenAI’s manuscript, a 67-page preprint dated October 25 and published with its Lean code in the company’s public GitHub repository, describes a single deterministic machine that exactly counts the satisfying assignments of any k-CNF formula. Its running time is bounded by 2 raised to roughly n(log log n)² divided by the square root of log n. That exponent grows more slowly than any fixed multiple of n, which is all a refutation of ETH requires, and it would also refute the stronger SETH variant. The algorithm remains far from polynomial, so the P versus NP question is untouched, and OpenAI itself says that turning the result into faster practical solvers “will require significant further research.”
In mathematics, Larry Guth, Hong Wang and Ruixiang Zhang proved the local smoothing conjecture in two dimensions in 2019, and Wang and Joshua Zahl settled Kakeya in three dimensions in 2025; OpenAI says its model proved local smoothing in every dimension, which would resolve both Kakeya and Stein’s restriction conjecture. The physics result builds on Tadeusz Balaban’s constructive field theory to prove that QCD and a grand unified completion of the Standard Model exist as rigorous mathematical objects, with pure Yang-Mills as a sub-case. The claim covers existence only and leaves the mass gap half of the Millennium problem open.
Lean verification makes AI proofs fast to check and slow to understand
Lean is a proof assistant that accepts a proof only if every logical step follows from the last. Machine checking answers one question cleanly, whether the proof establishes the formal statement written in Lean. It leaves open a second question that only experts can answer, whether that formal statement says what the conjecture says, and a third that matters most to a research field, why the proof works.
A community issue opened to port the result into an open complexity-theory library notes that the Lean comparator states a weaker bound than the sharper theorem in the revised manuscript, and that its maintainers have not yet built or audited roughly 3,977 files of proof code. Both are routine for a new formalization and show that a Lean certificate marks the start of review, and that the volume of machine-generated mathematics already exceeds what a few specialists can read.
| Result | Field | How OpenAI is releasing it | Who is examining it |
|---|---|---|---|
| Local smoothing and Kakeya in all dimensions | Harmonic analysis | AI write-up and Lean proof public; anyone may organize review | Open to the field |
| Exponential Time Hypothesis is false | Complexity theory | Proof, Lean code and raw data public; OpenAI funds a conference | Impagliazzo, Paturi (UC San Diego), Williams (MIT) |
| Existence of Yang-Mills, QCD and a Standard Model completion | Quantum field theory | AI artifacts withheld while experts write the result up themselves | David Gross, Michael Douglas, Arthur Jaffe, Igor Klebanov, Nikita Nekrasov |
OpenAI handed the ETH review to the hypothesis’s own authors
The release process is the most deliberate part of the announcement. OpenAI asked outside experts to act as shepherds, and they chose three different strategies, summarized in the table above. Collaborators sign no NDAs and work unpaid, and OpenAI says it seeks no academic credit for its models’ discoveries. The ETH group goes furthest, picking reviewers who built careers on the hypothesis and pairing them with Williams, who has spent years refuting strong versions of it.
“Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny and an understanding that others can reconstruct, question, and build upon.”
Russell Impagliazzo, Ramamohan Paturi and Ryan Williams, Message to the TCS Community on ETH, October 2026
The same letter raises the issue any lab producing results at this rate now faces. Early access to an AI result gives its first readers a head start on follow-up papers, and the work of checking, simplifying and explaining a proof earns less credit than the discovery itself. OpenAI shipped GPT-6.1 Terra the same day, though the science release carries longer consequences. The credit concern sharpened after OpenAI’s September claims on more than 100 open problems drew objections from mathematicians and its October 6 release of 722 manuscripts left most results without expert readers. A $5 million contribution to the Simons Foundation for workshops is OpenAI’s answer so far.
A Lean certificate settles whether a proof is valid. It takes a room of human experts to decide whether the theorem it proves is the one anyone cared about.
Hundreds of conditional hardness results now need a second look
If the ETH disproof survives review, its practical effect lands first on theory. Every paper that proved a problem hard “assuming ETH” loses that guarantee, and SETH-based lower bounds for problems such as edit distance would need new foundations, though the reviewers note the underlying reductions keep their value.
For the AI industry, the release extends a pattern visible across labs this autumn. Anthropic used Claude to produce a machine-checked formalization of Fermat’s Last Theorem and to verify 123 open-source libraries, and OpenAI’s model now produces claimed answers to open conjectures faster than the people best placed to read them. The reasoning model behind the results is unreleased, so outside researchers cannot reproduce the search itself, only check what OpenAI chose to publish.
The decisive test for this release will come from a few dozen complexity theorists and field theorists working through proofs they did not write. With the logic already checked by machine, whether any of these results becomes accepted science now depends on human experts explaining them well enough to teach, the one step in the pipeline OpenAI’s model still leaves to people.
Santage is committed to independent, transparent journalism. This article is produced in accordance with Santage's Editorial Standards and aims to provide accurate and timely information. Readers are encouraged to verify information independently.