The Exponential Time Hypothesis, proposed in 1999, holds that no shortcut can escape the exponential growth in effort needed to solve satisfiability puzzles, in which switches must be set so every rule in a list is met. Each added switch doubles the number of possible combinations. The idea is closely tied to the P versus NP problem and lets researchers show other problems are hard by linking them back to satisfiability. The hypothesis has been widely believed true and used in hundreds of papers across graph theory, computational biology, databases and computational geometry, OpenAI said in its announcement. If it falls, those conditional hardness results lose their footing.
OpenAI's disclosure came as part of a broader release that also covered harmonic analysis and quantum field theory. Both companies say their results were formally verified in Lean, a programming language used as a proof checker, though no human has yet fully confirmed the proofs, and the episode has raised questions about how AI-generated work should be shared, Science reported. Those questions include who gets credit, who gets early access and how a community verifies a proof it did not write.
Anthropic's claim surfaced with less ceremony. It came hours after OpenAI posted its results and reached an almost identical proof by a different route. The company's public collection of Lean proofs includes a project credited to its Claude model, describing an algorithm that counts every solution to a broad class of satisfiability puzzles fast enough to break the conjecture, according to the repository.
Verification is now the open task. Russell Impagliazzo and Ramamohan Paturi of UC San Diego, two of the hypothesis' original proposers, will oversee the review with MIT's Ryan Williams, and at the group's request OpenAI is publishing the raw results and paying for a conference on what they mean for the field, the company said. Even if the refutation holds, turning it into faster real-world algorithms will take what the company called significant further research.