OpenAI says its AI disproved a core assumption of computer science; experts are reviewing it
OpenAI claims an AI-found algorithm refutes the Exponential Time Hypothesis, with a checked proof. The idea's originators are reviewing it.
Many results in computer science rest on the Exponential Time Hypothesis (ETH). It assumes that 3-SAT, the classic problem of deciding whether a logical formula can be made true, cannot be solved much faster than by checking an exponential number of possibilities.
On 26 October 2026 OpenAI added a manuscript to its openai/math repository. It gives an algorithm that exactly counts the solutions of k-SAT formulas in subexponential time (much faster than exponential), for every fixed k, using a modest amount of memory. If correct, the 3-SAT case refutes ETH and the stronger SETH. According to OpenAI, as reported by The Next Web, the model found the algorithm on 16 October and it was checked in Lean, a proof-checking language, on 17 October.
Russell Impagliazzo and Ramamohan Paturi, who proposed ETH, are leading an independent review with Ryan Williams. They stress that this is not certification; Williams says they signed no NDAs and are unpaid. Lance Fortnow, who had not checked the proof himself, judged ETH very likely dead. He noted that results built on ETH don’t automatically become false. Ryan O’Donnell and Shiva Kintali posted simpler alternative proofs, and Anthropic released a companion paper.
On the same day OpenAI also claimed the Kakeya conjecture in all dimensions and, through a physics group led by David Gross, the existence of 4D quantum field theories including pure Yang–Mills. The physics material was not released.
What it means
If the review confirms it, a basic assumption that many computer science results lean on is false, and those results would need new support, though they don’t automatically become false. It would not make hard everyday problems such as route planning fast, and it says nothing about P vs NP. For now it is a claim under expert review.
Caveats
- The result is about k-SAT only. It gives no fast algorithm for all of NP, says nothing about P vs NP, and does not speed up problems such as Subset Sum or the travelling salesman problem.
- It is under review, with no independent confirmation in the sources we read.
- Fortnow notes the Lean version proves a slightly weaker bound than the paper, and sources state the exact running time differently.
- The Kakeya and Yang–Mills claims are OpenAI’s alone; the physics material was unreleased.