OpenAI and Anthropic Both Say the Exponential Time Hypothesis Is False

What ETH says and what the claims are

ETH, proposed by Russell Impagliazzo and Ramamohan Paturi with Francis Zane, says 3-SAT cannot be solved in time 2^o(n) for n variables. OpenAI's post notes that it "has been used in hundreds of papers to derive conditional computational hardness results". If it is false, those results lose their basis, though not necessarily their conclusions.

Anthropic's README states the claim precisely: "A deterministic algorithm solves 3-SAT on n variables in time 2^o(n)". It says the algorithm also counts satisfying assignments within a stated bound, and adds: "The result is purely asymptotic and says nothing about solving formulas in practice." The paper's provenance note says the core algorithm "was found on October 16 by an internal Claude research model with 14M output tokens and no human input", and that Anthropic researchers then worked with Claude on the presentation. It also cites OpenAI's claim as independent and concurrent. OpenAI's post gives the same discovery date for its own system, October 16, with the Lean formalization finished on October 17.

What Lean does and does not settle

Anthropic's README is unusually direct about the limit. A short file, MainResults.lean, states that ETH is false and states the paper's main theorem. "Lean checks the proofs, but no machine checks that this file says what the paper says; the file is kept short so that a reader can check this." The repository's CI also uses Comparator to match theorem statements against a challenge file and re-checks the proofs with a second, independently written kernel. The build took about 8 minutes on 24 virtual CPUs.

So a passing Lean build establishes that the stated propositions follow from Lean's standard axioms. Whether those propositions are ETH as complexity theorists mean it, on the right machine model, is a question for people. That is where expert review now has to concentrate.

Three release strategies at OpenAI

OpenAI calls its manuscripts "a form of raw research data" and tried a different release for each result. For local smoothing, which it says also resolves the Kakeya and Stein restriction conjectures in all dimensions, it published the AI writeup and Lean proof. For ETH, a group led by Impagliazzo, Paturi and Ryan Williams will verify and explain the result, and OpenAI agreed to make all raw data public and to fund a conference. For physics, a group led by David Gross will hold the AI-produced artifacts and write the work up itself. The physics claim covers existence of pure Yang–Mills theory, which OpenAI describes as "part of" the Clay Millennium problem. It does not claim the mass gap.

The ETH reviewers have been explicit, according to a letter reported by R&D World: "Our involvement should not be taken as certification of the claim." The independent Advisory Group on Mathematics and Artificial Intelligence asked OpenAI to release the physics proofs, arguing that "understanding should develop in the open, with everyone given the same access."

What remains uncertain. No outside group has confirmed any of the three results. The physics proofs are not public and cannot be checked. Both labs credit unreleased internal models, so the methods cannot be reproduced. OpenAI's October 6 batch is a caution: its repository says some unformalized results "could have issues", and Scientific American reported that some had been retracted after outside scientists found mistakes.

Analysis: For engineers, nothing changes in SAT solvers this week. Both labs say the result is asymptotic. What changes is how machine-produced work gets checked. When a proof is too long for a referee to read, the human job shrinks to a small, readable statement file plus the check that the statement means what the paper claims. The same pattern applies to agent-written code with generated tests: the tests can pass while testing the wrong property. Keep the specification short and reviewed by a person, and treat everything below it as something to verify mechanically.

Sources and evidence

• Working with academic communities to build scientific understanding (OpenAI, October 26)
• openai/math repository: manuscripts and Lean formalizations (GitHub, updated October 26)
• A 2^o(n) Time Algorithm for 3-SAT: paper and Lean 4 formalization (anthropics/formal-math, October 27)
• The most exciting claims from OpenAI's heap of new proofs (Scientific American, October 8)
• OpenAI says its AI models produced major proofs in mathematics, computer science and physics (R&D World, October 27)