Two AI labs say models disproved a key computing hypothesis

Anthropic on Oct. 27 posted a paper on Hexagon, a math preprint site, saying an internal Claude research model found an algorithm that refutes the Exponential Time Hypothesis, a long-standing conjecture about how hard a basic logic problem is to solve. The paper says an internal model at OpenAI “independently and concurrently” claims to have proven a similar result. OpenAI made that claim on Oct. 26, as AI Early Edition reported this morning.

The claim: The paper, titled “A 2^o(n) Time Algorithm for 3-SAT,” presents a deterministic algorithm for 3-SAT, the problem of deciding whether a formula with three variables per clause can be made true, that runs in subexponential time. The paper says the algorithm also solves the harder counting version, #3-SAT, by reporting how many satisfying assignments exist. Anthropic said the result has been formalized in Lean 4, a proof-checking language.

What the hypothesis says: As the paper explains it, the Exponential Time Hypothesis, proposed by Russell Impagliazzo and Ramamohan Paturi, holds that 3-SAT can’t be solved faster than a fixed exponential rate. The paper says a literature search carried out by Claude found more than 800 papers that prove at least one result only under that hypothesis or a stronger one. It also says the result refutes the stronger version, known as SETH, but not the Orthogonal Vectors hypothesis, on which many other lower bounds rest.

How it was found: According to the paper’s provenance statement, the core algorithm was found on Oct. 16 by an internal Claude research model “with 14M output tokens and no human input.” Anthropic researchers then worked with Claude to improve the presentation. Hexagon labels the paper “Primarily AI-generated text.”

What it doesn’t do: The paper says the result “does not bear on the P vs NP question directly” and doesn’t yield practical algorithms. It calls the result “purely asymptotic.” The paper says the proven bound doesn’t beat brute-force search until formulas have an astronomically large number of variables, so “our result says nothing about solving formulas in practice.”

The OpenAI side: OpenAI said its system found its disproof on Oct. 16 and formalized it in Lean on Oct. 17. A group led by Impagliazzo and Paturi of UC San Diego and Ryan Williams of MIT will verify and shepherd that work, OpenAI said. Its preprint is on GitHub.

Our read: Two labs announcing the same kind of result from the same day of model output is striking, and both say machine-checked proofs back them. But neither claim has been verified by outside experts, and both still need peer review. A Lean check confirms that a proof matches the formal statement it was given, not that the statement captures the hypothesis as mathematicians mean it, and that gap is what reviewers will examine first. If the results hold, the paper’s own count of more than 800 dependent papers shows how much of complexity theory would need revisiting. Anthropic’s paper is also direct that none of this speeds up real-world solving. For now, these are two companies’ claims, and the outside review is the real test.

What’s next: OpenAI said the Impagliazzo, Paturi and Williams group will verify and shepherd its result, and that it agreed to fund a conference on it.