Exponential Time Hypothesis Disproved? What AI Labs Claim

The Exponential Time Hypothesis, a basic assumption in computer science for more than 25 years, may have just fallen, and AI did it. On October 26, 2026, OpenAI said one of its internal models had disproved it. Hours later, Anthropic said its own Claude research model had found a way to do the same, independently.

If the claims hold, they would be among the biggest results in theoretical computer science in decades, and the first produced by AI. But there's a lot of hype to cut through. Neither result is peer reviewed yet, the practical impact is close to zero and the verification story is more subtle than the headlines suggest. Here's what was claimed, what's checked and what it means for engineering teams.

Disclosure: Van Data Team builds AI systems with models from several providers, including OpenAI and Anthropic. This article was researched with Claude, which is made by Anthropic, one of the two labs making these claims. We treat both labs' claims the same way: as unreviewed until outside experts finish checking them.

Key Takeaways

• OpenAI and Anthropic each say an internal AI model disproved the Exponential Time Hypothesis (ETH), announced on the same day, October 26, 2026.
• Both published Lean proofs that a computer has checked. Neither has been peer reviewed yet.
• A group led by Russell Impagliazzo and Ramamohan Paturi, two of ETH's original authors, and Ryan Williams of MIT is organizing an open examination of OpenAI's claim.
• The result is theoretical. Anthropic's paper says its algorithm only beats brute force above roughly 10^10,000 variables.
• It doesn't prove P equals NP, doesn't break encryption and won't speed up today's solvers. The bigger story is AI doing original, machine-checked research.

The Exponential Time Hypothesis Claims at a Glance

Item	OpenAI	Anthropic
Announced	October 26, 2026	October 26, 2026, hours later
When the AI found it	October 16; Lean proof October 17	October 16, using 14 million output tokens
Human role in discovery	Internal model produced the proof	None, per Anthropic; humans helped refine the write-up
Lean proof	Published on GitHub	Published on GitHub; checked by two separate checkers
Outside review	Group led by Impagliazzo, Paturi and Williams	Not yet announced
Peer reviewed	No	No

Sources: Unite.AI's summary of OpenAI's announcement, OfficeChai's report on Anthropic's paper and Anthropic's formal-math repository.

What Is the Exponential Time Hypothesis?

Start with a puzzle called 3-SAT. You get a long list of rules, each saying at least one of three true-or-false switches must be on, or off. The question: is there any way to set all the switches so every rule is met?

Checking every combination works, but it doubles in effort with each new switch. With 100 switches, there are more combinations than atoms in a person. Clever algorithms do better, but every known method still slowed down exponentially as the puzzle grew.

The Exponential Time Hypothesis, introduced by Impagliazzo and Paturi in 1999 and developed with Francis Zane, says that's unavoidable. No algorithm can solve 3-SAT in what's called subexponential time. That was the bet. It became one of the most used assumptions in computer science.

A Simple Way to Think About It

Think of ETH as a speed limit on a long road. For years, everyone agreed you could never drive faster than a certain pace, no matter what car you built. Many other rules were written on top of that limit.

Now two AI labs say the limit was never real. There's a faster route. But the new route only pulls ahead after a distance so long that no one will ever drive it.

So the map changes, and people who study roads have work to do. Your commute stays the same.

Why the Exponential Time Hypothesis Matters

Computer scientists use ETH as a foundation. If ETH is true, they can prove that many other problems are also hard, because a fast algorithm for them would give a fast algorithm for 3-SAT.

You'll find this method in graph theory, databases, biology and geometry. Anthropic says Claude's own search of past work found more than 800 papers that depend on ETH or a stronger version, called SETH.

If ETH is false, those results lose their foundation. They aren't necessarily wrong, but they'd need new justifications. That's a lot of rework for one field.

OpenAI's Exponential Time Hypothesis Claim

OpenAI's ETH claim came as part of a larger announcement about three AI-generated results. For the computer science result, it says its model:

• Produced a natural-language disproof of ETH on October 16, 2026.
• Had it checked in Lean on October 17.
• Showed a method that counts the solutions to these puzzles in subexponential time, using only modest memory.

OpenAI published both the write-up and the Lean proof on GitHub. It asked Impagliazzo, Paturi and Williams to lead a group to examine the result. At their request, OpenAI agreed to release all the raw data and to fund a conference on what the result means for the field.

Anthropic's Exponential Time Hypothesis Claim

