On October 26, OpenAI released a 67-page paper, written by an unnamed internal model, that claims to refute the Exponential Time Hypothesis (ETH). Russell Impagliazzo and Ramamohan Paturi formulated the conjecture in 1999, and OpenAI says “hundreds of papers” have since used it to show that problems in graph theory, databases and computational biology are hard, assuming ETH holds. According to OpenAI’s announcement, the model found the disproof on October 16, and a version checked in Lean, a proof assistant, was ready the next day.
Impagliazzo and Paturi, both at UC San Diego, now lead the group that will examine the claimed refutation of their own hypothesis, with Ryan Williams of MIT. The same release carries two more claims: a proof of Sogge’s local smoothing conjecture in every dimension, which would settle the Kakeya conjecture, and an existence proof for Yang-Mills theory and quantum chromodynamics (QCD) that covers part of a Millennium Prize problem.
The floor under 3-SAT
3-SAT is the textbook hard problem of computer science. A 3-SAT formula is a list of constraints, each on three true-or-false variables, and the question is whether some assignment of values satisfies all of them at once. Trying every assignment takes 2^n steps for n variables. Decades of work lowered the base of that exponential: Uwe Schöning’s 1999 algorithm runs in about (4/3)^n, the PPSZ family reached 1.308^n in a 2014 paper by Timon Hertli, and later refinements, most recently a 2026 preprint by Tao Jiang and Shaowei Cai, brought it to about 1.307^n.
ETH says this progress has a floor. Its standard form holds that 3-SAT needs time 2^(cn) for some fixed c above zero, however good the algorithm. Complexity theorists use that floor as a yardstick: if a fast algorithm for problem X would give a fast algorithm for 3-SAT, X inherits the hardness. ETH implies that P differs from NP, so it is the stronger of the two statements.
What the paper claims
The paper, dated October 17 and revised October 25, describes a deterministic algorithm that counts the assignments satisfying a formula of this kind, for any fixed clause width, in time 2^(n/(log n)^(1/2+o(1))) up to polynomial factors, using polynomial memory. A count above zero also answers whether a solution exists, so the bound covers 3-SAT. On his blog, Shtetl-Optimized, the UT Austin complexity theorist Scott Aaronson summed it up as “an algorithm to solve 3SAT in an amount of time that scales roughly like exp(n/√log(n)).”
That running time still grows faster than any polynomial, but its exponent per variable shrinks toward zero as n grows, which is what ETH ruled out. The formal proof, according to OpenAI’s Lean scope page, covers exact counting in time 2^O(n(log log n)^2/√log n), a slightly weaker bound than the paper’s sharpest one and still subexponential.
Three results in one release
The mathematics result concerns waves. Christopher Sogge proposed the local smoothing conjecture in 1991. Larry Guth, Hong Wang and Ruixiang Zhang proved it in two spatial dimensions in 2019, and Wang and Joshua Zahl proved the Kakeya conjecture in three dimensions in 2025, work cited in Wang’s 2026 Fields Medal.
OpenAI’s 59-page paper claims a proof of local smoothing in every dimension from two up, with the Kakeya and restriction conjectures as consequences. OpenAI says it obtained that output on October 18 and formalized it in Lean the following day. Earlier this month, three teams posted proofs of a 31-year-old geometry conjecture with AI help.
The physics result is the one the public cannot read yet. OpenAI says its models produced a proof of the existence of pure Yang-Mills theory on September 9 and of QCD on September 18, and that it finished the Lean formalization of Yang-Mills existence on October 16. A group led by David Gross, who shared the 2004 Nobel Prize in Physics, with Michael Douglas, Arthur Jaffe, Igor Klebanov and Nikita Nekrasov, “decided to hold off on releasing the AI-produced artifacts” and will write the work up itself.
Jaffe wrote the Clay problem statement with Edward Witten. It asks for existence and a mass gap; OpenAI claims existence only. On October 17, we covered another physics result of this kind: AI-found counterexamples to a 1967 fusion conjecture.
A campaign measured in days
OpenAI says it began testing its internal model on every open Millennium Prize problem on September 1. The group that worked on Navier-Stokes involved “on the order of 10,000 concurrent agents,” and OpenAI’s September 8 post dates the claimed resolution to September 5, about 88 hours after launch, plus 17 hours for the Lean check. OpenAI wrote then that it did “not intend to claim the Millennium Prize.”
On October 6, the company put hundreds of manuscripts on GitHub. The repository now lists 721 manuscripts in 373 families, with about 42% of top-line results formalized, and OpenAI says the average result used the equivalent of “roughly three hours of ChatGPT Pro thinking.” Aaronson’s comment on the ETH paper: “Even as we struggle to digest the previous courses, the endless buffet continues!” By OpenAI’s dates, the ETH disproof came 45 days after the September 1 start, and the all-dimension local smoothing proof two days after that.
Who checks the proof
OpenAI calls the manuscripts “a form of raw research data” and tried a different release method in each field: the math output went out as is, the ETH files are public while an outside group organizes their examination, and the physics group decides on its own release. Under OpenAI’s rules, the groups sign no nondisclosure agreements and take no pay, and OpenAI says it does not seek academic credit. Its post concedes that picking the outside experts it calls shepherds “creates asymmetry of information.”
The ETH group’s letter to the community sets out its role: “Our involvement should not be taken as certification of the claim.” It adds: “If the claim is correct, it will change an important part of theoretical computer science.” On Bluesky, Williams wrote that the group has no access to OpenAI’s internal models (“We only got the PDF”) and that OpenAI agreed to its two requests: release all the raw data and pay for a conference.
The Verge pointed to the timing: one day before the release, on October 25, the Advisory Group on Mathematics and Artificial Intelligence, an independent group of mathematicians at the Institute for Advanced Study, wrote on Terence Tao’s blog that “we recommend that AI companies do not adopt” the practice of designating mathematicians to receive AI output, citing unequal access, biased selection and “borrowed reputation.” The panel adds that its advice is meant for mathematics and “not necessarily for other areas of science.” OpenAI released its math result directly, with no designated group.
The caveats in the papers
The ETH paper limits its own reach. Its result “does not imply that general NP problems admit subexponential time algorithms,” it says, because bounds of this kind do not carry over through the usual reductions between problems. P versus NP stays open, and no SAT solver gets faster from this paper: OpenAI writes that turning the theory into practical gains “will require significant further research.”
A Lean proof covers only its formal statement, and readers still have to check that this statement says what ETH says in the literature, using the comparator file OpenAI published alongside the proof. On October 7, OpenAI withdrew three manuscripts after a sign error and revised 14 others, and its README warns that “some of the unformalized results could have issues.” None of the three results has been refereed.
What it means
OpenAI’s dates show proofs arriving faster than experts can read them: one day from a natural-language disproof of ETH to a Lean version, while the organizers of the community review have only begun to plan it. In this case, understanding the result is the slow step, and the authors of the 1999 hypothesis lead that work, with Ryan Williams.
If the refutation holds, theorems in complexity theory stated “assuming ETH” lose their footing. The ETH group’s letter says the ideas, reductions and techniques developed through decades of ETH-based research “retain their value.”
The next steps to watch are the findings repository, blog and feedback form announced by the ETH group, the conference OpenAI agreed to fund, any human-written reconstruction of the argument, and the Gross group’s write-up of the Yang-Mills and QCD material. Until then, the ETH result is what OpenAI’s own files show: a claim, formalized in Lean by OpenAI, open to anyone who wants to check it, and not yet reviewed by peers.
Sources
- Working with academic communities to build scientific understanding, OpenAI, October 26, 2026
- The Exponential Time Hypothesis is False, OpenAI, GitHub (openai/math), October 25, 2026
- The Exponential Time Hypothesis is False (scope of the Lean formalization), OpenAI, GitHub (openai/math), October 26, 2026
- Local smoothing for the Euclidean wave equation, OpenAI, GitHub (openai/math), October 25, 2026
- Message to the TCS Community on ETH, Russell Impagliazzo, Ramamohan Paturi and Ryan Williams, October 26, 2026
- Podcasts about the Topic: Part II, Scott Aaronson, Shtetl-Optimized, October 26, 2026
- Disadvantages of Designating Mathematicians for AI Output Releases, Advisory Group on Mathematics and Artificial Intelligence, on Terence Tao’s blog, October 25, 2026
- OpenAI announces three big science discoveries and a new way to work with academics, Richard Lawler, The Verge, October 26, 2026
Header image: chart by MACCUS, data from OpenAI’s paper The Exponential Time Hypothesis is False (October 25, 2026)
