Atlas AI Resources

← Back to AI News

AI research

OpenAI and Anthropic say their AI disproved a 27-year-old rule of computer science. Experts are still checking.

Published November 3, 2026

On October 26, OpenAI said one of its internal AI models had disproved the Exponential Time Hypothesis, an assumption about how hard certain logic puzzles are that computer scientists have leaned on since 1999. Hours later, Anthropic posted its own AI-found proof of the same thing. Both companies say a proof-checking program accepted their work. Outside experts call it a major result if it holds, but no one outside the two companies has yet confirmed it, and it changes nothing about how fast your computer solves anything today.

What happened

The puzzle is called satisfiability. Science magazine explains it with switches: you have a set of on-off switches and a list of rules, each naming three switches and how they should be set, and a rule is met if at least one of its three switches is set its way. Can you set every switch so all the rules are met? Every extra switch doubles the number of combinations to try, so the work grows exponentially, meaning it multiplies with each step instead of adding.

The Exponential Time Hypothesis, or ETH, was proposed by Russell Impagliazzo and Ramamohan Paturi of UC San Diego (OpenAI also credits Francis Zane). It says that clever shortcuts can trim the work, but no method can ever escape that exponential climb. OpenAI’s paper, credited simply to “OpenAI,” gives a method that grows a little more slowly than exponential, which would make ETH false. OpenAI says its AI found the argument on October 16 and turned it into a checkable formal proof the next day. Anthropic’s paper, credited to “Claude (Anthropic),” reaches the same conclusion by a different route; Science reports Anthropic says its model found it on the same day.

Both companies used Lean, a programming language that checks proofs step by step, much like a spell checker that only passes airtight logic. Neither paper is peer-reviewed. Instead, OpenAI asked Ryan Williams of MIT to shepherd the result, and he recruited Impagliazzo and Paturi, Science reports. The three have invited other researchers to help organize an open examination. They signed no nondisclosure agreements and are unpaid, and they plan a virtual meeting before the end of 2026.

Why it matters to a normal person

Mostly, it matters as a sign of what AI can now do. Anthropic counted more than 800 research papers whose results rest on ETH or a stronger version of it, according to Science. Those results now need new foundations. “It would require a complete revision of several areas of algorithms and complexity,” Fedor Fomin of the University of Bergen told New Scientist.

It also raises a new question for science: who checks work when a company’s private model produces it? OpenAI picked the first reviewers itself, which Science reports has left some researchers uneasy. Magnus Wahlström of Royal Holloway, University of London, called it “mathematics done by press” in New Scientist.

What it does not mean

It does not mean computers got faster at real puzzles. Anthropic’s own write-up says the result “is purely asymptotic,” meaning it only describes behavior at enormous sizes, “and says nothing about solving formulas in practice.” Science reports Anthropic’s paper expects no gain over trying every combination below about 10 million switches, while trying every combination is already hopeless at about 100.

It does not mean the proof is confirmed. A Lean check shows the proof matches its own formal statement, not that the statement means what ETH means. Carlos Toledo, an independent checker, replayed both proofs and found they check, but wrote that this “does not certify that ETH is false.” Papex, a site that tracks AI research claims, notes that OpenAI’s Lean proof covers a slightly weaker speed bound than the headline one in its paper. “As far as I’m concerned, this is not 100% certain,” Impagliazzo told Science.

And it does not crack the famous P versus NP problem, which asks whether every problem that is quick to check is also quick to solve. “We should not view it as progress towards P versus NP,” Leslie Goldberg of the University of Oxford told New Scientist.

Related: OpenAI Posted 722 AI-Written Math Papers. Checking Them Will Take Months.

Sources