OpenAI and Anthropic refute the Exponential Time Hypothesis
On 26 October OpenAI posted a Lean-checked algorithm that solves 3-SAT in subexponential time, and Anthropic posted its own a few hours later. By Wednesday Lance Fortnow wrote that the hypothesis could be assumed false.
Source published · In the Weekly Review of 1 November 2026
Filed under Mathematics, Reasoning and inference
The Exponential Time Hypothesis says that 3-SAT, deciding whether an AND of three-variable clauses can be satisfied, needs time exponential in the number of variables \(n\). Hundreds of conditional hardness results rest on it. On 26 October OpenAI said one of its internal models had found an algorithm running in time \(2^{o(n)}\), and published a natural-language write-up and a Lean proof. Hours later Anthropic published its own paper, titled “A 2^o(n) Time Algorithm for 3-SAT” and credited to “Claude, Anthropic”, which Anthropic dates to 16 October.
The week moved towards acceptance. Ryan O’Donnell and Shiva Kintali posted simplified proofs. OpenAI said it would work with Russell Impagliazzo, Mohan Paturi and Ryan Williams to verify and study the result, and on 29 October the three opened a site with a discussion blog and a paper repository. Fortnow, who said he had not checked the proof himself, wrote that it was safe to assume the hypothesis was false.
The same OpenAI release claimed the Kakeya conjecture in every dimension and the existence part of the Yang-Mills problem. The Yang-Mills paper has not yet been made public, and the mass-gap half of that Millennium Prize Problem remains open.