On 26 October 2026 OpenAI said an internal model had refuted the Exponential Time Hypothesis, a 1999 assumption about how fast the hardest little logic puzzles can get. On 27 October Anthropic posted its own refutation, found, it says, on the same day, 16 October, by a different model. Headlines then jumped to P versus NP, to broken passwords, and on X to the Ethereum coin.
Short answer: if the proofs hold, a famous speed limit was the wrong shape. The new speed is still nowhere near fast. Anthropic’s paper says the bound does not beat dumb trial of every possibility until a puzzle has more than 10^108 switches, or 10^10000 switches in the version that also counts clauses. Nothing you run this year gets faster. P versus NP (the question of whether every puzzle that is quick to check is also quick to solve) is not answered. Ethereum (the cryptocurrency, ticker ETH) is a different word.
This is a claim about the shape of a curve, not a claim that your laptop just learned magic. A hypothesis (a precise bet the field has been using, not yet a theorem) can sit under hundreds of papers and still be false. OpenAI says this one has been used in hundreds of papers, in graph theory (the math of dots and the lines between them), computational biology, databases, and geometry. If the bet is wrong, those papers do not all become garbage. Their proofs of “if the bet is true, then this other problem is also hard” remain proofs. The “if” just stops being a thing the field wants to assume.
What are the words, before the news?
A variable is a switch. A clause is a small rule. A formula is a pile of rules that all have to be true at once. 3-SAT is the puzzle of whether such a pile has any setting that works.
Start with a bit (a single yes or no, also called a Boolean value, after George Boole, the 19th-century mathematician who made true and false into algebra). Call three bits A, B, and C. Each one will be true or false. Nothing else. There is no “maybe” in this puzzle.
A literal (one switch, or the flipped version of that switch) is the smallest piece you can write. “A” means the switch is on. “NOT A” means the switch is off. A clause (a little rule written as an OR, meaning “at least one of these is true”) with three literals is the “3” in the name. Here are three clauses:
- A OR B OR C
- NOT A OR B OR C
- A OR NOT B OR NOT C
A formula (the whole puzzle: every clause must hold) is those three lines together. 3-SAT (satisfiability of formulas whose clauses each have three literals) asks one question: is there any setting of the switches that makes every line true? SAT (satisfiability, the same question without the limit of three) is the bigger family. The “3” is there because three is the smallest clause size where the puzzle stays hard in the sense that matters. Two is a different, easier puzzle.
Try A true, B true, C false. Line one is saved by A. Line two is saved by B. Line three is saved by A. So this formula is a yes. There are other yeses too. #3-SAT (the counting version: not “is there a yes?” but “how many yeses?”) is the harder question both labs say they can answer. Counting is harder because a single lucky guess is not enough. You have to know the size of the whole pile of yeses.
How many settings exist at all? Two choices for A, times two for B, times two for C. That is 2^3, which is 8. You can list them on a napkin. That listing is brute force (trying every setting, one by one, and checking each one). Checking one setting is cheap. There are only three lines to read. The cost is the listing, and the listing doubles every time you add one switch.
Add a fourth switch and the napkin has 16 rows. A fifth makes 32. The puzzle did not become a different kind of puzzle. It became a longer list. That length is the whole argument.
What does exponential mean, in numbers a person can see?
Exponential (growing by a constant multiple each time you add one item) is what happens when the list doubles, or nearly doubles, per extra switch. The old speed records were still that shape. The new claim is a different shape.
Here is brute force, and nothing but brute force. The number of settings is 2^n (2 multiplied by itself n times), where n (the count of switches) is the only thing that grows.
| Switches, n | Settings to try, 2^n | In words |
|---|---|---|
| 10 | 1,024 | A short loop |
| 20 | about 1 million | A blink, for a computer |
| 30 | about 1 billion | A few seconds of checking, if each check is tiny |
| 40 | about 1 trillion | A serious job |
| 100 | about 10^30 | Anthropic’s paper: already impractical |
People have not been stuck on the raw 2^n list since the 1980s. Anthropic’s paper records the previous best as about 1.328^n for a deterministic algorithm (one that does not flip coins; the same input always takes the same path), citing Liu in 2018, and about 1.308^n for randomized algorithms (ones that are allowed to flip coins), citing a line of papers from 2005 through 2021. Those numbers are smaller bases than 2. They are still a constant raised to n. Shrink the base and you win a constant factor in the exponent. You do not change the family of the curve.
That family is what the hypothesis defends. The Exponential Time Hypothesis, shortened to ETH (the 1999 bet of Russell Impagliazzo and Ramamohan Paturi, with Francis Zane, that 3-SAT has no 2^{o(n)} algorithm), says there is some fixed percentage of n you cannot shave off. In symbols the forbidden zone is 2^{o(n)}. The little-o (a growth that becomes a smaller and smaller fraction of n as n gets huge) is the part to learn. n divided by 100 is not little-o of n, because the fraction stays 1 percent forever. n divided by the square root of log n (the number of times you can cut n in half, roughly) is little-o of n, because that fraction shrinks toward zero, only very slowly.
So 1.328^n does not refute ETH. It is still exponential time (time bounded by some constant, bigger than 1, raised to n). A runtime of 2 raised to n over the square root of log n does refute it, if the proof is right, because that exponent is o(n). Subexponential (in this field, the name for 2^{o(n)}, not the everyday word “a bit faster”) is that second shape.
Read the ladder from the bottom if the names feel slippery. Brute force tries every row. The old papers skip a lot of rows and still take exponential time. ETH was the bet that you cannot skip enough rows to leave that exponential family. The new papers say they left it. They did not land in the top rung.
What did each lab actually release?
Two write-ups, two methods, one calendar day for the discovery, and a public warning from the hypothesis’s own authors that their names are not a stamp.
OpenAI’s post of 26 October, “Working with academic communities to build scientific understanding,” says an internal system produced a natural-language disproof on 16 October and that the lab formalized it in Lean (the same checker behind OpenAI’s earlier math preprints; a proof assistant: a programming language in which every step must be a rule the computer can check) on 17 October. The English PDF and the Lean file are public on GitHub. OpenAI’s sentence is “our system has recently proved that the ETH is false.” Hold that verb next to the next paragraph.
The same day, Impagliazzo, Paturi, and Ryan Williams of MIT wrote to their colleagues. The letter calls it “a claimed refutation.” The sentence to keep: “Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny.” They also write that if the claim is correct, it will change an important part of theoretical computer science (the study of what computers can and cannot do, measured as a function of the size of the input). OpenAI says it will fund a conference. The letter asks the community whether it wants a virtual meeting before the end of 2026. Those are related plans, not yet one event with a date.
Anthropic posted on 27 October, in a GitHub folder and on the Hexagon preprint site. The paper is titled “A 2^{o(n)} Time Algorithm for 3-SAT” and the author line is “Claude, Anthropic.” The provenance note, in the paper, says the core algorithm was found on 16 October by an internal Claude research model, using 14 million output tokens (the small chunks of text a model writes; 14 million of them is a long book, not a tweet), “with no human input.” The next sentence matters just as much: Anthropic researchers then worked with Claude to improve the presentation. The discovery pass and the writing pass are not the same pass. The paper also says an internal OpenAI model “claims to have proven a similar result,” independently and concurrently.
The methods are not copies of one paragraph. Anthropic’s repository describes the idea as a contraction of tensor networks (a way of storing a giant grid of numbers as smaller pieces, then multiplying those pieces in an order that avoids building the giant grid). Write-ups that have read OpenAI’s PDF describe a different route, through shared linear summaries and counting common zeros of sparse polynomial systems (equations with many variables but few terms). I did not re-derive either argument. Two routes are a reason to look harder, not a reason to stop looking.
TechCrunch, on 27 October, reported that Anthropic mathematician Levent Alpöge had suggested OpenAI’s solutions drew on earlier work, and that Anthropic then released its own note. I am not treating that suggestion as a finding. It is a reason the side-by-side reading exists.
| When | What is on the page |
|---|---|
| 1999 | Impagliazzo, Paturi, and Zane propose ETH |
| 16 October 2026 | Both labs say an internal model found a disproof this day |
| 17 October 2026 | OpenAI says it formalized its result in Lean |
| 26 October 2026 | OpenAI’s public post. The PDF and Lean notes go up. The three-person letter goes out |
| 27 October 2026 | Anthropic’s paper and Lean 4 files go up, author line “Claude, Anthropic” |
What does a machine-checked proof not check?
Lean checks that a formal sentence follows from the rules. It does not check that the formal sentence is the sentence in the headline.
A proof (a chain of small steps, each one an allowed move, from things already known to the thing you wanted) can be wrong in two different places. A step can be illegal. Or every step can be legal and the destination can be a nearby, smaller claim than the one in the title. The first mistake is what a proof assistant is built to catch. The second mistake is a human job.
Stefan Szeider, at TU Wien, told New Scientist he expects OpenAI’s result to withstand scrutiny, and that researchers still have to check that the formally proven statement means what its authors say it means. Anthropic’s own repository points at the same gap from the other side: the file that states the theorems does not, by itself, prove that those theorems are the English claims. A reader lines them up. That lining-up is the work Impagliazzo, Paturi, and Williams asked the field to do in public.
There is a smaller, already visible gap on OpenAI’s side, reported by readers of both the PDF and the Lean file. The Lean write-up is said to carry a slightly weaker time bound than the paper’s headline, with an extra log log n factor, and that weaker bound would still be subexponential and would still refute ETH. Weaker-but-still-enough is not a scandal. It is a reminder to quote the checked sentence, not the boldest sentence.
Leslie Goldberg, at Oxford, told New Scientist that if the result is confirmed it is an enormous breakthrough, and then said the sentence the headlines keep skipping: it does not have a direct impact on P versus NP, so it should not be viewed as progress toward P versus NP.
What is P versus NP, and why this is not that?
P is “quick to solve.” NP is “quick to check.” ETH was a stronger bet than “they differ.” Knocking down the stronger bet does not collapse the two.
P (the class of problems a computer can solve in polynomial time, meaning time like n, or n squared, or n to some fixed power) is the “quick” class. NP (the class of problems where a proposed answer can be checked that quickly, even if finding the answer looks hard) is the “I’ll know it when I see it” class. Every problem in P is in NP, because if you can find the answer quickly you can certainly check it quickly. The famous question is whether anything sits in NP and outside P.
Sudoku is the picture people use, and it is a fair picture. A filled grid is quick to check: each row, column, and box contains the digits once. Inventing the digits is the slow part, once the grid is large. P = NP (the claim that every checkable puzzle is also quickly solvable) would say the inventing is quick too, for every puzzle of this kind, not just Sudoku. Williams told TechCrunch that this “just seems too good to be true.” Most of the field bets P is not equal to NP. Nobody has proved that bet either.
ETH sits above that bet. If ETH were true, P would not equal NP, because a polynomial algorithm is also a 2^{o(n)} algorithm. The arrow does not reverse. A false ETH is compatible with a true “P is not NP.” It is also compatible, logically, with a future polynomial algorithm that nobody has. Goldberg’s point and Williams’s point can live together. Goldberg: this result is not progress on the question. Williams, in the same news cycle, to TechCrunch: every computer scientist should put a little more weight on the plausibility of P = NP, the weight will differ by person, and he does not think OpenAI’s algorithm is the best one that will ever exist. One of them is talking about what has been proved. The other is talking about how the intuition feels after a wall moves. Do not let a headline fuse those into “AI solved P versus NP.”
The new runtime, even in the optimistic reading, is not polynomial. 2 raised to n over a slow-growing log still outruns n^3, and n^10, and n raised to any fixed power, once n is large. Superpolynomial (growing faster than every polynomial) is the honest name for it. Subexponential and superpolynomial are not opposites. This claimed algorithm is both.
Why the faster method does not make anything faster
The paper says so, in numbers so large they are the story.
Anthropic’s abstract gives a deterministic 2^{o(n)} algorithm for 3-SAT, and says the same method counts solutions of #3-SAT in time 2 raised to a constant times n times log log n, divided by the square root of log n. The README calls the result purely asymptotic (a statement about the shape as n goes to infinity, silent about any n a person will ever type).
Then the paper gets specific, which is rarer and more useful than the symbol. For 3-CNF formulas (3-SAT formulas written in the usual AND-of-ORs shape) with m = 5n clauses, the bound it proves does not beat exhaustive search unless n is greater than 10^10000. The bound in n alone, which holds no matter how the clauses are counted, does not beat exhaustive search unless n is greater than 10^108. The authors add that the general approach seems unlikely to yield any general improvement unless n is greater than 10^7, however it is built. And brute force is already impractical at n = 100. The sentence they chose to land on: “Thus our result says nothing about solving formulas in practice.”
Read 10^7, 10^108, and 10^10000 as three different sentences. 10^7 is 10 million, and it is the authors’ rough guess about the approach, not the bound they proved. 10^108 and 10^10000 are the proved crossovers, and they are not “very big instances.” A puzzle with 10^108 switches does not fit in the universe in any sense that matters. Headlines that say “it only helps past 10 million variables” have picked up the guess and dropped the theorem.
SAT solvers (programs that attack these formulas with a bag of practical tricks, and that already check things like chip designs) are not running the 2^n list, and they are not about to run this algorithm either. They are fast on many real formulas because real formulas are full of structure, which is a different fact from worst-case time (the time on the most stubborn formula of a given size). A worst-case breakthrough that starts paying rent at 10^108 switches does not move a solver that is already aimed at the easy shape of industrial formulas.
Cryptography (the art of making a secret easy to open with a key and absurd to open without one) was the first practical fear, and it was a reasonable fear to ask about. Williams told TechCrunch he asked OpenAI science lead Dan Roberts whether the algorithm broke cryptographic systems. The reported answer: they had checked, and they were reasonably confident it did not. That is a lab’s confidence, relayed by an interview, not a published proof that every scheme is untouched. It matches the only quantitative statement the Anthropic paper is willing to make, which is that the speedup is not a speedup at any size anyone computes.
What are the other two OpenAI claims, and why they are not this claim?
Same announcement, different fields, different amounts of paper on the table.
OpenAI bundled the computer-science claim with two others on 26 October. They share a press cycle. They do not share a meaning.
The mathematics claim is about waves. In 1991 Christopher Sogge stated the local smoothing conjecture (a statement that a wave cannot stay tightly focused for long; a typical moment is much less focused than the worst moment). It implies the Kakeya conjecture (a statement about how thin a shape can be while still containing a unit line segment in every direction) and Stein’s restriction conjecture. OpenAI says its models proved local smoothing in every dimension, hence those two as well. The natural-language output is dated 18 October, the Lean formalization 19 October, and both are public. Earlier human work had done the two-dimensional case in 2019 and the three-dimensional Kakeya case in 2025. “Every dimension” is the new part, if it holds.
The physics claim is an existence proof (a proof that a mathematical object is well-defined, not a new measurement in a lab) for certain quantum field theories (the equations physicists use for fundamental particles) in four dimensions, including quantum chromodynamics (the theory of the strong force, the one that holds atomic nuclei together) and a piece of pure Yang-Mills theory (the version with force-carrying fields and no matter particles). Pure Yang-Mills is part of a Clay Mathematics Institute Millennium Prize problem (one of seven problems with a standing million-dollar award). OpenAI is explicit that this is part of that problem. It is not the mass gap (the other, harder half: a proof that the force-carrying particles cannot be massless). The natural-language Yang-Mills argument is dated 9 September, the QCD argument 18 September, and the Lean formalization of Yang-Mills existence 16 October. The shepherd group, led by David Gross, has held the artifacts back while it writes them up. You cannot audit what is not on the table.
A careful reader separates three shelves. Shelf one, ETH: public English, public Lean, a named working group that has refused to be treated as a rubber stamp, and a second lab’s public paper with its own enormous size caveat. Shelf two, local smoothing: public, and a different kind of expertise needed to read it. Shelf three, Yang-Mills: not public yet, and not the full prize problem even on OpenAI’s telling.
What should you do with this on a Tuesday?
Nothing in your stack changes. Something in the map of the field might. The honest next step is other people’s checking, which has not finished.
If you write code, ship a product, or pick a cipher, this week is not an action week. Do not rotate keys because a blog used the word exponential. Do not cancel a SAT-solver dependency. Do not brief a room that P equals NP. If someone in the room says “ETH is dead, so the coin crashed,” they have mixed up a 1999 conjecture with a ticker.
If you read theory, the useful posture is the one in the letter. Look at the argument. Separate the checked formal sentence from the English headline. Separate “ETH is false” from “the Strong ETH is false” and from every neighboring acronym until the formal file is lined up with each one. OpenAI’s blog, the page a non-specialist can read, states the ETH claim. Stronger variants are a question for the PDF and the working group, not for a recap. Separate the asymptotic shape from the crossover sizes Anthropic printed. And keep the old reductions (proofs that solving problem A quickly would let you solve problem B quickly). They are still maps. Some of their captions may change.
Williams told TechCrunch that parts of OpenAI’s proof look routine and that two or three parts look alien, and that those alien parts are why the field has to work on them together. He had previously called an earlier OpenAI proof drop a denial-of-service attack on mathematicians (a flood large enough to knock the readers over). He is inside the tent this time because the claim, if real, moves the floor. That combination, irritation plus custody, is a better guide than either thrill or dismissal.
I would send this to a reader who saw the headline and felt either panic or triumph. Both feelings are aimed at the wrong object. The object is a curve, a formal sentence, and a pile of papers whose “if” may have to come off. That is a large event for one field. It is a small event for a Tuesday.
Common questions about the Exponential Time Hypothesis
Is the Exponential Time Hypothesis false?
OpenAI and Anthropic each say an internal model refuted it, and both posted proofs. The hypothesis’s authors call it a claimed refutation and say their involvement is not certification.
Does this mean P equals NP?
No. A false ETH is compatible with P not equal to NP. The new runtime is still superpolynomial, so it is not progress toward P versus NP.
Will SAT solvers or my code get faster?
No. Anthropic’s paper says its bound does not beat exhaustive search until a puzzle has more than 10^108 switches, or 10^10000 in the version that also counts clauses.
Does the result break cryptography?
Ryan Williams told TechCrunch that OpenAI said it had checked and was reasonably confident it did not. That is a lab’s confidence relayed in an interview, not a published proof.
