OpenAI claims ETH is false

On Monday 26 Oct 2026 OpenAI updated its public maths repository and published a blog post about three model results and how researchers can check them. The computer-science result is a 67-page paper titled bluntly “The Exponential Time Hypothesis is False”. Its abstract: “We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary k-CNF formula … Our algorithm refutes the Exponential Time Hypothesis (ETH), which postulates that deciding 3-SAT on n variables requires 2^Ω(n) time in the worst case.”

The running time is subexponential but only just: 2 to the power n/(log n)^(1/2+o(1)). That is far from practical, but ETH only says that no 2^o(n) algorithm exists, so any such bound refutes it. Because the algorithm counts solutions exactly and deterministically, the paper says it also refutes the Strong ETH, Gap-ETH and the nondeterministic NSETH.

Unlike the 6 Oct release, OpenAI did not just post the files. Its changelog says an outside working group led by Russell Impagliazzo and Ramamohan Paturi (who formulated ETH) and Ryan Williams (MIT) “will examine and explain the proof”, and that the materials went public at once “at the group’s request”. OpenAI’s Lean scope note says the formal proof covers a slightly weaker time bound, (log log n)² instead of log log n in the exponent.

The blog post itself could not be read here (HTTP 403). Its RSS summary and the press relays name the other two results: the local smoothing conjecture in every dimension, with the Kakeya conjecture as a corollary (separate entry), and a rigorous existence proof for four-dimensional quantum field theories including QCD and pure Yang–Mills, to be reviewed by a group led by David Gross. The QFT materials are withheld at the reviewers’ request (separate entry, OpenAI claims 4D Yang–Mills and QCD existence).

ETH is a working assumption across complexity theory. Hundreds of lower bounds in parameterized and fine-grained complexity are stated “assuming ETH”. If the proof holds, those results lose their footing. Lean covers the main theorem, so the open questions are whether the Lean statement says what the paper claims and whether the encoding and machine model match the usual meaning of ETH. Those are the questions the working group will answer. Until it reports, treat this as an extraordinary claim from a company, made without peer review.

Nobody has published a refutation. The first experts to comment took the claim seriously and stayed cautious. Ryan Williams, who sits on the working group, explained it for non-experts and said he had asked OpenAI to check that existing cryptosystems are not affected (“Apparently they are safe”). Ryan O’Donnell pointed out that the reductions behind ETH-based lower bounds still hold; what goes is their premise. He also posted an LLM-assisted 12-page exposition of a special case, saying he had “no idea if it’s correct”. Scott Aaronson moved his P = NP estimate from 3% to 5% and fell back to a weaker form of the hypothesis. Stefan Szeider worked out from the paper’s own constants that the algorithm only beats exhaustive search on inputs with at least 2^131071 variables, a number the paper does not state. He also read the Lean statement and found that it states the intended (weaker) result. So the claim is a pure theory result: if it holds, the ETH-conditional lower bounds lose their premise, and for any input that fits in a computer nothing gets faster.