AI Labs Claim Breakthrough Refuting Exponential Time Hypothesis

OpenAI released solutions to three long-standing mathematics problems yesterday, with its most prominent claim being a refutation of the Exponential Time Hypothesis, a foundational assumption that has shaped computer science research for decades. Anthropic mathematician Levent Alpöge initially questioned whether OpenAI was drawing from pre-existing work, but hours later, Anthropic released its own claimed refutation of the same hypothesis, corroborating the core finding. If the claims withstand scrutiny, they would overturn a principle that has guided computational theory since 1999 and potentially reshape how researchers understand what computers can and cannot do efficiently.

What the Exponential Time Hypothesis Claims

The core principle and Sudoku example

The Exponential Time Hypothesis belongs to a family of problems known as P vs NP, which has preoccupied computer scientists for decades. The central question asks whether every problem whose solution can be verified quickly can also be solved quickly.

MIT computer scientist Ryan Williams, who is coordinating the research community’s response to OpenAI’s claims, explained the concept through Sudoku. Once someone fills in the grid, verifying the solution takes seconds. Finding that solution through trial and error takes far longer. This asymmetry between verification and solving appears across many computational problems, including those underlying encryption. With a cryptographic key, decoding a message is instant. Cracking the code without the key would take longer than any practical attack allows.

Why ETH provided reassurance to computer scientists

The scientific consensus assumes P ≠ NP, meaning that most problems whose solutions can be verified quickly cannot be solved quickly. If the inverse were true (if P = NP), then every problem you could verify in seconds could be solved in seconds. As Williams told TechCrunch, “P = NP is asserting that this is true for every single problem you can verify quickly — if you can verify it quickly, you can solve it quickly. So this just seems that just seems too good to be true.”

The Exponential Time Hypothesis provided mathematical support for this belief. Formulated in 1999 by UC San Diego computer scientists Russell Impagliazzo and Ramamohan Paturi, the ETH stated that solving certain logic puzzles requires algorithms to work exponentially harder as the number of variables increases; a barrier that seemed unbreakable. Over the past decade, researchers built hundreds of papers on the assumption that this principle holds, making it one of the foundational beliefs in computational complexity theory.

The OpenAI and Anthropic Claims

Read also: iOS 27.2 Extends Siri to Five Languages and Adds iPhone Duo Features · Nvidia Backs Simplismart’s $14M Funding for GPU-Efficient AI Inference · Grok Debuts AI-Generated Odyssey Episode in Musk’s Bid Against Nolan · Google Releases Genie 4 World Model With Real-Time Audio Generation

Sub-exponential algorithms and what that means

OpenAI released its solutions on GitHub, claiming that its models produced algorithms capable of solving the types of logic puzzles covered by ETH in “sub-exponential” time. This means faster than the computational limits previously believed to apply. The algorithms would not solve these problems instantly, but they would scale better than existing methods as the number of variables grew.

If accurate, this would suggest that the Exponential Time Hypothesis itself is false and might point toward algorithms that could eventually solve NP problems in P time, potentially raising the specter of P = NP being true.

Different release strategies for different fields

OpenAI did not treat all three solutions equally. Mathematicians received the work on GitHub. Computer scientists formed a working group that requested public sharing of the proofs and asked OpenAI to fund a conference to discuss the findings. Physicists established their own working group to determine how their result would be released. This approach acknowledged that different research communities have different norms for evaluating and sharing work, rather than imposing a single release method across all disciplines.

How the Research Community Is Responding

What makes the proof noteworthy to specialists

Williams, who previously called OpenAI’s approach to releasing mathematical proofs a “DDOS attack on mathematicians,” agreed to help interpret these new findings. He was joined by Impagliazzo and Paturi, the computer scientists who formalized ETH. In describing the OpenAI work to TechCrunch, Williams noted that while many sections follow standard mathematical reasoning, “there are two or three alien-looking parts, and it’s exactly these parts that that I saw that made me think, wow, this is something that the whole community needs to work on together.”

The unusual sections apparently contain novel approaches or insights that diverge from conventional computer science methods, which is why they demand community scrutiny.

Raising the probability of P = NP

Williams was cautious about drawing final conclusions. “I don’t think that OpenAI’s algorithm could possibly be the best algorithm you can get,” he said. However, the implications for theoretical understanding are substantial. “Every computer scientist should probably put a little more weight on the plausibility of P = NP, but one’s weight may vary. 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.”

The findings force researchers to reconsider fundamental assumptions about what is computationally tractable. They do not necessarily solve P vs NP, but they shift the conversation about what is possible.

Cryptography and Security Implications

The immediate question: Are current systems vulnerable?

Security concerns took priority in the initial review. Williams said that improved algorithms could theoretically render some cryptographic systems reliant on certain key sizes vulnerable. One of his first questions to OpenAI science lead Dan Roberts was whether the claimed algorithms affect any currently deployed encryption systems. According to Williams, OpenAI “checked, and they were reasonably confident that this didn’t … imply any breaks.” Current cryptographic systems appear safe for now, though the research remains preliminary.

Why the process matters as much as the result

Williams emphasized that the durability of ETH has led to it appearing in many papers over the past decade that will need to be revisited if the claims hold up. He pushed OpenAI to support a conference specifically to help researchers understand the implications. “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, what should the foundations be that we had before?”

What This Means for the Future of Scientific Discovery

Despite concerns about the process, Williams expressed qualified optimism. He sees AI involvement in fundamental research as pushing scientists to pose more ambitious questions. “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 the kind of scientific questions I want to ask?”

One challenge remains: how younger researchers will develop expertise when foundational problems are solved by AI systems. Williams acknowledged this tension, though he suggested that researchers with deep mathematical training may adapt more easily than those focused purely on theoretical foundations.

Source: TechCrunch