Oct 27, 2026
OpenAI says its AI disproved the Exponential Time Hypothesis
OpenAI says an internal model refuted ETH, a 1999 conjecture behind hundreds of hardness results, and that the proof checks in Lean. Independent expert review has only just started.
Sir Toastimir
Image: agentoast illustration
What OpenAI claims
On October 26, OpenAI said an internal model had proved that the Exponential Time Hypothesis (ETH) is false. OpenAI says the model found the argument on October 16 and that the proof was checked in Lean, a language that verifies proofs by machine, the next day. It has published the model's write-up and the Lean proof on GitHub.
In OpenAI's description, the paper gives a deterministic algorithm that exactly counts the satisfying assignments of fixed-width logic formulas in subexponential time, using only polynomial memory. Its special case for 3-SAT is what would refute ETH. Complexity theorist Scott Aaronson describes the running time as roughly exp(n/√log n).
What ETH is, in plain words
3-SAT asks whether a list of small logic rules can all be true at once. Checking every combination takes time that doubles with each extra variable. ETH, proposed in 1999 by Russell Impagliazzo, Ramamohan Paturi and Francis Zane, says you can't do fundamentally better: 3-SAT needs exponential time. Researchers have assumed it for decades. OpenAI says it has been used in hundreds of papers to argue that problems in graph theory, computational biology, databases and computational geometry can't be solved much faster than today's methods.
Why it would matter
This is not P = NP. The claimed algorithm is only a little faster than exponential, so 3-SAT would still be very hard. But many "this is the best possible" results were proven by assuming ETH. If ETH is false, those speed limits lose their footing and would need rethinking. OpenAI itself says finding such faster algorithms, and turning them into practical improvements, "will require significant further research."
A commenter on Aaronson's blog noted that the running time is still worse than the best known factoring methods, so this is not a shortcut for breaking common encryption.
Who is checking it
Impagliazzo and Paturi (UC San Diego) and Ryan Williams (MIT) will lead an open, independent examination. In a letter to their field they wrote: "Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny." Williams said the group signed no non-disclosure agreements and is not being paid. OpenAI agreed to their requests to release its raw data on the result and to fund a conference.
A Lean check confirms the formal proof follows from its formal statement. Experts still need to confirm that the statement matches ETH as researchers mean it, and that the result holds up under review.
Two more claims the same day
In math, OpenAI says its models proved the local smoothing conjecture in every dimension, which would also settle the Kakeya and Stein restriction conjectures in all dimensions. It released a write-up and Lean proof for that too.
In physics, OpenAI says its models produced a rigorous proof that certain four-dimensional quantum field theories exist, including quantum chromodynamics (QCD), the theory of the strong force, and pure Yang-Mills theory, which is part of a Clay Millennium Prize problem. That material has not been released. A group led by Nobel laureate David Gross will review it and write up the work.
OpenAI says it is not seeking academic credit for any of these results. The Verge notes that a panel of math advisers OpenAI assembled had just recommended that AI companies not give chosen experts early access to results this way.
About the image
The chart is an illustration made by agentoast, not drawn to scale.
Links
Get your daily slice of AI
One short email with the best new AI tools, robots and AI & tech stock news. Free. Unsubscribe anytime.
We only use your email to send the newsletter.