Two AI labs say they broke the same pillar of computer science, hours apart

For 27 years a large part of computer science has rested on a bet nobody could prove: that certain problems are hard, stay hard, and no amount of cleverness gets you out of paying for it. On Monday OpenAI said one of its internal models had knocked that bet over. A few hours later Anthropic posted a paper saying its own model had done the same thing.

The bet is called the Exponential Time Hypothesis, or ETH. If either paper holds up, it is false. Two of the first people checking the claim are the people who proposed it.

What actually got claimed

ETH is about 3-SAT, the textbook hard problem. You get a long list of conditions on yes-or-no variables, and you need one setting of the variables that satisfies every condition at once. Checking an answer is easy. Finding one, as far as anyone knew, costs a search that grows exponentially with each variable you add. Researchers have chipped at the exponent since the 1980s; Anthropic's paper puts the previous deterministic record at O(1.328^n).

ETH, put forward by Russell Impagliazzo and Ramamohan Paturi in 1999, says the chipping has a floor. There is some fixed exponential rate you can never get under.

OpenAI's preprint is titled "The Exponential Time Hypothesis is False" and sits in the company's public math repository on GitHub. It describes a deterministic algorithm that counts every satisfying assignment of a k-SAT formula in subexponential time, using only polynomial memory. The abstract does not hedge: "Our algorithm refutes the Exponential Time Hypothesis (ETH)." The paper is dated October 17 and was revised on October 25.

Anthropic's version is called "A 2^o(n) Time Algorithm for 3-SAT," and its listed author is "Claude, Anthropic." It went up in Anthropic's formal-math repository hours after OpenAI's announcement and claims a counting bound of the same shape, 2^O(n log log n / sqrt(log n)). According to OfficeChai's reading of the paper, an internal Claude research model found the core algorithm on October 16 using 14 million output tokens, with no human input in the discovery itself. Reports on OpenAI's paper put its model's disproof on the same day.

Two rival labs, one hypothesis, same date. Neither company has said much about the coincidence.

Proofs that no person has finished reading

Both results come with formal proofs in Lean, a proof assistant that checks every logical step mechanically. Anthropic's README says its build takes about eight minutes on 24 virtual CPUs and is rechecked by a second, independently written kernel called nanoda. It also says the Lean code "was written by AI models." OfficeChai reports that the paper's appendix goes further and says no person is known to have checked it.

Lean catches broken logic. It does not catch a theorem statement that quietly says something weaker than the paper claims. That already happened once: human readers of OpenAI's Lean-verified Navier-Stokes work found Lean had verified a weaker statement than the one OpenAI published, Gizmodo reported, citing Science. Anthropic seems to know where the soft spot is. Its statement file is kept deliberately small, the README says, "so that a reader can check this."

OpenAI handed its ETH result to Impagliazzo and Paturi at UC San Diego and Ryan Williams at MIT. The group says it signed no nondisclosure agreement, isn't being paid and will publish interim findings as it goes. OpenAI agreed to release all the raw data and to pay for a computer science conference on the result. The reviewers' open letter says their "involvement should not be taken as certification of the claim," according to Cryptopolitan. Writing on X, Williams said practical SAT solving could see real progress within a year, then added: "I really don't know."

Caution is earned. On October 6 OpenAI pushed 722 machine-written preprints to GitHub. Three were withdrawn within a day over a sign error and 14 more were revised, Cryptopolitan reported. A year earlier the mathematician Thomas Bloom called an OpenAI executive's claim about solved Erdős problems "a dramatic misrepresentation."

ETH was one of three announcements. OpenAI also claims a proof of the local smoothing conjecture in every dimension, which would settle the Kakeya conjecture along the way, and a proof that certain four-dimensional quantum field theories exist, including the existence half of the Yang-Mills Millennium Prize problem. The physics material is being held back while a group led by Nobel laureate David Gross writes it up. Scientific American reports that an advisory group OpenAI itself set up had just said "there is no scientific reason for delaying the release any further."

If ETH falls, its stronger cousin SETH falls with it, and so does the footing under a big stack of fine-grained complexity results. Those papers proved things like "this problem can't be solved faster unless ETH is false." Each of those proofs still holds, but each one now starts from a false premise. P versus NP is untouched, since the new algorithms are still slower than polynomial.

Nor is your SAT solver about to get faster. Anthropic's README says flatly that "the result is purely asymptotic and says nothing about solving formulas in practice." OfficeChai, summarizing the paper, says the bound doesn't beat brute force on a typical formula until there are roughly 10^10,000 variables.

The strangest part of Anthropic's folder is at the bottom. The README says Claude Opus 5.5, running at high effort, can rederive the refutation from a condensed hint written for AI models. The hypothesis survived 27 years of human attack. The hint fits in one paragraph, full of tensor networks and swap operators, and its last two words are "Prove it."

Sources: OpenAI: The Exponential Time Hypothesis is False (preprint, GitHub), Anthropic: A 2^o(n) Time Algorithm for 3-SAT (GitHub), Scientific American, Gizmodo, The Decoder, OfficeChai, Cryptopolitan.