OpenAI has released solutions to three major math problems, including a rejection of the Exponential Time Hypothesis, a foundational assumption in computer science about computational difficulty, according to a report published by TechCrunch on October 27. Anthropic followed hours later with its own refutation of the hypothesis, though one of its mathematicians suggested OpenAI's work built on existing research. The claims have sparked mixed reactions from scientific communities, prompting computer scientists to form a working group to examine the findings and ask OpenAI to fund a conference to discuss them.
The Exponential Time Hypothesis asserts that even the fastest computer algorithm requires exponentially more time to solve a specific class of logic puzzles as the number of variables increases. OpenAI and Anthropic claim their models have developed algorithms that solve these puzzles in "sub-exponential" time, meaning faster than speeds previously thought achievable. The hypothesis is connected to the broader P versus NP question, which asks whether problems whose solutions can be quickly verified can also be quickly solved. Russell Impagliazzo and Ramamohan Paturi, computer scientists at UC San Diego, first published the Exponential Time Hypothesis in 1999 and are now helping interpret OpenAI's solution alongside MIT professor Ryan Williams.
Williams, who is organizing the computer science field's response to the finding, told TechCrunch that parts of OpenAI's proof appear routine, but "there are two or three alien-looking parts" that require the entire community to work on together. He noted that every computer scientist should "probably put a little more weight on the plausibility of P = NP" based on the claims. According to the report, Williams said the durability of the hypothesis has led to its inclusion in many scientific papers over the past decade that will need revisiting if the AI labs' proof holds up. Williams also doesn't believe OpenAI's algorithm "could possibly be the best algorithm you can get."
The hypothesis has underpinned cryptographic systems, which rely on the principle that decoding a message without the key takes too long to be useful, even though verifying a solution with the key is quick. Williams said he asked OpenAI science lead Dan Roberts whether the improved algorithm affects cryptographic systems relying on certain key sizes, and the lab reported it had checked and was reasonably confident the work doesn't imply any security breaks. Williams also called for OpenAI to support a conference on the topic because it will affect many researchers' work and the field needs to determine how its foundations should change. Williams has criticized OpenAI's past proof releases, calling an earlier October drop a "DDOS attack on mathematicians," but agreed to collaborate to help guide ideas vital to the field.
Williams said he remains optimistic despite concerns about training the next generation of scientists, noting that AI is "forcing people to be a little more ambitious about the kind of work that they do" and to reconsider their approach if previous problems become low-hanging fruit for AI. The computer scientists' working group has released an open letter calling for feedback from scientists interested in these problems and discussion of norms around AI contributions to their work. If the industry's leading labs can consistently crack decades-old mathematical barriers, research institutions may need to rethink not just verification protocols but the entire pipeline of how theoretical breakthroughs move from conjecture to peer acceptance. The shift could also pressure academic departments to clarify whether AI-generated proofs carry the same weight as human-authored work when evaluating tenure and publication standards.