OpenAI and Anthropic Models Claim to Refute a Foundational Complexity Theory Assumption

OpenAI just dropped solutions to three major math problems, and one of them is the kind of result that makes computational complexity theorists sit up straight. The company claims its models produced a refutation of the Exponential Time Hypothesis (ETH), a decades-old assumption that underpins how computer scientists reason about which problems are actually hard to solve. Anthropic, not to be outdone, released its own ETH refutation hours later.

If that sounds like inside baseball, stick with me, because the implications touch cryptography, algorithm design, and the entire P vs NP question that's been sitting unresolved since the 1970s.

The reception from the scientific community was, predictably, a mix of excitement and suspicion. Anthropic mathematician Levent Alpöge publicly suggested OpenAI's solution leaned heavily on pre-existing work. That kind of pushback has become a pattern with these AI-generated proof drops: a lab publishes, outside researchers scrutinize, and the credit-and-correctness debate plays out on social media before anyone's had time to actually verify the math.

What's different this time is the delivery mechanism. OpenAI tailored its release strategy by discipline. Mathematicians got a straight GitHub dump. Physicists got a working group that will decide how to release their result. Computer scientists, though, pushed back and got a different deal: a public proof, plus OpenAI funding a conference to actually discuss it.

That computer science response is being organized by MIT professor Ryan Williams, a complexity theorist who's been openly critical of how these labs have handled previous releases. Earlier this month he called one of OpenAI's proof dumps a "DDOS attack on mathematicians," which tells you where his starting skepticism lived. He still agreed to help interpret this result, working alongside UC San Diego's Russell Impagliazzo and Ramamohan Paturi, who literally coauthored the 1999 paper that introduced ETH in the first place.

Why ETH Actually Matters

Here's the quick version of the theory, for anyone who hasn't thought about P vs NP since an undergrad algorithms class.

NP problems are ones where a proposed solution is easy to check but potentially brutal to find. Sudoku is the classic example: verifying a completed grid takes seconds, but solving a hard puzzle from scratch can take a lot longer. The P vs NP question asks whether every problem that's easy to verify is also secretly easy to solve, we just haven't found the trick yet. Most computer scientists bet that P does not equal NP, because the alternative seems too good to be true. As Williams put it to 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 too good to be true."

ETH has been one of the load-bearing assumptions behind that bet. It states that for a specific family of hard logic problems, the best possible algorithm needs time that grows exponentially with the number of variables, no shortcuts, no clever tricks. It's been cited across a decade of complexity theory papers as a kind of trusted baseline for "yes, this really is hard."

Now OpenAI and Anthropic are both claiming their models found algorithms that solve these problems in sub-exponential time, meaning meaningfully faster than ETH said was possible. If the math holds up, that's a genuine refutation, and it nudges the needle, however slightly, toward P = NP being plausible after all.

Williams isn't ready to declare victory for either side, but he's recalibrating. "Every computer scientist should probably put a little more weight on the plausibility of P = NP, but one's weight may vary," he said. He's also skeptical this is the final word on the algorithm itself: "I don't think that OpenAI's algorithm could possibly be the best algorithm you can get."

The practical fallout is already keeping him up at night. ETH shows up as a load-bearing assumption in a huge number of published complexity papers. If it's actually false, those papers need to be revisited, not necessarily thrown out, but reexamined. That's part of why Williams pushed for the conference: it's not just about verifying the proof, it's about figuring out what else in the field now needs rebuilding.

There's also a more immediate, less academic concern: cryptography. A lot of encryption schemes lean on the assumption that certain problems are computationally infeasible to crack within a human lifetime, which is exactly the kind of guarantee ETH-adjacent results could threaten if key sizes turn out to be less secure than assumed. Williams said one of his first questions to OpenAI science lead Dan Roberts was whether the company had checked for exactly that. According to Williams, OpenAI had, and came away "reasonably confident that this didn't imply any breaks" in existing crypto systems. That's reassuring, but it's also the kind of claim that the field will want to independently verify rather than take on faith from the lab that built the model.

What to Watch

This episode is really a case study in how frontier labs, academic fields, and AI models are going to negotiate the norms of AI-assisted discovery going forward, and nobody's fully worked out the rules yet.

Williams, despite his earlier "DDOS" criticism, sounds cautiously optimistic about the overall trajectory, even as he flags real concerns about training the next generation of researchers if AI starts eating the low-hanging fruit of a field. His read: the pressure is forcing working scientists to raise their ambitions. "If all the things I used to work on are now low-hanging fruit for AI, how can I raise the bar for the kind of scientific questions I want to ask?" That's probably the most useful framing to carry forward, whether or not this particular ETH result survives the community's scrutiny. Watch for the computer science working group's conference and the formal writeup, since that's where we'll find out if the "alien-looking parts" of the proof that caught Williams's attention actually hold up under peer review.