Three computer scientists asked to examine an AI-produced disproof of the exponential time hypothesis have declined to certify it. Russell Impagliazzo, Ramamohan Paturi and Ryan Williams are unpaid, signed no non-disclosure agreements, and have published no verdict. OpenAI and Anthropic released the competing proofs on 26 October 2026.
What the Exponential Time Hypothesis Says
The hypothesis is a bet that one famous problem never gets dramatically easier. Impagliazzo and Paturi, both computer scientists at the University of California, San Diego, proposed it in 1999, and it concerns 3-SAT: the task of deciding whether a logical formula made of three-term clauses can be satisfied at all.
In plain terms, it holds that every algorithm for 3-SAT needs time that grows exponentially with the number of variables, so the cost per variable never fades away. Theoretical computer scientists have leaned on it heavily, because assuming it lets them prove that other problems in graph theory, databases and computational biology are also hard. Claude’s own literature search, cited in Anthropic’s paper, counted more than 800 published papers whose results depend on the hypothesis or a close relative holding true.
What the Two Papers Claim
Both labs claim an algorithm that beats the hypothesis by counting 3-SAT solutions in less than exponential time. Each says an internal model found the core algorithm on 16 October 2026, and each published separately ten days later.
| OpenAI | Anthropic | |
|---|---|---|
| Paper title | The Exponential Time Hypothesis is False | A 2^o(n) Time Algorithm for 3-SAT |
| Length | 67 pages | 49 pages |
| Listed author | An unnamed internal OpenAI model | “Claude, Anthropic” |
| Method | Deterministic counting of satisfying assignments in polynomial memory | Tensor networks and rank arguments |
| Claimed running time | Roughly 2^(n/√log n) | Roughly 2^(n/√log n) |
| Also claims to refute | SETH, Gap-ETH, NSETH | SETH |
Anthropic says its research model produced the core algorithm with about 14 million output tokens and no human input, and that its researchers then worked with Claude on how the result was presented. OpenAI has said turning the result into faster real-world algorithms “will require significant further research”. Neither paper has been peer-reviewed, and neither gives concrete constants, so nobody can yet say at what problem size the new method would overtake existing solvers.
Why the Named Reviewers Will Not Certify It
The reviewers put their position in writing before any examination began. In an open letter to their field, Impagliazzo, Paturi and Williams wrote: “Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny.” They added that “if the claim is correct, it will change an important part of theoretical computer science”.
The terms are unusually bare. According to Williams, who is a computer scientist at the Massachusetts Institute of Technology, the group signed no non-disclosure agreements and will not be paid. It asked OpenAI to publish all its raw data on the result and to fund a conference for the research community; both Williams and OpenAI say the company agreed. Separately, OpenAI has given $5 million to the Simons Foundation for workshops and conferences on AI-produced results, though that payment has not been tied publicly to this review.
Impagliazzo, who co-proposed the hypothesis he is now being asked to bury, called it very shocking news in comments to The New York Times on 7 November 2026, and noted that most researchers had expected stricter versions of the hypothesis to fall first. He told the journal Science that “as far as I’m concerned, this is not 100% certain”. Williams has said parts of the OpenAI proof look routine while two or three “alien-looking” parts still need scrutiny.
As of 8 November 2026, thirteen days after publication, no independent verdict has been published, no reviewer has reported a flaw in public, and neither lab has withdrawn or amended its central claim.
What Lean Checked, and What It Did Not
Both labs say their arguments were checked in Lean, a proof assistant that verifies a formal proof step by step against a small set of axioms. That is a real guarantee, and a narrow one.
Lean confirms that the formal theorem as written follows from its premises. It does not confirm that the formal statement faithfully matches the hypothesis as the field defines it, which depends on human choices about the machine model and how formulas are encoded. In OpenAI’s case the formalised bound is also slightly weaker than the headline bound, though still enough to contradict the hypothesis if the definitions line up. Checking that correspondence is human work, and it is the main thing the review has to settle.
OpenAI’s own repository is blunt about the general standard of this material. Its README describes the manuscripts as “raw research data” produced by an unnamed internal model, warns that some unformalized results “could have issues”, and reports that about 42 per cent of top-line results across its 721 manuscripts are formalized in Lean. The company has released AI-generated proofs at this scale before, including an OpenAI Navier-Stokes proof in September that faces a two-year wait under the Clay Mathematics Institute’s rules, and it set up an external math advisory group of nine members that same month.
No, This Does Not Break Encryption
The result would not weaken the encryption protecting bank transfers, messages or websites. The hypothesis was never what those systems rested on.
RSA, the public-key system behind much of the web’s certificate infrastructure, depends on the difficulty of factoring large numbers, and factoring has had a subexponential algorithm — the general number field sieve — for decades without becoming breakable in practice. AES, the symmetric cipher used to encrypt data in transit and at rest, does not rest on the hypothesis either. “Subexponential” is also a weaker word than it sounds: a running time below 2^n can still be astronomically long.
Nor does the claim settle the field’s biggest open question. Disproving the hypothesis would not show that P equals NP, because the claimed bound remains far above any polynomial, and OpenAI’s own president has said P still probably does not equal NP. Williams has suggested the result should make computer scientists put only a little more weight on the possibility.
Why Crypto Traders Read the Wrong ETH
The acronym collided with a much more heavily traded one. “ETH” is the ticker for Ether, the cryptocurrency of the Ethereum network, and traders reacting to headlines announcing that “ETH is false” briefly treated the news as market-moving.
It is not. The exponential time hypothesis is a 1999 conjecture in complexity theory with no connection to Ethereum, its price or its founder. Ethereum’s security rests on elliptic-curve cryptography and proof-of-stake consensus, neither of which is addressed by either paper.
What Happens to the 800 Papers Built on the Hypothesis
If the disproof survives review, the papers that assumed the hypothesis do not become wrong — they become unproven. Each of those results took the form “this problem is hard, assuming the exponential time hypothesis”. Removing the assumption removes the proof of hardness; it does not hand anyone a fast algorithm for the problem.
Some lower bounds would survive on other foundations. The quadratic lower bound for edit distance, for instance, also rests on the weaker orthogonal vectors conjecture, which neither paper claims to refute. Practising programmers would see nothing change: real SAT solvers exploit structure in real-world instances rather than the worst cases the hypothesis describes, and no solver is affected by either result today.
The episode also raises a question about credit that the reviewers themselves flagged: that recognition may flow to whoever publishes first or has the largest models, while the slower work of verifying and explaining a result counts for less. It is not the first AI-produced scientific claim to meet the reproducibility problem — a Claude enzyme discovery in September failed to reappear across ten reruns.
Frequently Asked Questions
Has the Exponential Time Hypothesis Actually Been Disproved?
Not confirmed. OpenAI and Anthropic have each published a claimed disproof with a machine-checked formal proof, but no independent group has verified that the formal statements match the hypothesis, and the reviewers have published no verdict as of 8 November 2026.
Who Is Reviewing the Claim?
Russell Impagliazzo and Ramamohan Paturi of UC San Diego, who proposed the hypothesis in 1999, together with Ryan Williams of MIT. They are organising an open examination rather than a private one, and have said their involvement is not an endorsement.
Does This Mean P Equals NP?
No. The claimed algorithm still takes far longer than polynomial time, and the papers do not show that every problem in NP can be solved quickly. OpenAI’s president has said P still probably does not equal NP.
Is My Encryption or My Bitcoin at Risk?
No. RSA depends on factoring and AES on symmetric key design, neither of which the hypothesis underpins, and nothing in either paper touches the elliptic-curve cryptography used by Bitcoin and Ethereum.
Why Did Both Labs Find the Same Result on the Same Day?
Both say their models produced the core algorithm on 16 October 2026 and describe the work as independent, using different methods and arriving at a similar running time. No outside party has examined how that coincidence arose.
