OpenAI and Anthropic each say AI disproved a central conjecture in computer science

On 26 October OpenAI and Anthropic each published an algorithm, said to have been found by one of their models, that they say refutes the Exponential Time Hypothesis (ETH). Posted the same day and checked in the Lean proof language, both papers claim 3-SAT can be solved in subexponential time. OpenAI’s announcement bundled two further claims, in analysis and in physics.

ETH, introduced by Russell Impagliazzo and Ramamohan Paturi, holds that 3-SAT needs exponential time in the worst case. OpenAI’s paper gives a deterministic counting algorithm for k-CNF formulas running in roughly 2^(n/(log n)^(1/2+o(1))) time. Anthropic’s repository, whose paper is credited to “Claude (Anthropic)”, reports a 2^o(n) algorithm that it says an internal research Claude model found. Both say the results are asymptotic: Anthropic’s paper says it does not bear directly on P versus NP or yield practical algorithms. Anthropic’s Lean files depend only on Lean’s three standard axioms, though its README notes that no machine checks that the Lean statement says what the paper says, so a reader must. TechCrunch and Quanta reported that Anthropic’s release came hours after OpenAI’s.

OpenAI said it had asked Impagliazzo, Paturi and Ryan Williams of MIT to organise a review, and agreed to publish its raw data and fund a conference. In an AFP interview Williams, a long-time ETH sceptic, said he felt vindicated; Impagliazzo said he “would have much preferred it to be discovered by a human who could explain their thought process”; Paturi said “A company’s announcement cannot substitute for the community’s assessment.” TechCrunch reported the group’s open letter invites feedback, and that OpenAI told Williams it was “reasonably confident” the result breaks no cryptography.

OpenAI’s second claim is a 59-page manuscript proving Sogge’s local smoothing conjecture in every dimension from two up, from which it deduces the Kakeya conjecture. Unlike the other two it has no review group; OpenAI released the output directly, as it had on 6 October.

The third is a proof of the existence of four-dimensional quantum Yang-Mills theory with quarks. Physicists led by David Gross are withholding the 1,147-page manuscript. Their statement says confinement and the mass gap “remain very important open challenges”, and:

Before we release it, we would like to be convinced that it is correct.

— Shepherding committee statement

Quanta also noted unvetted, parallel Yang-Mills work by Anthropic’s Levent Alpöge and Ethan Sussman using Claude. As of 2 November none of the three claims had been reported as confirmed or refuted by outside experts.