Two AI labs say the Exponential Time Hypothesis is false. What that means

On Monday 26 October OpenAI said an internal AI system had proved that the Exponential Time Hypothesis, usually shortened to ETH, is false. Hours later Anthropic posted a paper of its own, written up from work by an internal Claude research model, claiming the same thing by a different route. Both companies say a proof-checking program has verified their work. If the claims hold, they overturn an assumption that computer scientists have leaned on for more than 25 years. Here is what that means, and what it does not.

What the Exponential Time Hypothesis says

ETH is about a classic puzzle called satisfiability, or SAT. Science magazine explains it well with switches. Imagine a bank of on/off switches and a list of rules. Each rule names three switches and a position for each, and is met if at least one of them is set that way. Is there a way to set the switches so that every rule is met?

Checking a proposed answer is easy. Finding one is hard, because every extra switch doubles the number of combinations. Clever methods have been found that beat checking every combination, but they all still slow down exponentially as the puzzle grows. ETH, proposed by Russell Impagliazzo and Ramamohan Paturi of the University of California San Diego, says that will always be true: no method can escape that exponential climb for the three-switch version of the puzzle, known as 3-SAT.

Researchers have used ETH as a foundation. If you assume it, you can show that many other problems are also hard. Anthropic says a literature search by Claude found more than 800 papers that prove at least one of their results only by assuming ETH or a stronger version of it.

What OpenAI and Anthropic claim

OpenAI says its model found a written disproof on 16 October and the team formalised it in Lean, a language for machine-checked proofs, on 17 October. The AI-written paper, titled bluntly "The Exponential Time Hypothesis is False", describes a method that counts every valid setting of the switches in "subexponential" time: slower than any fixed polynomial, but faster than the exponential growth ETH predicted. Counting the solutions also tells you whether there is at least one. The paper says this refutes not only ETH but several stronger relatives.

Anthropic's paper, "A 2^o(n) Time Algorithm for 3-SAT", credits "Claude" as its author. It says the core method was found on the same day, 16 October, by an internal Claude research model using 14 million output tokens with no human input. A spokesperson told Science that Anthropic's internal teams "reworked the paper's introduction for clarity ahead of release". Its proof is also written in Lean, and the two companies' methods differ.

How sure can we be?

A Lean proof is strong evidence: the computer checks every step, so faulty reasoning is rejected. But there is a catch that both companies acknowledge in different ways. Lean checks the proof of the statement written in Lean. A human still has to confirm that the Lean statement really says what the paper claims. Anthropic's repository says so directly: "no machine checks that this file says what the paper says". It keeps that file short so people can check it by hand.

Human experts have not finished that work. "As far as I'm concerned, this is not 100% certain," Impagliazzo, one of the people who proposed ETH, told Science. Even so, the reaction from specialists has been striking. Holger Dell of the IT University of Copenhagen told Science: "Clearly this is a major breakthrough."

Will this make computers faster?

No, not in any practical sense. Anthropic is unusually blunt. Its write-up says the result is "purely asymptotic" and "says nothing about solving formulas in practice". Its approach seems unlikely to beat simply trying every combination unless a puzzle has more than about 10 million switches, according to Science, while trying every combination is already hopeless at around 100.

It does not solve the famous P versus NP problem either. Science notes that the new results only just break ETH and leave P versus NP "far out of reach". It also does not appear to break encryption. Ryan Williams of MIT told TechCrunch that one of his first questions to OpenAI was whether any encryption systems were affected, and that OpenAI had checked and was "reasonably confident" they were not.

The impact is on theory. Results that rest on ETH will need to be rebuilt on safer assumptions. "Every computer scientist should probably put a little more weight on the plausibility of P = NP, but one's weight may vary," Williams told TechCrunch.

How the results were released

The way the work reached the public has drawn almost as much attention as the maths. Earlier in October, OpenAI posted hundreds of AI-written maths papers in one go, which Williams called a "DDOS attack on mathematicians". This time OpenAI tried something different. It asked outside experts to act as "shepherds" for each result:

• Computer science (ETH). Impagliazzo, Paturi and Williams agreed to organise an open review. They say they signed no non-disclosure agreements and are unpaid, and that their involvement "should not be taken as certification of the claim". At their request, OpenAI published the raw material and committed to funding a conference.
• Maths. OpenAI says its models proved the local smoothing conjecture in every dimension, which would also settle the Kakeya and Stein restriction conjectures. It released the AI output as it was, on its expert's advice.
• Physics. OpenAI claims a rigorous proof that certain quantum field theories exist in four dimensions, including quantum chromodynamics. A committee chaired by Nobel laureate David Gross is holding the material back until it is satisfied.

Not everyone is comfortable with an AI company choosing the gatekeepers for its own results. Science reports that an independent advisory group of mathematicians said companies should not handpick reviewers. Williams himself told Science it would have been better for academics to select the people in charge. Anthropic took the opposite approach. It appointed no outside reviewers, simply posted its paper and Lean files, and told Science: "It's important for the theoretical computer science community to lead the discussion on what this finding means for their field."

What happens next

According to Science, the ETH group plans a fully human-readable proof, a virtual review conference before the end of the year and possibly an in-person meeting in 2027. Until then, the honest summary is this: two independent AI systems produced machine-checked arguments that ETH is false, specialists are taking them very seriously, and the final human verdict is still to come.

What to watch

• Whether reviewers confirm that the Lean statements match the papers' claims.
• How the two proofs differ, and whether people can learn new techniques from them.
• Whether the shepherd model, or Anthropic's straight-to-public approach, becomes the norm for AI-made discoveries.