ReadingResearchRadarInvestment framework
Sign in / Sign up
← Back to reading
NewsStructural4 min readDisconfirmAI Editorial

MIT Professor of Computational Complexity Ryan Williams: AI Claims to Refute Exponential Time Hypothesis, Credibility of P=NP Rises

OpenAI and Anthropic have respectively released AI-generated mathematical proofs claiming to overturn the long-held belief in computer science regarding the Exponential Time Hypothesis (ETH). MIT professor of computational complexity Ryan Williams explains the implications of this discovery for the P versus NP problem, the verification efforts being organized by the community, and why he believes this is 'probably not the final answer.'

2026-10-28 01:08 GMT+8

In October 2026, OpenAI released solutions to three blockbuster math problems that have long vexed researchers. One was a surprise rejection of the Exponential Time Hypothesis (ETH), a durable assumption in computer science that plays a large role in how we understand what is difficult to compute. Hours later, Anthropic also released its own refutation of ETH.

Ryan Williams, a professor at the Massachusetts Institute of Technology (MIT) specializing in computational complexity, is organizing his field’s response to this new finding. Williams has previously criticized OpenAI’s approach, calling its proof dump earlier in October a “DDOS attack on mathematicians.” However, he agreed to collaborate with frontier labs to help shepherd ideas vital to the field. OpenAI asked him to help interpret the solution, working alongside Russell Impagliazzo and Ramamohan Paturi, computer scientists at the University of California, San Diego, who first published the ETH in 1999.

Williams explained the meaning of the ETH to TechCrunch: it essentially states that even the fastest computer algorithms require exponentially more time to find a solution as the number of variables grows within a specific class of tricky logic puzzles. The ETH is part of the broader P versus NP problem. The core question of P versus NP is whether a problem whose solution can be quickly verified can also be quickly solved. Williams used Sudoku as an example: once a solution is laid out, you can verify it quickly, but finding that solution is time-consuming. This dynamic exists across many important problems and underpins cryptographic systems—when you have the key, you can decode the message, but cracking an effective code takes too long to be practically useful.

Sign in / Sign up
ReadingResearchRadarInvestment framework

The claims from OpenAI and Anthropic are that their models have developed algorithms to solve these puzzles in “sub-exponential” time, meaning faster than previously thought possible. If true, they may have proven the ETH false and potentially opened a path for algorithms that generally achieve P = NP.

"Every computer scientist should probably put a little more weight on the plausibility of P = NP, but one’s weight may vary," Williams said. "I do think that it kind of calls into question a lot of the intuitions that we thought we had about … how tractable [hard NP problems] are. I also think that this is probably not the final answer either. I don’t think that OpenAI’s algorithm could possibly be the best algorithm you can get."

Williams pointed out that the durability of the ETH has led to its inclusion in many scientific papers over the past decade, which will need to be revisited if the AI labs' claims that they have proven it wrong hold up. "This is partly why I was asking or pushing OpenAI to support a conference on this — it’s going to affect many researchers’ works, and we need to figure out, okay, what happens next besides understanding the algorithms. We need to understand, how should the foundations change compared to what we had before?"

Their first step was to release an open letter calling for feedback from scientists interested in these problems and a discussion of the norms around AI contributions to their work. Williams said, "Some parts [of OpenAI’s proof] are, maybe you could say routine, but then yes, there are two or three alien-looking parts, and it’s exactly these parts that I saw that made me think, wow, this is something the whole community needs to work on together."

Before scientific concerns, there are cybersecurity questions. Williams noted that improved algorithms could imply that cryptographic systems relying on certain key sizes might be considered broken. One of the first questions he asked Dan Roberts, OpenAI’s science lead, was whether they had checked if this affects any crypto systems or if anything is now insecure. According to Williams, they checked and were "reasonably confident that this didn’t … imply any breaks."

Williams remains optimistic about AI as a new paradigm for scientific discovery, despite real concerns, particularly regarding the training of the next generation of scientists. He says AI is "forcing people to be a little more ambitious about the kind of work that they do, and to think more deeply about, okay, if all the things I used to work on are now low-hanging fruit for AI, how can I raise the bar for the kind of scientific questions I want to ask?"

Sources

  • techcrunch.comTechCrunch↗
Continue researching →