Analysis

OpenAI and Anthropic say AI disproved the Exponential Time Hypothesis, but the claim is not certified and the speedup only starts at astronomically large inputs

OpenAI and Anthropic say AI disproved the Exponential Time Hypothesis. Impagliazzo calls it shocking, but review is pending and gains need huge inputs.

By ·

Russell Impagliazzo, who co-proposed the Exponential Time Hypothesis (ETH) in the 1990s, called an AI-produced refutation of it very shocking news, according to press coverage relayed by AI Weekly on November 7. The framing needs care: two papers, one from OpenAI and one from Anthropic, were announced on October 26 and claim a faster algorithm for 3-SAT; reviewers say their involvement is not a certification, the result does not settle P versus NP, and the speedup only beats brute force at input sizes far beyond anything storable. Disclosure: Anthropic makes Claude, which helps draft articles on this site, and published one of the two papers.

The essentials

What is and is not shown

A subexponential algorithm is not a polynomial one, so both labs say the result does not resolve P versus NP, and OpenAI says the speedup does not extend to NP problems in general. Lean checking confirms the logic of a formal statement, but the reviewers still asked for raw data and a conference, which OpenAI agreed to fund, per AI Weekly. Dates reported: the AI found the natural-language argument on October 16, it was formalized the next day and the papers came out on October 26.

Chips and encryption: what is established

ETH is a hypothesis about worst cases, so the immediate effect is on theory and on lower bounds built on it. Talk of faster chip verification or weaker encryption is long-term speculation. BeInCrypto and Let's Data Science say current cryptography and industrial solvers are untouched, and AI Weekly relays a computer scientist calling one press article misleading. HackerNoon says the authors also apply the method to elliptic-curve problems on paper; we have not seen that checked.

What is not established

Summary table

Summary table
PointWhat is stated as of November 7, 2026Source
AnnouncementTwo papers announced October 26, 2026 (OpenAI 67 pages, Anthropic 49 pages)AI Weekly
Result claimed3-SAT in 2^o(n) time, checked in LeanAI Weekly
Break-even sizeAbout 10^2,389 variables (OpenAI), 10^10,000 (Anthropic five-clause case)AI Weekly
ReviewersImpagliazzo, Williams, Paturi; joint statement says not a certificationAI Weekly
P versus NPNot resolved, per both labsLet's Data Science

FAQ

Did AI prove that P equals NP?

No. The claimed algorithm is subexponential, not polynomial, and both labs say P versus NP is not resolved.

Is encryption now weaker?

Not in practice. Outlets we read say deployed cryptography is unaffected, and the speedup only appears at absurdly large inputs.

Is the proof confirmed?

Not yet certified. The proofs were checked in Lean, but the reviewers say their involvement is not certification and further study is under way.

Method and limits

Sources checked on November 8, 2026. We did not read the two papers, the Lean files or the original newspaper articles; we relied on AI Weekly, Let's Data Science, HackerNoon, BeInCrypto and Wikipedia. Disclosure: Anthropic makes Claude, which helps draft articles on this site. This is not investment or security advice.

Sources

Spotted an error in this article? Report it · Our corrections policy

OrigoTech logo

New: the app iPhone & iPad

OrigoTech is now an iPhone and iPad app

Read the articles natively, with “New” markers on unread ones, local search and offline reading of what you have already loaded. Free, no account, iOS 17 or later; ads appear between articles.

Rekha icon: a house drawn in a single stroke

From the same author Self-promotion

An Eulerian path, drawn with your finger

Rekha, the iPhone game by OrigoTech's author: connect every dot in a single stroke without tracing the same link twice, across 500 drawings that are all solvable.

The OrigoTech newsletter

A sourced weekly digest of AI tool news.

Read next