OpenAI Says Its AI Refuted a Core Computing Hypothesis

OpenAI said that an internal AI model has produced a proof that the Exponential Time Hypothesis is false, a claim that outside computer scientists have not yet confirmed.

What OpenAI announced

In its announcement on Oct. 26, OpenAI wrote that "our system has recently proved that the ETH is false, a result that was subsequently verified in Lean," a programming language that checks proofs by machine. OpenAI says the model found a disproof in natural language on Oct. 16 and that it was formalized in Lean the next day, according to the company's post and The Next Web. OpenAI published the AI-written paper and the Lean proof on GitHub, as The Verge and The Next Web reported.

The announcement covered two other claimed results, one in mathematics and one in physics, which are not part of this story.

What ETH says

3-SAT is a puzzle about a long formula of true-or-false variables grouped into clauses of up to three. The question is whether some setting of the variables makes every clause true. Trying every setting takes about 2^n steps for n variables. Before this claim, the best known algorithms took about 1.308^n steps if they use randomness and about 1.328^n if they do not, according to Anthropic's paper. OpenAI's paper cites similar figures.

ETH says progress has a floor: there is some fixed constant for which 3-SAT cannot be solved in 2 to the power of that constant times n steps, in the worst case. Impagliazzo and Paturi proposed it with Francis Zane, OpenAI and The Next Web reported, and The Verge dates it to 1999. OpenAI says hundreds of papers have used it to show that problems in graph theory, computational biology, databases and other fields are hard.

What the papers claim

OpenAI's paper gives a deterministic algorithm that counts the satisfying assignments of any formula whose clauses have a fixed width, using memory that grows only as a polynomial. Its running time is roughly 2 to the power of n divided by the square root of log n, up to smaller factors. The paper says the 3-SAT case refutes ETH. Scott Aaronson, a computer scientist at the University of Texas at Austin, summarized the claim on his blog 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. The paper says it "does not imply that general NP problems admit subexponential time algorithms," because bounds of this kind do not carry over through the usual conversions between problems. Lance Fortnow, who writes the Computational Complexity blog, wrote on Oct. 27 that the claimed refutation does not reduce the running times of NP problems in general and that there is still no approach to settling P versus NP.

Anthropic's paper says its result is purely asymptotic and that its general approach seems unlikely to yield improvements "unless n > 10^7." OpenAI says turning the result into practical improvements "will require significant further research." The Decoder noted that real-world SAT solvers often handle formulas with millions of variables, because such formulas are usually easier than the worst case ETH describes.

What has been checked

Impagliazzo, Paturi and Williams are organizing what they call an open and independent examination. In an open letter to colleagues they wrote: "Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny." They also wrote: "If the claim is correct, it will change an important part of theoretical computer science."

Williams said on Bluesky that the three signed no nondisclosure agreements and are not paid, and that OpenAI agreed to release all its raw data and to sponsor a conference.

OpenAI says "verified in Lean," but its own scope note describes a narrower statement than the paper's headline. Lean proves exact counting in time about 2 to the power of n times (log log n) squared over the square root of log n, for formulas in a fixed encoding. The paper states a sharper bound, according to OpenAI's note, Kaino.dev and Papex. The Decoder noted that Lean only checks that a proof establishes the statement as written in Lean, so experts still have to judge whether that statement captures ETH.

OpenAI's repository also warns that some unformalized results "could have issues." On Oct. 7, OpenAI withdrew three unrelated manuscripts from its Oct. 6 release after a sign error, according to its change log and MACCUS.

A second lab makes the same claim

Anthropic posted a paper credited to Claude, titled "A 2^o(n) Time Algorithm for 3-SAT," on its GitHub page late Monday. It says the core algorithm was found on Oct. 16 by an internal Claude model "with 14M output tokens and no human input," and that "independently and concurrently, an internal model at OpenAI claims to have proven a similar result." Its repository includes a Lean formalization that is re-checked with a second, independent proof checker, according to Anthropic's page and Papex. The examination group's letter lists Anthropic's paper among its resources. Both labs give Oct. 16 as the date of discovery; those dates are the companies' own statements.

Reaction so far

Aaronson wrote on Oct. 26 that his students had come to his office to tell him an OpenAI model had refuted ETH. His post relays the claim and does not report a check. The examination group has not yet published a finding that confirms or disputes the claim.

OpenAI made an earlier claim in May, that an internal model had disproved the Erdős unit-distance conjecture. In that case a group of outside mathematicians had checked the proof and written a human-verified version, according to OpenAI and a paper on arXiv by those mathematicians. No comparable human-written verification of the ETH proof has been published.