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.
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
- The claim: OpenAI's 67-page paper and Anthropic's 49-page companion present 3-SAT algorithms running in 2^o(n) time, which would contradict ETH. Both say AI was heavily involved and that the proofs were checked in Lean, per AI Weekly.
- What ETH said: 3-SAT cannot be solved in subexponential time. It is stronger than P not equal to NP and is used to show that many algorithms are near-optimal, per Wikipedia.
- Verification so far: a group of Impagliazzo, Ryan Williams and Ramamohan Paturi examined the work. Their joint statement says their involvement should not be taken as certification, and Williams spoke of a few alien-looking parts the community must study.
- Practical reach: outside estimates put the break-even with brute force near 10^2,389 variables for OpenAI's bound and 10^10,000 for Anthropic's five-clause case. Current SAT solvers and encryption are not affected.
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
- Certification of the proofs by the review group: pending, per AI Weekly.
- Any usable speedup on real SAT instances: not shown; thresholds are astronomical.
- Any practical attack on encryption or chip-design tools: not established.
- Whether the Wall Street Journal and New York Times claims about chips and encryption go beyond speculation: we did not read them directly.
Summary table
| Point | What is stated as of November 7, 2026 | Source |
|---|---|---|
| Announcement | Two papers announced October 26, 2026 (OpenAI 67 pages, Anthropic 49 pages) | AI Weekly |
| Result claimed | 3-SAT in 2^o(n) time, checked in Lean | AI Weekly |
| Break-even size | About 10^2,389 variables (OpenAI), 10^10,000 (Anthropic five-clause case) | AI Weekly |
| Reviewers | Impagliazzo, Williams, Paturi; joint statement says not a certification | AI Weekly |
| P versus NP | Not resolved, per both labs | Let'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
- AI Weekly: OpenAI's AI Disproof of 1998 ETH Shocks Co-Author Impagliazzo (verified 2026-11-08)
- Let's Data Science: OpenAI and Anthropic Broke a 1999 Conjecture. Both Found It on October 16. (verified 2026-11-08)
- HackerNoon: OpenAI and Anthropic claim AI has disproved a 27-year-old computer science hypothesis (verified 2026-11-08)
- BeInCrypto: OpenAI Says Its AI Refuted the Exponential Time Hypothesis. Is Bitcoin Safe? (verified 2026-11-08)
- Wikipedia: Exponential time hypothesis (verified 2026-11-08)
Spotted an error in this article? Report it · Our corrections policy