Two AI labs now say one of theoretical computer science’s load-bearing assumptions is false, and the researchers who first proposed it are the ones organizing the check. OpenAI posted a paper titled “The Exponential Time Hypothesis is False” on Monday, and Anthropic followed that night with its own claimed refutation, credited to Claude. Neither paper has been peer-reviewed, and no outside group has confirmed either proof yet.
The Exponential Time Hypothesis, or ETH, says no algorithm can solve the logic problem known as 3-SAT in time that grows slower than exponentially with the number of variables, written 2o(n), in the worst case. It is a stronger assumption than P ≠ NP, so knocking it down would not show that P = NP. OpenAI’s paper says its result “does not bear on the P vs NP question directly, nor does it yield any practical algorithms for NP-complete problems.” OpenAI said in its announcement that the conjecture has been used in “hundreds of papers” to derive hardness results in graph theory, computational biology, databases and computational geometry. Both labs describe a deterministic algorithm that counts the satisfying assignments of a formula in subexponential time, and both put Lean formalizations on GitHub next to their papers. OpenAI says its result “was subsequently verified in Lean.” Anthropic’s repository adds a caveat that applies to any such check: “Lean checks the proofs, but no machine checks that this file says what the paper says.”
The GitHub commit logs put the two releases about six hours apart. OpenAI’s files landed in its openai/math repository at 4:52 p.m. ET, and Anthropic’s arrived in its formal-math repository at 11:07 p.m. ET. Each company says its model found the result on Oct. 16. Anthropic’s paper says an internal Claude research model found the core algorithm “with 14M output tokens and no human input,” and that a model at OpenAI “independently and concurrently” claims a similar result. OpenAI’s post doesn’t mention Anthropic.
The people being asked to check it
OpenAI asked Russell Impagliazzo and Ramamohan Paturi of UC San Diego, who proposed ETH with Francis Zane, and MIT’s Ryan Williams to lead an outside group that will verify and explain the proof. The three were careful about what that means. “Our involvement should not be taken as certification of the claim,” they wrote in an open letter to colleagues. They asked OpenAI to make all raw data public and to pay for a conference on the result, and OpenAI says it agreed to both. Under the terms OpenAI published, participation is unpaid and nobody signs a nondisclosure agreement. The company also says it won’t seek academic credit for what its models produced.
Williams doesn’t expect this to be the last word on the problem. “I don’t think that OpenAI’s algorithm could possibly be the best algorithm you can get,” he told TechCrunch.
The first question was about encryption
A faster algorithm for this class of problem could, in principle, make cryptographic systems that rely on certain key sizes look broken, Williams told TechCrunch. He said it was one of the first things he asked OpenAI science lead Dan Roberts. OpenAI “checked, and they were reasonably confident that this didn’t … imply any breaks,” Williams said. Neither lab’s paper mentions cryptography.
Anthropic’s paper is blunt about the gap between theory and production. Its bound in terms of variables doesn’t beat exhaustive search until a formula has more than 10 billion variables, and the authors say their general approach seems unlikely to yield any general improvement below 10 million. Brute force already becomes unworkable at 100 variables, the paper notes. “Thus our result says nothing about solving formulas in practice,” the paper says. OpenAI’s post makes a similar point, saying that getting real-world gains from it “will require significant further research.”
For anyone running a SAT solver today, nothing changes this week. What does change is the theory that explains why some everyday algorithms seem to be as fast as they’ll get. OpenAI’s paper says its theorem refutes ETH along with the stronger SETH, Gap-ETH and NSETH, removing one basis for lower bounds on edit distance, longest common subsequence, regular-expression matching and Fréchet distance. Some of those bounds also follow from weaker hypotheses that may still hold, such as the Orthogonal Vectors Conjecture, the paper adds. A literature search run by Claude found more than 800 papers that prove at least one result only under ETH or a hypothesis that implies it, Anthropic said.
The computer science result was one of three OpenAI released Monday. It also published a proof of Sogge’s local smoothing conjecture in every dimension, which the company says settles the Kakeya and Stein restriction conjectures as well. A physics group led by Nobel laureate David Gross is holding back the AI-generated material on four-dimensional quantum field theories, including quantum chromodynamics, so it can write the result up itself. The staggered approach follows OpenAI’s early-October release of hundreds of AI-generated math manuscripts, which Williams called a “DDOS attack on mathematicians,” according to TechCrunch. Last week, a Microsoft researcher and a collaborator resolved the KLS conjecture with human-directed AI.
The organizers’ letter proposes a virtual meeting before the end of the year and lists Anthropic’s refutation among its resources, alongside OpenAI’s.