OpenAI yesterday published AI-generated solutions to three significant mathematical problems that have long challenged researchers. One of the announcements unexpectedly asserted a refutation of the Exponential Time Hypothesis (ETH), a long-standing assumption in computer science that influences how researchers classify computational difficulty.
Mixed reaction: excitement and skepticism
As with previous proof releases from OpenAI, the scientific community reacted with a mix of enthusiasm and concern. Anthropic mathematician Levent Alpöge suggested that OpenAI’s solutions may have relied on pre-existing work, and hours later Anthropic published its own ETH refutation.
This time OpenAI organized the releases differently by discipline: mathematicians received the work on GitHub; computer scientists formed a working group and requested the proofs be shared publicly along with OpenAI funding a conference to discuss them; and physicists created a working group that will decide how to publish their result.
Coordinated response from computer science
MIT Professor Ryan Williams is coordinating the response from the computer science community. Williams, whose research focuses on computational complexity, has previously criticized OpenAI’s approach and called an earlier October proof drop a “DDOS attack on mathematicians.” Despite that, he agreed to work with the labs to help steward ideas that are important to the field.
OpenAI asked Williams to help interpret the solution alongside University of California San Diego computer scientists Russell Impagliazzo and Ramamohan Paturi, who first published the ETH in 1999. Their initial step was to release an open letter soliciting feedback from scientists interested in these problems and calling for discussion of norms around AI contributions to such work.
Williams said some parts of OpenAI’s proof look routine, but “there are two or three alien-looking parts” that convinced him the whole community needs to collaborate on the issue.
What ETH is and why it matters
The Exponential Time Hypothesis is part of the broader P versus NP family of questions. Broadly speaking, P vs NP asks whether every problem whose solution can be quickly verified (NP) can also be quickly solved (P). Sudoku is an everyday illustration: a completed solution is quick to verify, while finding the solution can be time-consuming.
Most researchers assume P ≠ NP; ETH has provided technical evidence supporting that assumption by stating that for certain classes of hard problems, the fastest algorithms require time that grows exponentially with the number of variables.
OpenAI and Anthropic claim their models found algorithms that solve those hard problems in “sub-exponential” time—faster than previously believed. If validated, those algorithms would amount to a scientific refutation of ETH and could open theoretical paths toward algorithms with implications for P = NP.
Potential consequences and outstanding questions
Williams said every computer scientist might increase the weight they give to the plausibility of P = NP, though the degree of belief will vary. He also said he does not expect OpenAI’s current algorithm to be the ultimate best algorithm.
Because ETH has been used as an assumption in many papers over the past decade, a confirmed refutation would require revisiting numerous results. That partly motivated Williams’s push for OpenAI to support a conference — beyond understanding the algorithms, the community needs to decide how foundational assumptions should change.
Before theoretical shifts, there are cybersecurity concerns. Improved algorithms could impact cryptographic systems that rely on certain key sizes. Williams asked OpenAI science lead Dan Roberts whether they had checked whether any crypto systems are affected; OpenAI says they checked and were reasonably confident the results did not imply immediate breaks.
AI’s evolving role in discovery and the future of research
The new AI-driven mode of scientific discovery is still maturing. Williams expressed cautious optimism despite substantive concerns, particularly about training the next generation of scientists. As someone who is both a computer scientist and works in high-level mathematics, he feels the transition may be easier for researchers with similar backgrounds than for pure mathematicians.
He also argued that AI is pushing researchers to be more ambitious in the questions they pursue: if many problems that were once challenging become “low-hanging fruit” for AI, scientists must raise the bar and focus on deeper, more fundamental problems.
Overall, the published claims have sparked significant debate across computer science and mathematics. The coming weeks and months of community scrutiny and verification will determine to what extent the AI-proposed proofs change the field’s foundations and practices.
