OpenAI claims a disproof of the Exponential Time Hypothesis

OpenAI announced three discoveries spanning mathematics, computer science and physics, including its claim that an AI system disproved ETH.[1] The company says the system found the natural-language disproof on Oct. 16, 2026, and that the result was formalized in Lean the following day.[1] OpenAI says the result was subsequently verified in Lean and that it released both the AI-generated writeup and a Lean proof in a public GitHub repository.[1]

The paper describes a deterministic algorithm that counts satisfying assignments of a k-CNF in subexponential time and polynomial space.[3] ETH has been widely believed and used in hundreds of papers to derive conditional computational-hardness results.[1] OpenAI says the refutation reopens questions about how much faster these tasks could become and may help guide the search for better algorithms.[1] The claim does not solve the broader P-versus-NP problem.[4] That distinction matters: the reported result challenges a central assumption used for conditional results, rather than resolving a broader question about the limits of computation.

The article describes possible future uses—including computers cracking encryption and designing medicines by optimizing proteins—as theoretical scenarios.[2] Impagliazzo said a fast algorithm for solving Sudoku could be used to design optimal circuits.[2] Ryan Williams said the result has no immediate practical applications, and the article notes that realizing the potential of a theoretical result can take years or decades of engineering.[2] A separate report says improved algorithms could affect cryptographic systems that rely on certain key sizes.[5] These possibilities should not be read as evidence that current encryption has been broken or that the algorithm is ready for practical use.

OpenAI says a group led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams will verify and shepherd the work, and that it agreed to fund a conference on the result’s implications.[1] Science reported that neither OpenAI’s nor Anthropic’s proof had yet been fully confirmed by a human.[4] Anthropic announced an ETH refutation shortly after OpenAI’s announcement.[2] Science also reported that Anthropic counted more than 800 papers relying on ETH or a stronger version; Williams said researchers would need to revisit such work if the AI labs’ claims hold up.[4][5] The evidence also calls for making all raw results data public to facilitate independent verification.[1]