OpenAI released solutions to three blockbuster math problems that have long vexed researchers, including a surprise rejection of the Exponential Time Hypothesis (ETH), a long-standing assumption in computer science about what is difficult to compute. Scientific communities responded with a mixture of thrill and dismay. Anthropic mathematician Levent Alpöge suggested OpenAI was building on pre-existing work, and hours later Anthropic released its own refutation of ETH. OpenAI also structured its releases differently by field: mathematicians received a GitHub drop, computer scientists formed a working group and asked OpenAI to share the proofs publicly and fund a conference, and physicists formed a working group to decide how their result would be released.

MIT professor Ryan Williams, a computational complexity researcher who previously called OpenAI‘s proof dump a “DDOS attack on mathematicians,” agreed to help shepherd the field’s response. He was asked to interpret the solution alongside UC San Diego’s Russell Impagliazzo and Ramamohan Paturi, who first published ETH in 1999. Their first step was an open letter calling for feedback from interested scientists and a discussion of norms around AI contributions. Williams told TechCrunch that while some parts of the proof are routine, there are “two or three alien-looking parts” that convinced him the whole community needs to work on them together.

ETH is part of the broader P vs NP problem, which asks whether problems that can be easily verified (NP) can also be easily solved (P). As Williams explained, with Sudoku a solution can be quickly checked but is time-consuming to find; P = NP would mean every quickly verifiable problem can be solved quickly, which “seems too good to be true.” Most researchers assume P ≠ NP, and ETH has been supporting evidence: it says that even the fastest algorithm needs exponentially more time as the number of variables grows in a specific class of logic puzzles. OpenAI and Anthropic claim their models produced algorithms that solve those puzzles in sub-exponential time, which would refute the hypothesis and perhaps open a path toward P = NP. Williams said every computer scientist should probably put more weight on the plausibility of P = NP, but he added that this is probably not the final answer and that OpenAI‘s algorithm could not possibly be the best possible one.

Because ETH has underpinned many papers over the past decade, those works would need to be revisited if the refutation holds. Williams said he pushed OpenAI to fund a conference because many researchers are affected and the field needs to understand what the foundations should be. Before settling the scientific concerns, there are cybersecurity questions: an improved algorithm could imply that cryptographic systems relying on certain key sizes are broken. Williams asked OpenAI science lead Dan Roberts whether any crypto systems are now insecure; Roberts said they had checked and were reasonably confident no breaks are implied. Williams is optimistic about AI-driven scientific discovery despite concerns about training the next generation, and he believes AI is forcing researchers to be more ambitious about the kind of scientific questions they ask.