OpenAI and Anthropic Claim AI Models Refuted the Exponential Time Hypothesis

OpenAI yesterday released solutions to three long-standing mathematics problems, including a surprise refutation of the Exponential Time Hypothesis (ETH), a durable assumption in computer science that shapes how researchers understand what is hard to compute. Hours later, Anthropic released its own refutation of ETH.

The claims arrive with high stakes. ETH underpins a large body of research on computational hardness, and it sits inside the broader P versus NP question that has animated computer science for decades. If the AI-produced algorithms hold up, they could force a revisit of many scientific papers published over the past ten years and shift assumptions about the security of cryptographic systems.

Anthropic mathematician Levent Alpöge suggested that OpenAI based its solutions on pre-existing work, according to the source report. Anthropic then released its own refutation shortly afterward. Scientific communities responded with what the report describes as a mixture of thrill and dismay — a pattern familiar from previous proof-drops by the frontier lab.

How each discipline is handling the proofs

OpenAI structured this release differently for each of the three disciplines involved:

• Mathematicians received the work directly on GitHub.
• Computer scientists formed a working group, asked for the proofs to be shared publicly, and asked OpenAI to fund a conference to discuss them.
• Physicists formed a working group that will determine how their result will be released.

MIT Professor Ryan Williams, a computer scientist whose research focuses on computational complexity, is organizing his field's response to the new finding. Williams has criticized OpenAI's approach before, calling its earlier proof dump in October a "DDOS attack on mathematicians."

Despite that criticism, he agreed to collaborate with the frontier labs to help shepherd ideas he considers vital to the field, he told TechCrunch. OpenAI asked him to help interpret the solution, along with UC San Diego computer scientists Russell Impagliazzo and Ramamohan Paturi — the two researchers who first published the ETH in 1999.

Their first step was an open letter calling for feedback from scientists interested in these problems and for a discussion of the norms around AI contributions to their work.

"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 that I saw that made me think, wow, this is something that the whole community needs to work on together," Williams told TechCrunch.

What is the Exponential Time Hypothesis?

The ETH belongs to the broader class of problems known as P versus NP, which has driven research in computer science and many other fields for decades. In reductive terms, researchers are trying to determine whether any problem whose solution can be quickly verified (NP) can also be quickly solved (P).

A simple example is Sudoku. Once a solution to a puzzle is in place, it can be verified quickly, but finding the solution takes time. That dynamic holds across a range of important problems, and it underpins cryptographic systems: with the key to an encoded message, you can reveal it, but cracking an effective code takes too long to be useful.

Scientists have not proven whether that asymmetry always holds.

"P = NP is saying that, not only can you verify Sudoku solutions when they exist, you can just generate them," Williams said. "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."

That intuition is why most scientists assume that P ≠ NP. ETH supplied evidence for that assumption. In essence, it states that even the fastest computer algorithm needs exponentially more time to find a solution as the number of variables grows in a specific class of tricky logic puzzles.

OpenAI and Anthropic claim their models produced algorithms that solve those puzzles in "sub-exponential" time — faster than previously thought possible. If true, the labs may have refuted ETH and possibly opened a path toward algorithms that generally perform as if P = NP.

What does the claim change for the field?

"Every computer scientist should probably put a 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."

The durability of ETH has led to its inclusion in many scientific papers over the past decade. Those papers will need revisiting if the AI labs' claims hold up, Williams said.

"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?" he said.

Are cryptographic systems at risk?

Before the scientific questions come the cybersecurity ones. Williams said an improved algorithm could imply that cryptographic systems relying on certain key sizes should be considered broken.

One of his first questions to OpenAI science lead Dan Roberts, he said, "was if they had checked that that this affects any crypto systems … is anything insecure now? And apparently, they checked, and they were reasonably confident that this didn't … imply any breaks."

That reassurance matters because ETH-adjacent assumptions sit behind widely deployed cryptography. A genuine sub-exponential algorithm for the relevant class of logic puzzles would reset the calculus on key sizes and hardness guarantees that much of modern encryption leans on.

What comes next for AI-driven discovery?

This new paradigm of AI-assisted scientific discovery remains a work in progress. Williams says he is optimistic despite real concerns, particularly about training the next generation of scientists. His own background as a computer scientist who does high-level math has, he suggested, made the adjustment easier for him than for pure mathematicians.

He also sees a forcing function in the technology. 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?" Williams said.

The immediate next steps are already in motion: the computer science working group's open letter, the requested public release of the proofs, and the push for an OpenAI-funded conference to re-examine the foundations of the field. Whether ETH actually falls will depend on how those "alien-looking" proof sections withstand the scrutiny Williams is now organizing — with the help of the two researchers, Impagliazzo and Paturi, who formulated the hypothesis in 1999.