Anthropic's paper lists "Claude, Anthropic" as its author, and its title, "A 2^o(n) Time Algorithm for 3-SAT," names the claim. Anthropic researcher Levent Alpoge says an internal Claude model found the core method on October 16. It used 14 million output tokens, and no human helped with the discovery itself.

The paper claims a method for 3-SAT that beats exponential time and always gives the same answer, plus a version that counts solutions. That would refute both ETH and SETH. It also claims faster theoretical algorithms for problems like Independent Set, Clique and Vertex Cover.

Anthropic's paper cites OpenAI's preprint and says an OpenAI model "claims to have proven a similar result." The two labs appear to have reached the same conclusion separately, on the same day.

Why Two Labs on the Same Day?

Two labs finding the same result on the same day sounds unlikely. Both say their models found it on October 16, and both announced it on October 26.

Neither lab has fully explained the timing. One plain reading is that top AI models from different labs now have similar skills, so similar results can appear at once. Anthropic's paper cites OpenAI's preprint, which suggests it published quickly once OpenAI went first.

The details differ, too. The two write-ups use their own methods and their own Lean proofs. If both hold up, that's good news: two separate routes to the same answer make the result more likely to be right.

How the Exponential Time Hypothesis Proofs Were Checked

Both labs used Lean, a proof assistant that checks every logical step of a formal proof. If Lean accepts a proof, the logic is sound. That's a big deal for AI-made math, because no one has to trust the AI.

Anthropic's version is large: about 1,050 Lean files built on Mathlib, a shared math library. It was checked by Lean's own kernel and a second, independent checker called nanoda.

There's an important catch, though. Lean checks that the proof proves the formal statement.

It doesn't check that the formal statement says what the paper claims, so a proof can be perfectly correct about the wrong question if the statement was written badly. A person must confirm that match. Anthropic's README says this plainly, and its paper notes the Lean code was written and reviewed by AI models, with no person known to have checked it at the time of writing.

Why "Verified" Needs Care

Several headlines say the results were "verified by the people who invented ETH." That isn't accurate yet.

Impagliazzo, Paturi and Williams have agreed to lead an open examination of OpenAI's claim. They stress it isn't an endorsement. Their job is to help the community check it properly, not to vouch for it in advance.

So the honest status is this:

• Formal proofs: both pass machine checks.
• Statement match: still needs careful human reading.
• Expert review: started for OpenAI's claim; none announced yet for Anthropic's.
• Peer review: not done for either.

If the statements match and the reviews hold up, the claims will stand, and the field will spend years working out what else changes.

Does Disproving ETH Change Anything in Practice?

Almost nothing, for now. This is the part most headlines skip.

Anthropic's own paper says the result "says nothing about solving formulas in practice." For a typical 3-SAT puzzle, its algorithm only beats brute-force search once the number of variables passes roughly 10^10,000. That's a 1 followed by ten thousand zeros. Real puzzles never get close.

OpenAI says the same in its own way: turning the theory into practical speedups will take significant further research. The result changes what's possible in principle, not what runs faster tomorrow.

What Disproving ETH Does Not Mean

A few common myths are worth clearing up:

• It doesn't prove P equals NP. ETH is a stronger assumption. Disproving it leaves P versus NP open.
• It doesn't break encryption. Mainstream encryption relies on different assumptions, and this algorithm is far too slow to matter.
• It doesn't speed up SAT solvers. Modern solvers already handle huge industrial problems using shortcuts, not worst-case guarantees.
• It doesn't make the 800 papers wrong. Their results need new support, but many may still turn out to be true once researchers rebuild them on other, weaker assumptions that still hold.

The Other Results OpenAI Announced

ETH was one of three results OpenAI announced on the same day. The other two are even bigger claims, and also unreviewed:

Field	Claim	Release approach
Mathematics	Proof of the local smoothing conjecture in all dimensions, which would also settle the Kakeya and Stein restriction conjectures	AI write-up and Lean proof published openly
Computer science	Disproof of the Exponential Time Hypothesis	Published openly; expert group leads examination
Physics	Existence proof for QCD and pure Yang-Mills theory in four dimensions, part of a Millennium Prize problem	Held back; a group led by Nobel laureate David Gross will write it up

OpenAI says it wants no academic credit for these results. It asks for no secrecy deals, and it will pay for researchers to study them. Some mathematicians criticized its October 6 math release for making many claims with little checking. This release looks more careful.

