이 아티클은 아직 번역되지 않아 영어로 표시됩니다.
Exponential Time Hypothesis Explained: Did OpenAI and Claude Break a 1999 Math Bet?
OpenAI and Anthropic's Claude both claim the Exponential Time Hypothesis is false. What 3-SAT is, how the algorithm counts, and why it is unverified.
For 27 years, a large part of computer science has rested on one assumption written down in 1999. In October 2026, two AI models claimed they broke it, within hours of each other.
Neither paper has been peer reviewed. This article explains the claim and what it would and would not change. Here ETH means the Exponential Time Hypothesis, not Ethereum.
▶ WATCH ON YOUTUBEWatch the video
▶ WATCH ON YOUTUBEFull video
What 3-SAT is
You get a row of on-off switches and a list of rules. Each rule names three switches and says at least one of them must be set a certain way. Find one setting that keeps every rule happy.
- Checking an answer is easy.
- Finding one is the hard part.
The simple way is to try everything, and every new switch doubles the work. With n switches that is 2^n. Decades of clever tricks brought it down to about 1.3^n. Better, but the curve still explodes.
The 1999 bet
Russell Impagliazzo and Ramamohan Paturi put a bet in writing: no trick will ever solve 3-SAT faster than exponential time. That is the Exponential Time Hypothesis.
It is a bigger claim than P vs NP, and people used it anyway because it is so useful. Assume it is true and you can prove speed limits for many other problems, such as clique, vertex cover and graph colouring. Anthropic's literature search found more than 800 papers with a result proved only under this assumption or one that implies it.
The claim
| OpenAI | Anthropic | |
|---|---|---|
| Paper | 67 pages, "The Exponential Time Hypothesis is False" | 49 pages, credited to Claude |
| Method | An extra parameter and Hermite interpolation | Tensor networks |
| Date the model found the idea | October 16, 2026 | October 16, 2026 |
Anthropic says its model used 14 million output tokens and no human input to find the core algorithm.
Both papers count 3-SAT solutions in about 2^(n / √log n) time. That curve still climbs, but it eventually falls under every true exponential. If it holds, the hypothesis is false, and so is the stronger version (SETH).
Not everything falls. Anthropic points out that the Orthogonal Vectors hypothesis still stands, and many results rest on that one.
How the algorithm works
Normal solvers search: they flip switches until something works. These algorithms do not search at all. They count how many settings work.
- The count can be written as one giant sum.
- Rules share switches, so the sum refuses to split into pieces.
- OpenAI's version bends the formula with an extra parameter until the pieces come apart.
- It counts each piece alone and multiplies the results, for several values of that parameter.
- Hermite interpolation, a classic trick, recovers the count for the original formula.
- If the count is not zero, a solution exists.
What it does not change
Nothing on your laptop gets faster.
- With five rules per switch, Anthropic's bound only beats brute force once
npasses 10^10,000. Brute force is already hopeless at 100 switches. - P vs NP is still open. A speed-up like this does not carry over to every NP problem.
- It is no reason to sell your Bitcoin. None of this makes anything faster today.
Scott Aaronson, a well-known complexity theorist, moved his personal odds of P = NP from 3% to 5%.
Nobody has certified it
- Both labs checked their proofs in Lean, a proof assistant. But Anthropic's own notes warn that no machine checks that the Lean file says what the paper says.
- OpenAI's Lean version proves a slightly weaker bound, still enough to break the hypothesis.
- OpenAI asked three experts to examine it: Impagliazzo, Paturi and Ryan Williams. Their open letter says their involvement should not be taken as certification.
- The letter also asks who gets credit for checking, fixing and explaining what an AI finds.
- Shiva Kintali has posted a simplified version of OpenAI's proof.
So the two people who made the bet in 1999 are now helping check whether a machine beat it.
Status
| Claim | Status |
|---|---|
| Two labs published proofs that ETH is false | True |
| The proofs are formalised in Lean | Claimed by both labs |
| The proofs are peer reviewed | No |
| Experts have certified the result | No |
| Practical speed-up | None |
| P vs NP solved | No |
Why developers should care anyway
Whether it stands or not, the hard part has moved. Producing a 67-page proof is no longer the bottleneck. Checking it is. That is the same shift coding agents brought to software, where review is now the slow step. See the Claude Code backlash.
Sources
- Full video: https://youtu.be/qq_qX_WwpCQ
- OpenAI, math repository: https://github.com/openai/math/blob/main/history.md
- Anthropic, formal-math repository: https://github.com/anthropics/formal-math/tree/main/eth
- Shiva Kintali, simplified proof (PDF since taken offline by its author)
- Scott Aaronson: https://scottaaronson.blog/?p=10239
- Wikipedia: https://en.wikipedia.org/wiki/Exponential_time_hypothesis
Would you trust a proof that no human found?


