Report · science.org
AI cracks a 27-year-old pillar of computer science, OpenAI and Anthropic claim
science.org
Source published October 30, 2026
Summary: 2 min read
55/100
Summary
OpenAI and Anthropic separately released proofs that they say refute the exponential time hypothesis (ETH), a 1999 conjecture that solving satisfiability problems cannot avoid exponential growth in computational effort. Both companies said their models found the results on 16 October, using different proof routes, and said the Lean proof-checking language formally verified them. Human experts have not yet fully confirmed either proof, and Russell Impagliazzo, co-creator of ETH, said the result is not yet 100% certain. ETH underlies claims about the difficulty of satisfiability, a class of problems relevant to chip design, scheduling, and cryptography. Refuting it would not solve the P versus NP problem, but it would mark progress toward that longstanding question and could require researchers to revisit results based on ETH. Anthropic identified more than 800 papers relying on ETH or a stronger version. Its paper says the new method is unlikely to outperform brute-force search for instances with fewer than roughly 10 million switches, limiting near-term practical effects. OpenAI asked Impagliazzo, ETH co-author Ramamohan Paturi, and MIT computer scientist Ryan Williams to help make its initially unreadable proof accessible. The group plans a human-readable version and a virtual review conference before year-end. OpenAI also released work on the Kakeya conjecture and submitted a 1,147-page quantum Yang-Mills proof to a committee chaired by Nobel laureate David Gross, which has not released it pending review.
Key Takeaways
- OpenAI and Anthropic say their AI systems independently found formally Lean-verified proofs refuting the exponential time hypothesis, although human review remains incomplete.
- The exponential time hypothesis, proposed in 1999 by Russell Impagliazzo and Ramamohan Paturi, holds that satisfiability problems cannot be solved without exponential-time growth in the worst case.
- A confirmed ETH refutation would not resolve P versus NP, but it could force researchers to rebuild theoretical results that rely on ETH or stronger related assumptions.
- Anthropic says its proposed algorithm is unlikely to beat brute-force search on satisfiability instances with fewer than about 10 million switches, so immediate practical benefits are limited.
- OpenAI recruited external computer scientists to help interpret its ETH proof, while critics questioned AI companies selecting reviewers for their own results.
What the discussion said
The discussion largely refused the headline’s victory lap and focused instead on what a collapse of a major complexity assumption would actually change. One technically minded thread argues that if the Exponential Time Hypothesis fails, its stronger variant and many conditional lower bounds built on it may fail too. That matters for machine learning because a common argument that self-attention must incur quadratic cost would no longer rule out a better algorithm. Still, commenters stress that invalidating a no-go proof is not the same thing as producing fast attention; the practical breakthrough remains unclaimed until someone constructs and validates it. Readers also flagged verification as the missing center of gravity. A flashy scientific claim needs scrutiny, especially when its consequences cascade through many results stated as optimal under these assumptions. Elsewhere, the tone is openly cynical: some see the announcement as familiar corporate AI promotion rather than established science. Another commenter imagines a far more disruptive outcome if P equaled NP, warning that modern online security and economic systems could be badly shaken before society adapts. The thread therefore treats the result as potentially profound, but emphatically provisional rather than a settled AI advance.
Where opinion split
The core dispute is whether the announcement represents a genuine computational breakthrough or an unverified marketing claim. Supporters see a possible collapse of assumptions that underpin limits on efficient attention and other algorithms; skeptics counter that removing a conditional lower bound neither supplies a faster method nor proves the headline’s sweeping conclusion.
Coverage & discussions
Reddit r/artificial · science.org
Community discussions
Community Sentiment
Positives
- If key complexity assumptions fall, the supposed quadratic floor under self-attention may be far less secure, reopening the search for materially cheaper long-context models.
- The strongest technical response pushes past the headline toward a useful research agenda: identify which conditional lower bounds survive weaker assumptions and rebuild the rest rigorously.
Concerns
- Toppling a proof that fast attention is impossible does not create a fast attention algorithm, so the claimed practical AI payoff remains speculative.
- Readers see verification as the real test: a result with consequences for decades of complexity theory cannot be treated as settled because AI companies announced it.
- Some commenters dismiss the framing as routine corporate hype, arguing that promotional confidence is not evidence of a landmark scientific result.
- If the discussion’s P-versus-NP implication were real, broken cryptographic assumptions could disrupt internet security and the economy before any benefits arrive.
Related Articles
Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?
Oct 27, 2026
OpenAI just scooped human researchers on a million-dollar quantum math problem
Oct 27, 2026
Why Erdős Problems Are Falling to AI
Aug 5, 2026
OpenAi claims to have proved that the Exponential Time Hypothesis is false, invalidating many past results that relied on it being true.
Oct 26, 2026
Human mathematicians are being outcounterexampled
Jul 20, 2026