Computers Have Checked Big Proofs Before

Machine-checked math isn't new. What's new is who does the work, and how fast.

Year	Milestone
1976	The four color theorem is proved with heavy computer help
2014	A formal, computer-checked proof of the Kepler conjecture, about stacking spheres, is finished after years of work
2026	Anthropic says Claude produced a computer-checked proof of Fermat's Last Theorem in 11 days
October 2026	OpenAI and Anthropic each claim an ETH disproof, with Lean proofs written by AI

The earlier projects took people years. Here, AI models wrote both the proofs and the formal checks in days.

That shift is why the checking step now matters so much, both for researchers reading these proofs and for anyone who relies on AI-written work. Writing proofs is getting cheap. Understanding and trusting them is not.

Why AI-Made Research Is the Bigger Story

Set the specific result aside. The bigger news is that two AI labs say their models produced original, top-level research, largely on their own, and backed it with machine-checked proofs.

That changes the bottleneck. When AI can produce proofs faster than people can read them, the hard part becomes checking, understanding and deciding what matters. OpenAI's "shepherd" groups and Anthropic's detailed caveats are early attempts to handle that.

Credit, access and trust are now open questions. For business, it shows AI can now take on problems once left to top experts, if someone can check the output. Our guide to ChatGPT for academic researchers covers how researchers already use these tools.

What This Means for Engineering Teams

Most engineering teams won't feel this result directly. But it carries useful lessons:

• Verification beats trust. The labs didn't ask anyone to trust the AI. They gave machine-checkable proofs. Teams using AI for code and analysis should aim for the same: tests, checks and reproducible outputs.
• Check the spec, not just the proof. Lean can prove the wrong statement perfectly. Likewise, AI-written code can pass tests that don't match the real requirement.
• Hard problems are now in reach. AI may help with problems your team once shelved as too hard, from optimization to tricky algorithms.
• Expect more AI-found results. New algorithms and research claims will arrive faster. Someone on the team should know how to judge them.

Our post on AI agent internet access covers why limits and checks matter as AI does more on its own.

Will This Change Optimization and Scheduling Tools?

Not soon. Many business tools use SAT and similar solvers. Here's what this result means for them:

• Schedulers and route planners: no change. They succeed because real-world problems have structure that solvers can exploit, not because of worst-case math, and nothing in this result changes that structure or the tricks built on it.
• Chip design and testing tools: no change. A worst-case method with enormous constants won't beat today's tuned solvers.
• Research and future solvers: maybe, over years. The ideas inside the proofs, like the tensor-network method in Anthropic's paper, might one day inspire practical tricks for real solvers. That's the usual path. It's slow.

If your team relies on SAT or optimization solvers, there's nothing to change today. Keep an eye on solver release notes over the coming years.

How to Judge Big AI Research Claims

This won't be the last headline like this. A quick checklist helps:

• Is there a formal proof, and has anyone checked that its statements match the claim?
• Who is reviewing it, and have they reached a conclusion or just started?
• Is it peer reviewed, or still a preprint?
• What's the practical impact, and does the source say so honestly?
• Did the lab share the raw data, including transcripts, code and formal files, so that anyone in the field can check the work for themselves?

Both labs did well here. The open questions are the human checks that take time.

Exponential Time Hypothesis: What to Watch Next

• The expert group's findings on OpenAI's ETH claim, and any review of Anthropic's.
• Human checks of the Lean statements against the papers.
• Peer review. A journal or major conference.
• The physics write-up from David Gross's group, which would be an even bigger result.
• New practical algorithms that build on the ideas, which would take years.

Exponential Time Hypothesis: Our Take

Two AI labs independently claiming to disprove the Exponential Time Hypothesis on the same day is remarkable, whatever happens next. Both backed their claims with machine-checked proofs and clear caveats, which is the right way to release results like this.

But the headlines run ahead of the facts. The results aren't peer reviewed, the expert examination has just started and the practical impact is essentially nil. For engineering teams, the takeaway isn't about 3-SAT. It's that AI can now produce serious technical work, and the teams that benefit most will be the ones that know how to check it.

How Van Data Team Helps Teams Use AI for Hard Problems

We help companies apply AI to hard technical work with the checks to trust it. That includes test suites for AI-written code, validation pipelines for AI analysis and model reviews for complex tasks.

If you're exploring AI for difficult problems, start with our guide to AI governance, then get in touch for a quick review.