Two rival AI labs claim their models have found algorithms that refute the Exponential Time Hypothesis (ETH). For decades the hypothesis has been the foundation for proofs of how hard many computational problems are. If the results are confirmed in full, algorithm theory will have to revise a significant part of its standard complexity estimates.
OpenAI and Anthropic published preprints and formalisations in Lean back in late October 2026. The new reason for discussion was a statement from the University of California, San Diego on 19 November: leading specialists, including the authors of the hypothesis itself, are organising an independent review of the claims. At the time of writing this is a subject of active scientific study, not a completed and generally accepted peer review.
What ETH is and why it matters
Picture a problem with several logical clauses: each clause requires that at least one of three statements is true. You have to find variable values that satisfy every clause at once. This is the 3-SAT problem, one of the classic examples of an NP-complete problem.
The straightforward way to solve it is to try every combination of values. For n Boolean variables there are 2^n such combinations. As the number of variables grows, even small changes in n sharply increase the amount of enumeration.
The ETH states that for 3-SAT in the worst case no subexponential algorithm is possible: running time inevitably depends exponentially on n, roughly 2^(Ω(n)). The hypothesis was formulated by Russell Impagliazzo, Mohan Paturi and Francis Zane at the turn of the 1990s and 2000s.
ETH is widely used in computational complexity theory. Researchers build chains of inference: if ETH holds, then certain graph problems, optimal-solution search or data processing cannot have algorithms faster than a given bound. Such proofs are called conditional lower bounds.

Our diagram: the exponential lower bound from ETH, the claimed subexponential algorithm and the stages of scientific review. It is a conceptual comparison, not a benchmark chart of a real program.
What OpenAI presented
According to the published statement, an OpenAI research system produced a proof in natural language on 16 October 2026, and the next day the company formalised the result in Lean. The paper text and the formalisation code were published later.
The authors claim an algorithm for k-SAT problems that runs in subexponential time for a fixed k. Formally this means time of the form 2^(o(n)) with extra polynomial factors. Such a result would contradict ETH, which forbids an algorithm of such low asymptotic complexity for 3-SAT.
Two important caveats apply. First, the mathematical estimate concerns asymptotic growth of running time on very large inputs, not a guaranteed speed-up of a specific SAT solver today. Second, checking a formal proof confirms the mathematical theorem as written; whether the formalisation matches the full claimed interpretation also has to be studied.
What Anthropic presented
Soon afterwards Anthropic published its own paper, "A 2^o(n) Time Algorithm for 3-SAT", attributed to an internal Claude research model. The research description says the model worked autonomously and generated about 14 million output tokens while searching for a solution.
Anthropic also provided a Lean project with the main theorem and checking tools. In the repository the result is stated as the existence of a deterministic subexponential algorithm for 3-SAT. Materials from both labs are available for re-running and independent analysis.
They address the same fundamental problem but differ in their technical constructions and the shape of the proof. Publication by both sides does not by itself replace expert analysis of the proofs.
What has been checked and what remains open
Part of the community has started reproducing the formal checks. The ETH: Community Examination and Discussion forum hosts independent attempts to re-run the Lean projects, comments on theorem statements and material explaining the hard parts of the proofs. Some participants confirm that the formal developments provided do check against their own claims.
But three levels of checking must be kept apart: whether the Lean code reproduces; whether the code proves exactly the mathematical statement from the paper; whether the full interpretation of that statement, applied to classical ETH, is correct. At each level separate questions can arise about models of computation, input encodings and the running time of reductions.
Impagliazzo and Paturi of UC San Diego, together with Ryan Williams of MIT, have taken on organising the independent discussion. The researchers' statement says plainly that the organisers' involvement should not be treated as confirmation that the result is correct. They plan open study of the papers and scientific meetings.
Complexity theorist Lance Fortnow expressed optimism about the result in his blog while noting that he had not personally checked the proof. He also stressed an important logical point: if a conditional hypothesis turns out to be false, statements that previously followed from it do not necessarily become false. It is just that the old justification can no longer be applied in the same form.
Does this settle P versus NP
No. Even a correct algorithm running in 2^(o(n)) time can remain far slower than any polynomial algorithm. So refuting ETH does not imply that P equals NP, and it does not create a universal fast way to solve every NP-complete problem.
Nor should one conclude that the cryptosystems used on the internet will be broken any time soon. Practical consequences depend on the specific algorithms, their constants, problem sizes and possible reductions from other problems to 3-SAT.
The result's potential for theory is enormous. It could open the way to new algorithmic bounds and force a rethink of hundreds of studies that use ETH as a premise. But the road from an asymptotic theorem to faster real-world software can be very long.
Why this story matters especially for AI
What comes into focus is not a contest between brands but a new way of doing research. AI systems now propose proofs of such complexity that analysing them requires collective expert effort, formal checking systems and independent explanations.
If the result survives scrutiny, it will be a significant achievement for AI in pure mathematics. If gaps are found, the very process of public analysis will still show how the scientific community should check ever larger results produced with the help of models. A scientific discovery gains value when it can be reproduced, understood and independently confirmed.
Sources
- UC San Diego: Independent Review of a High-profile OpenAI and Anthropic Result, 19 November 2026
- OpenAI: Working with academic communities to build scientific understanding
- Anthropic / Hexagon: A 2^o(n) Time Algorithm for 3-SAT
- Anthropic's Lean formalisation source code
- ETH: Community Examination and Discussion, organisers' statement
- Lance Fortnow: The Exponential Time Refutation
