What Is the Exponential Time Hypothesis? AI Claims It's False

What is the exponential time hypothesis? It is a bet, made about 25 years ago, that one famous logic puzzle cannot be solved much faster than by checking almost every possible answer. On October 26, 2026, OpenAI announced that an internal AI model had disproved it, and Anthropic published a rival paper credited to Claude that claims the same result and also reportedly refutes the strong exponential time hypothesis. Neither claim had been independently verified as of a November 2, 2026 report, and the details below are based on reporting by TNW and LetsDataScience; the primary papers have not yet been independently reviewed.

That caveat matters more than usual here. If the proofs hold, a foundation stone under hundreds of studies in computer science and biology moves. If they do not, this becomes a story about how AI labs announce results. Either way, it helps to know what the hypothesis actually says.

What is the exponential time hypothesis?

The exponential time hypothesis (ETH) is the claim that a problem called 3-SAT has no algorithm that is meaningfully faster than exponential time (running time that doubles, roughly, each time the puzzle gets one variable bigger). Russell Impagliazzo and Ramamohan Paturi of UC San Diego proposed it with Francis Zane, according to TNW's report on OpenAI's announcement.

It is a hypothesis, not a theorem, and nobody proved it. Researchers widely believed it was true and used it as a starting assumption, the way an engineer assumes steel has a certain strength. TNW reports that ETH has been used to show that problems in graph theory, computational biology and databases are hard to solve quickly.

The pattern runs: "if ETH is true, then this database or biology problem cannot be solved fast either." Those results were always conditional. Their strength came from how few people doubted the condition.

Emergent Mind's explainer on the exponential time hypothesis collects the research built on it, which gives a sense of how much depends on that one assumption.

Strong and gap versions

The strong exponential time hypothesis (SETH) is a tougher version of the same bet: it says that as the clauses in a SAT puzzle get longer, the best possible algorithm gets ever closer to plain brute force. SETH implies ETH, so if ETH is false, SETH has to be false too. That is consistent with coverage saying both papers reportedly refute SETH as well.

The gap exponential time hypothesis is another stronger variant, about telling apart puzzles that can be fully solved from puzzles where many conditions must fail. It also implies ETH, so by the same logic it would fall if the claim holds. The coverage does not discuss it, so that follows from the definitions rather than from a reported finding.

What is the SAT problem and the 3-SAT problem?

The SAT problem (short for Boolean satisfiability problem) asks a yes-or-no question: given a list of true-or-false switches and a set of rules connecting them, is there any way to set the switches so every rule is satisfied? A rule might say "switch A is on, or switch B is off." The puzzle is to find one setting that keeps every rule happy, or to show that none exists.

The obvious method is to try every combination. With 3 switches there are 8 settings to check. Each added switch doubles the count, which is why brute force becomes hopeless for large puzzles.

The 3-SAT problem is the version where every rule mentions at most three switches. That sounds like a small restriction, but 3-SAT is still hard enough to stand in for a huge family of problems, which is why ETH is stated in terms of it. If you can solve 3-SAT quickly, you can solve many other problems quickly by translating them into it.

That translation is the reason a claim about one logic puzzle reaches graph theory, biology and databases. The satisfiability problem is a kind of common currency in computer science.

What OpenAI and Anthropic say they found

According to TNW, OpenAI says an internal model found its disproof of the exponential time hypothesis on October 16, 2026, and checked it in Lean (a programming language for writing proofs that a computer can verify step by step) on October 17. OpenAI announced the result in a blog post on October 26 and published the write-up and the Lean proof on GitHub. This account of the blog post and the GitHub repository is based on TNW's reporting; the primary sources have not yet been independently reviewed.

LetsDataScience's report on both claims says OpenAI's paper runs 67 pages under the title "The Exponential Time Hypothesis is False." Anthropic's paper is 49 pages, titled "A 2^o(n) Time Algorithm for 3-SAT," and credited to Claude.

That title is the whole claim in compact form. The notation 2^o(n) means a running time whose exponent grows more slowly than the number of switches, n. ETH says 3-SAT cannot be solved in that kind of time. An algorithm that does it would break the hypothesis.

According to the same report, Anthropic reaches a bound of 2^O(n log log n / sqrt(log n)) using tensor network contraction (a technique for breaking a large calculation into a network of smaller linked pieces and combining them efficiently). In plain terms, the exponent is n multiplied by a factor that shrinks slowly as n grows. That shrinking factor is what makes the bound sub-exponential, even though it is still enormous.

OpenAI also gave $5m to the Simons Foundation for workshops and conferences on AI-produced results, and agreed to release the raw data behind its ETH work, TNW reports.

Has the exponential time hypothesis really been disproved?

Not yet, as far as anyone can say in public. The exponential time hypothesis has been claimed disproved by two AI labs, but LetsDataScience reported on November 2, 2026 that neither claim had been independently verified.

A review is under way. TNW reports that Impagliazzo and Paturi, two of the three people who proposed ETH, will lead an independent examination with Ryan Williams of MIT. They signed no NDAs (non-disclosure agreements), will not be paid, and say their involvement is not an endorsement. Having the hypothesis's own authors check the work is about as direct a test as the field could set up.

Early reactions differ in tone. Williams said he felt vindicated, according to LetsDataScience. Impagliazzo said he would much rather the result had come from a human who could explain their thought process.

A Lean check is strong evidence that each step of a proof follows from the ones before it. It does not replace the field's own reading of whether the statement proved is the one everyone means by ETH, and whether the argument holds up. That is the job the reviewers have taken on.

Does this solve P vs NP?

No. Coverage of both papers says the result does not settle P vs NP, the famous open question of whether every problem whose answer is easy to check is also easy to solve.

The reason is in the numbers. P vs NP asks about polynomial time (running time that grows like n squared or n cubed, not like 2 to the power of n). The new bound is sub-exponential, but LetsDataScience reports it is still far slower than polynomial. Beating exponential by a slowly shrinking factor is a long way from the kind of speed that would make SAT easy.

Your laptop's SAT solvers and the software built on them do not suddenly get faster either. LetsDataScience reports that Anthropic says its result says nothing about solving formulas in practice. The change, if it holds, is to theory: which problems researchers can prove are hard, and on what assumption.

For a sense of how AI labs have been pushing on mathematics more broadly, our post on GPT-6 Astra's math results covers a different OpenAI claim and the benchmark numbers behind it.

SyntaxRadar calculation: the timeline and the two papers

We worked out a few numbers from the dates and page counts in the coverage. The inputs are shown so you can check them.

The gaps tell a simple story. The machine check came a day after the reported discovery, and the public announcement 10 days after it. Human review, by contrast, had not reached a verdict a week after the announcement. Page count says nothing about correctness, but it does tell you the reviewers have more than a hundred pages of dense mathematics across the two papers to get through.

The money is a different kind of signal. The coverage does not tie the $5m Simons Foundation gift to the review itself; TNW describes it as funding for workshops and conferences on AI-produced results.

What to watch next

So what is the exponential time hypothesis today? Still a working assumption, and one that now waits on people, not models. Three things will decide how this story ends.

• The review verdict from Impagliazzo, Paturi and Williams. As of the November 2, 2026 report, no verdict had been published.
• Whether the two papers turn out to use the same idea or different ones, which will only be clear once experts compare them in detail.
• Which conditional results in graph theory, biology and databases researchers begin to restate on new assumptions.

If you follow how the AI boom is being paid for, our explainer on what AI capex is covers the spending side of the labs making claims like this one, and our report on the data center moratorium covers the political fight over where that computing gets built.