OpenAI and Anthropic Say Their AI Ruled Out the ETH Hardness Hypothesis
The Exponential Time Hypothesis (ETH) holds that for hard puzzles such as a huge Sudoku, the time needed to find a solution grows explosively with the number of variables. OpenAI said its model found an algorithm that solves them faster, and hours later Anthropic published its own refutation. If the claims hold up, many papers that rely on ETH will need to be revisited, but for now these are statements, not an accepted proof. Ryan Williams of MIT is gathering scientists' reactions and asking for the proofs to be made public. OpenAI checked and says the new algorithm does not imply any breaks of cryptosystems.
AI-processed from TechCrunch; edited by Hamidun News
Imagine you are building a service that has to assign shift schedules, courier routes or compatible package versions. Such tasks often run into brute-force search: the more inputs, the sharply longer the answer takes to find. Computer scientists have long debated whether this ceiling can be bypassed. Now two AI labs, OpenAI and Anthropic, say their models have found a way to do it faster than was considered possible. Here is what they actually said, and why it is still a claim rather than an established fact.
Which hypothesis is at stake and what the labs claimed
The Exponential Time Hypothesis (ETH) was introduced in 1999. It was published by Russell Impagliazzo and Ramamohan Paturi of UC San Diego. The idea: for a certain class of tricky logic puzzles, even the fastest algorithm spends exponentially more time as the number of variables grows. In plain terms, in a Sudoku each new cell does not add work but doubles it. Because of this "wall," the hypothesis was used for years as a foundation, explaining which problems are beyond the reach of computers.
OpenAI published solutions to three well-known mathematical problems, and one of them was unexpected: it challenges ETH. According to OpenAI, the model found an algorithm that solves these puzzles in "subexponential" time, that is, faster than the hypothesis predicted. If this is correct, ETH is false, or in scientific language, refuted.
Then a telling episode followed. Anthropic mathematician Levent Alpöge suggested that OpenAI was building on earlier work. A few hours later Anthropic released its own refutation of ETH. Two competing labs reached a similar conclusion, but this does not replace verification by independent scientists.
P versus NP and cryptography
ETH belongs to the family of "P versus NP" questions. The core issue: if the answer to a problem is easy to check, does that mean it is just as easy to find? A completed Sudoku can be checked in seconds, but devising a solution to a hard puzzle takes a long time. This asymmetry underpins encryption: the key holder reads the message, while breaking it without the key takes an unrealistically long time.
Most scientists believe P is not equal to NP, and ETH was one of the arguments for this. MIT professor Ryan Williams, a specialist in computational complexity, says every theorist should be slightly more open to P = NP, though each has their own degree of doubt. At the same time, he thinks OpenAI's algorithm is unlikely to be the best possible, and that this is probably not the final answer.
Williams first asked OpenAI's chief scientist Dan Roberts whether the result breaks any cryptosystems. According to Williams, OpenAI checked this and is fairly confident that no breaks follow from the result. He also noted that an improved algorithm could in principle mean compromising systems with certain key sizes. That is why security engineers should follow the discussion, without panicking.
How such results are now being published, and what readers should do
Williams had previously called OpenAI's October flood of proofs a "DDoS attack on mathematicians." This time the lab structured the process differently across three fields. Mathematicians received materials on GitHub. Computer scientists formed a working group, asked for the proofs to be opened publicly, and asked OpenAI to fund a conference. Physicists also formed a group that will itself decide how to publish their result.
Williams agreed to help, although he criticized the lab's approach: it matters to him to bring ideas to the community. Together with Impagliazzo and Paturi he published an open letter asking for feedback and for discussion of the norms for AI's contribution to science. In his words, the proof contains routine sections and two or three "alien-looking" fragments, which is why everyone needs to work on it together.
The practical takeaway for developers and founders is this.
- If the refutation survives verification, many papers from the last decade that cite ETH will need to be revisited. This is why Williams insisted on a conference.
- For products today, nothing changes: the material contains no data on the new algorithm's speed on real tasks, on computational costs, or on how the models are built.
- The signal for the industry matters more than the details: frontier models are already working at the edge of theoretical computer science, and the process for verifying such results has to be invented on the fly.
Williams acknowledges concern about training young scientists, but sees an upside too. If everything researchers used to work on becomes "low-hanging fruit" for AI, the bar for questions has to be raised. Until independent confirmation, it is reasonable to treat the result as a bold claim, not a new truth.
- Nov 21, 2026FDE job postings grew 4.6x in a year: what a forward deployed engineer actually does at the client's site
- Nov 21, 2026A swimming team captain handed ChatGPT three scheduled tasks and cut her routine work by a multiple
- Nov 21, 2026OpenAI GPT-6 Cyber Found About 35 Flaws in iPhone, Mac and Other Apple Devices
- Nov 21, 202622 Claude Agents Spent Six Weeks on Black Hole Problems — and Solved Two
Key Questions Answered
Which hypothesis is at stake and what the labs claimed?
The Exponential Time Hypothesis (ETH) was introduced in 1999. It was published by Russell Impagliazzo and Ramamohan Paturi of UC San Diego. The idea: for a certain class of tricky logic puzzles, even the fastest algorithm spends exponentially more time as the number of variables grows. In plain terms, in a Sudoku each new cell does not add work but doubles it. Because of this "wall," the hypothesis was used for years as a foundation, explaining which problems are beyond the reach of computers.
What are the key details on P versus NP and cryptography?
ETH belongs to the family of "P versus NP" questions. The core issue: if the answer to a problem is easy to check, does that mean it is just as easy to find? A completed Sudoku can be checked in seconds, but devising a solution to a hard puzzle takes a long time. This asymmetry underpins encryption: the key holder reads the message, while breaking it without the key takes an unrealistically long time. Most scientists believe P is not equal to NP, and ETH was one of the arguments for this.
How such results are now being published, and what readers should do?
Williams had previously called OpenAI's October flood of proofs a "DDoS attack on mathematicians." This time the lab structured the process differently across three fields. Mathematicians received materials on GitHub. Computer scientists formed a working group, asked for the proofs to be opened publicly, and asked OpenAI to fund a conference. Physicists also formed a group that will itself decide how to publish their result.
Test Frontier LLMs & Autonomous Agents in One Workspace
Run Claude Opus 5.5, GPT-6, Gemini 3.1, and DeepSeek side-by-side in Nomad AI (nomadnet.ai) — unified model routing, deep research, and multimodal workflows under one subscription.
The AI world, distilled — once a week
Seven stories that actually mattered, hand-picked. No noise, no reposts, no press releases.
Done! Check your inbox for a confirmation.