OpenAI and Anthropic claim their models refuted the Exponential Time Hypothesis

AI labs claim a landmark complexity result

OpenAI has released solutions to three major mathematical problems, and one of them is a claimed refutation of the Exponential Time Hypothesis (ETH), a long-standing assumption in computer science about which computations are fundamentally difficult. According to TechCrunch, the release drew a familiar mix of excitement and unease: Anthropic mathematician Levent Alpöge suggested OpenAI's solutions were derived from earlier work, and within hours Anthropic published a refutation of ETH of its own.

OpenAI also changed how it hands results to each field. Mathematicians received the work as a repository on GitHub. Computer scientists formed a working group that asked for the proofs to be made public and for OpenAI to fund a conference around them. Physicists set up a working group that will decide how their result is released.

A field organizing itself around the proofs

MIT professor Ryan Williams, who works on computational complexity, is organizing his discipline's response. He has been critical of OpenAI's approach before, describing an earlier proof dump this October as a "DDOS attack on mathematicians," but agreed to work with the lab on a result he considers vital to the field. OpenAI also brought in UC San Diego computer scientists Russell Impagliazzo and Ramamohan Paturi, who first published ETH in 1999.

The group's first move was an open letter inviting scientists to give feedback and to discuss norms for AI contributions to research. Williams told TechCrunch that parts of OpenAI's proof look routine, but a few sections struck him as unfamiliar — "two or three alien-looking parts" that convinced him the wider community needs to examine the work together.

What ETH says and why it is contested

ETH sits inside the larger P versus NP question, which asks whether every problem whose answer can be checked quickly can also be solved quickly. Sudoku is the standard illustration: verifying a completed grid is fast, but finding the solution takes far longer. Modern cryptography leans on the same asymmetry — with the right key a message decodes instantly, while cracking the code without it takes impractically long.

Nobody has proven which way the question resolves, and most researchers assume that fast verification does not guarantee fast solving. ETH backed that assumption: it holds that even the best possible algorithms need exponentially more time as the number of variables grows in a particular family of hard logic puzzles.

The labs' claim is that their models produced algorithms that crack those puzzles in sub-exponential time, faster than ETH allows. If the proofs hold, ETH is false, and the result could point toward algorithms that behave as though P equals NP. Williams put it cautiously, telling TechCrunch that every computer scientist should assign somewhat more weight to the plausibility of P = NP, while adding that he does not expect OpenAI's algorithm to be the best achievable.

Literature to revisit, crypto checked

Because ETH has been assumed in a large body of work, Williams said many papers from the past decade would need revisiting if the refutation stands. That is part of why he pushed for a conference: researchers must work out how the field's foundations should change, beyond simply understanding the new algorithms.

The immediate practical question is security. A sufficiently faster algorithm could render cryptographic systems with certain key sizes breakable. Williams said one of his first questions to OpenAI science lead Dan Roberts was whether the result affects any cryptography; OpenAI had checked and was reasonably confident it does not imply any breaks.

Williams also flagged concerns about training the next generation of scientists, though he remains broadly optimistic. In his view, AI is pushing researchers to be more ambitious and to think harder about which questions to pursue, now that some problems once considered deep may be low-hanging fruit for machines.

Why it matters

ETH has quietly underwritten decades of thinking about computational hardness and, indirectly, about what keeps encryption secure. If machine-generated proofs genuinely overturn it, a large body of published results rests on an assumption that no longer holds, and the boundary between hard and tractable problems shifts. The episode is also a live test of how science absorbs AI discoveries: results of this consequence are arriving faster than verification and publication norms can adapt, and how researchers respond will shape both complexity theory and the way frontier labs hand such findings to the world.