OpenAI and Anthropic claim their AI models have refuted a foundational computer science assumption
OpenAI and Anthropic say their models found sub-exponential algorithms for logic puzzles, potentially disproving ETH and challenging assumptions behind P vs NP. MIT’s Ryan Williams called OpenAI’s proof “alien-looking” and urged broad review.
OpenAI announced in October 2026 that its AI models had produced solutions to three long-standing mathematics problems, including a rejection of the Exponential Time Hypothesis (ETH) — a core assumption in computer science that shapes how researchers understand computational difficulty. Hours after OpenAI’s release, Anthropic published its own refutation of ETH.
The ETH is connected to the broader P vs NP problem, one of the most debated questions in computer science. It holds that even the fastest algorithms require exponentially more time to solve a specific class of logic puzzles as the number of variables grows. OpenAI and Anthropic now claim their models have found algorithms that solve those puzzles in “sub-exponential” time — faster than previously thought possible — which, if verified, would prove ETH false and could open a path toward algorithms that demonstrate P = NP.
MIT Professor Ryan Williams, a computer scientist specializing in computational complexity, is leading his field’s response to the finding. He described portions of OpenAI’s proof as “alien-looking” and said the work requires broad community review. Williams had previously criticized OpenAI’s earlier proof releases as a “DDOS attack on mathematicians,” but agreed to collaborate alongside UC San Diego computer scientists Russell Impagliazzo and Ramamohan Paturi, who originally published the ETH in 1999. The three issued an open letter inviting scientific feedback.
Williams said one of his first questions to OpenAI’s science lead was whether the new algorithm compromised any existing cryptographic systems. He said OpenAI checked and was “reasonably confident” no current systems were at risk, though the finding may suggest that cryptographic systems relying on certain key sizes could warrant closer scrutiny.
If the claims hold up, a significant portion of scientific literature built on ETH over the past decade may need to be revisited. Williams pushed OpenAI to fund a conference to help researchers work through the implications. He noted the AI-driven pace of discovery is raising questions about the future role of human scientists, but said he views it as pressure to pursue more ambitious research questions.