OpenAI says its AI proved Exponential Time Hypothesis false

Key takeaways

• OpenAI says its internal models produced a disproof of the Exponential Time Hypothesis (ETH), a 1999 conjecture that underpins hundreds of hardness results in computer science.
• The same announcement claims a proof of the local smoothing conjecture in every dimension and a rigorous existence proof for quantum chromodynamics (QCD).
• The ETH preprint describes a deterministic algorithm that counts the solutions of k-CNF formulas in subexponential time. OpenAI says the proof was checked in the Lean proof assistant.
• None of the three results has been peer reviewed. The physics group chose to hold back the AI-produced material and write up the work itself.
• Outside reaction ranges from "historic" (Alex Iosevich, University of Rochester, per Al Jazeera) to open scepticism on Hacker News.

OpenAI claimed on Monday, October 26, that its models proved the Exponential Time Hypothesis false, a 1999 conjecture by Russell Impagliazzo and Ramamohan Paturi. The claim rests on a preprint and a machine-checked proof that independent experts, including Impagliazzo, have only just started reviewing.

The ETH result was one of three announced together in a post titled "Working with academic communities to build scientific understanding." The other two are in harmonic analysis and in quantum field theory. OpenAI described the AI-written manuscripts as "a form of raw research data" that still needs expert interpretation. That framing matters for anyone searching whether the hypothesis has now been "proved false": the honest answer today is that OpenAI says so, and the verification process has just begun.

What the Exponential Time Hypothesis says

The ETH is a conjecture about 3-SAT, a basic problem in which a computer must decide whether a logical formula with n true-or-false variables can be satisfied. Brute force takes about 2ⁿ steps. ETH states that no algorithm can do fundamentally better: every correct 3-SAT algorithm needs time of at least 2^cn for some fixed constant c greater than zero. In technical terms, 3-SAT cannot be solved in subexponential time, 2^o(n).

The hypothesis is stronger than the familiar P ≠ NP conjecture. Researchers have used it as an assumption to show that many problems, including clique, vertex cover and graph colouring, have no subexponential algorithms. OpenAI's post says ETH has been used in hundreds of conditional hardness papers. If ETH falls, those results lose the premise they were built on, although many may survive under other assumptions.

What the OpenAI preprint claims

The preprint, posted in OpenAI's public openai/math repository on GitHub, is titled "The Exponential Time Hypothesis Is False". It lists "OpenAI" as author and is dated October 17, 2026, revised October 25. Its abstract describes a deterministic algorithm that exactly counts the satisfying assignments of any k-CNF formula, for every fixed k of at least 2.

According to the abstract, the algorithm uses polynomial space and runs in time (n+m)^O_k⁽¹⁾ · 2^{n/(log n)1/2+o(1)}, where n is the number of variables and m the number of clauses. Theorem 1.1 of the paper gives the exponent as O_k(n log log n / √log n). Because the exponent grows more slowly than any constant times n, counting solutions, and therefore deciding 3-SAT, would take subexponential time. That directly contradicts ETH.

Two caveats are important. First, the speed-up is asymptotic: dividing n by roughly the square root of log n is a real but modest gain, and OpenAI's post says turning the idea into faster practical algorithms would require "significant further research." Second, refuting ETH does not settle P versus NP. A subexponential algorithm is still far from a polynomial one.

The other two claimed results

Local smoothing in every dimension

In mathematics, OpenAI says its models proved the local smoothing conjecture, a central question in harmonic analysis about how solutions of wave equations gain regularity when averaged over time. According to OpenAI's post, the proof also resolves the Kakeya conjecture and Stein's restriction conjecture in all dimensions. Earlier human work had settled only low-dimensional cases: Larry Guth, Hong Wang and Ruixiang Zhang proved the two-dimensional local smoothing case in 2019, and Wang and Joshua Zahl proved the three-dimensional Kakeya conjecture in 2025, the post notes.

Alex Iosevich, a mathematics professor at the University of Rochester who specialises in harmonic analysis, told Al Jazeera that OpenAI appeared to have cracked the conjecture in a "historic development." He added that the conjecture "was formulated by my PhD adviser, Chris Sogge, so it is near and dear to my heart." Iosevich said the news was "a shock at first," that he expects theoretical mathematics to change drastically, and that "I feel a twinge of sadness as a result."

Quantum chromodynamics existence proof

In physics, OpenAI claims a mathematically rigorous existence proof for certain four-dimensional interacting quantum field theories with gauge fields and fermions. These include quantum chromodynamics, the theory of how quarks and gluons interact, and what the post calls a unified Standard Model completion. The work builds on Tadeusz Balaban's approach and includes a proof that pure Yang–Mills theory exists, a question tied to one of the Clay Millennium Prize problems. OpenAI does not say the prize problem has been solved, and Hacker News commenters pointed out that the "mass gap" part of that problem does not appear to be covered.

How the "shepherd" process works

Rather than simply posting papers, OpenAI asked outside experts to act as "shepherds" for each result. The groups decided how the results would be released:

Source: OpenAI announcement, October 26, 2026. Dates are those given by OpenAI.

OpenAI set out four principles for these collaborations: no non-disclosure agreements, no academic credit claimed by OpenAI for the discoveries, recognition for collaborators' own work, and voluntary, unpaid participation. It also committed $5 million to the Simons Foundation for workshops and related programmes and said it would fund a conference on the implications of the ETH result. The company acknowledged that its choice of initial shepherds "creates asymmetry of information," Al Jazeera reported, and asked for feedback on the approach.

What is verified and what is not

• Verified by machine, per OpenAI: Lean formalizations for the ETH result, the local smoothing result and the pure Yang–Mills existence proof. A Lean check confirms that the formal proof follows from its stated definitions, but experts still have to confirm that those definitions match the intended mathematical statements.
• Not yet done: peer review or journal publication for any of the three results. OpenAI's post does not mention either.
• Not yet public: the QCD material, which the physics group decided to hold back while it writes up the work.
• Open question: OpenAI itself says it does not yet know which of the three release approaches will prove most useful.

On Hacker News, the announcement drew more than 700 points and over 300 comments within hours. Some commenters went straight to the Lean files. One called the ETH result "a huge result if true," while others dismissed the announcement as "a publicity stunt." Several noted that the claimed all-dimensions Kakeya result builds on earlier human breakthroughs, including Hong Wang's work. For background on why AI-generated claims need checking, see our explainer on what AI hallucinations are.

What it means

If the ETH disproof holds up, it would be one of the most consequential results in computational complexity in decades. A long list of "this problem cannot be solved faster" results would need new foundations, and researchers would revisit which hardness assumptions remain safe. It would not, by itself, make hard problems easy in practice, and it would not decide P versus NP.

For the AI industry, the announcement is a bid to show that frontier models can produce research-grade mathematics, not just assist with it. It also comes days after OpenAI changed how it trains frontier models, which we covered in OpenAI's move to train models without live internet access. Whether the claims become accepted science now depends on the shepherd groups and the wider research community, a process that usually takes months, not days. Follow our OpenAI coverage and the wider AI section for updates as reviewers report back.