OpenAI says its model disproved the Exponential Time Hypothesis; experts now checking

OpenAI says one of its models has disproved the Exponential Time Hypothesis (ETH), the long-standing belief that 3-SAT cannot be solved in subexponential time, and it published the write-up and a Lean proof on GitHub on 26 October 2026 before anyone outside the company has checked them. A working group led by the computer scientists who proposed ETH is now examining the claim. Until that work is done, this is a claim, not an established result.

Key points

• OpenAI's paper, "The Exponential Time Hypothesis is False" (dated 25 October 2026), describes a deterministic algorithm that exactly counts satisfying assignments of fixed-width CNF formulas in subexponential time and polynomial space; OpenAI says the 3-SAT case refutes ETH (OpenAI, via The Verge).
• ETH was formulated by Russell Impagliazzo and Ramamohan Paturi in 1999 and is widely believed to be true (Wikipedia; The Verge).
• An independent working group of Impagliazzo, Paturi and MIT's Ryan Williams will examine and explain the proof; at their request OpenAI released the materials immediately (The Verge).
• The announcement also covered a math result (local smoothing for waves, with consequences for the Kakeya conjecture) and a physics claim whose full write-up has not been released (The Verge; Engadget).
• No independent verification has been published as of this writing, and the paper's own GitHub page carries only a title, author, date and citation, with no abstract.

What happened

On 26 October OpenAI announced three results in mathematics, computer science and physics. For the computer science result, the company published a paper and a Lean formalisation in its openai/math GitHub repository. The directory for the paper contains a README.md, a paper.pdf and a build/ folder; the README gives only the title, "OpenAI" as author, the date of 25 October 2026 and a citation.

According to OpenAI's announcement as quoted by The Verge, the paper "gives a deterministic algorithm that exactly counts satisfying assignments of fixed-width CNF formulas in subexponential time and polynomial space." The company adds that "the case of 3-SAT refutes the Exponential Time Hypothesis."

Rather than simply posting the claim, OpenAI says it asked outside experts to act as "shepherds". For computer science that is the group of Impagliazzo, Paturi and Williams. Impagliazzo and Paturi proposed ETH in 1999, so the people best placed to judge the result are also the people whose hypothesis it would overturn. The Verge reports that the group asked for the materials to be made public at once so other researchers can examine them in parallel. OpenAI also published an open letter asking the community three questions: what expectations should govern early access to AI-generated results, how credit should recognise both discoveries and the work of checking and explaining them, and how to support students and researchers as methods change.

The other two results, per The Verge and Engadget:

• Mathematics: a proof of Sogge's local smoothing conjecture for waves in every spatial dimension of at least two. OpenAI says it yields the Kakeya maximal and dimension conjectures and Stein's spherical restriction estimates throughout the interior of the conjectured range. The company released the model output directly, as it did in an earlier release on 6 October, so researchers can work out their own explanations.
• Physics: a claimed "mathematically rigorous existence proof of certain interacting quantum field theories containing gauge fields and fermions in four dimensions", including Quantum Chromodynamics. The full material has not been released; David Gross will lead a group with Michael Douglas, Arthur Jaffe, Igor Klebanov and Nikita Nekrasov to shepherd it.

Background

ETH is an unproven hardness assumption about 3-SAT, the problem of deciding whether a Boolean formula made of clauses with three literals each can be satisfied. In its usual form it says there is a constant s such that every correct algorithm needs time at least 2^(s·n) on formulas with n variables; equivalently, 3-SAT has no subexponential-time algorithm. Wikipedia notes it is stronger than P ≠ NP: ETH implies P ≠ NP, but if ETH fails that says nothing about whether P equals NP.

ETH matters because hundreds of papers use it as the premise for "conditional lower bounds". Instead of proving that no fast algorithm exists, which nobody can do, those papers show that a fast algorithm for their problem would break ETH. According to Wikipedia, ETH implies that problems such as graph k-coloring, Hamiltonian cycle, maximum clique, maximum independent set and vertex cover have no algorithms faster than c^n for some constant c, and it rules out finding cliques or independent sets of size k in n^o(k) time. Engadget describes the hypothesis as underpinning papers in databases, computational biology and geometry.

OpenAI's wording is about counting satisfying assignments of fixed-width CNF formulas, which is at least as hard as deciding whether any exist. A subexponential counting algorithm would therefore also decide satisfiability in subexponential time. That is why the company says the 3-SAT case refutes ETH. We could not open the paper's PDF text, so we have not checked this chain of reasoning ourselves; it is OpenAI's statement.

The release also follows a pattern. The Verge notes that the announcement comes less than a month after OpenAI published hundreds of manuscripts it said solved long-standing math questions, and that a panel of math advisers OpenAI assembled (AGMAI) said the day before that it recommends AI companies not adopt the practice of giving certain people early access to output, citing unequal access, borrowed reputation and biased selection. It recommended releasing output on scholarly repositories, with Lean-formalised proofs, information on how problems were chosen, and funding for people working to understand the results. OpenAI itself acknowledges that its approach "could have its own issues."

What it means

If the proof stands, the consequences would be wide but not immediate. Every result of the form "no algorithm faster than 2^o(n) unless ETH fails" loses its footing, and many such results would need to be re-examined to see which survive under weaker assumptions. Wikipedia points out that SETH, the stronger Strong Exponential Time Hypothesis, is a separate assumption, and the OpenAI claim as quoted is about ETH. Which conditional bounds fall and which remain is exactly what the working group and the wider field would need to sort out.

For practitioners the news is less dramatic. A subexponential bound on counting is an asymptotic statement; it does not say anything about how fast a solver would run on real formulas. Engadget reports OpenAI as saying that practical speedups would take significant further research, and cautions that better algorithms in dependent fields are a conditional possibility, not a confirmed consequence.

For research culture, the more lasting question may be process. Whether a proof generated by a model, released with a machine-checked Lean certificate, should be trusted on the strength of the certificate, and who is responsible for checking that the formal statement says what the informal one does, is now a practical question for the people reading the files. OpenAI says it will not seek academic credit for the discoveries and that the expert groups receive credit for their write-ups.

What we don't know yet

• Whether the proof is correct. The working group had not published any assessment when we checked, and we found no statement from Impagliazzo, Paturi or Williams.
• What the algorithm's exact running time is. The sources we could open only say "subexponential"; the paper's details were not available to us in readable form.
• Whether the Lean formalisation states the theorem precisely as the paper does, and what, if anything, it assumes.
• How the physics claim holds up: the group led by David Gross had not published anything, according to Engadget.
• Whether other labs have made similar claims. We saw one mention of this on Wikipedia, but could not confirm it from a primary source, so we leave it out.

What to watch next

• A write-up or statement from the Impagliazzo–Paturi–Williams group, and any independent reading of the paper by complexity theorists.
• Responses to OpenAI's open letter on credit and early access.
• Whether the math manuscripts on local smoothing and Kakeya get independent confirmation.
• Release of the physics materials by the group led by David Gross.

Sources

• The Verge: OpenAI announces three big science discoveries and a new way to work with academics (26 October 2026)
• OpenAI: Building scientific understanding with academic communities (the announcement; we read it as quoted by The Verge because the page would not open for us)
• GitHub: The Exponential Time Hypothesis is False (OpenAI, 25 October 2026)
• Engadget: OpenAI announces new discoveries in mathematics, computer science and physics
• Wikipedia: Exponential time hypothesis