Claude's Claimed 3-SAT Refutation Needs Human Review
Anthropic reports a formally verified refutation of the Exponential Time Hypothesis, with an enormous threshold for beating exhaustive search and human review of the formal statements still needed.
Claude and the Claimed Refutation of the Exponential Time Hypothesis
Anthropic says its Claude model independently found an algorithm that disproves the Exponential Time Hypothesis. However, the final running time bound beats exhaustive search only when the number of variables exceeds one followed by 100 million zeros.
The claim concerns 3-SAT: assign true or false to variables so that every condition of the form “x or not y or z” is satisfied. Exhaustive search takes about 2^n steps, where n is the number of variables. The hypothesis states that there is a positive constant c such that every algorithm needs at least 2^(cn) steps in the worst case.
The company says its internal model found the main algorithm on October 16 without human involvement. Anthropic published the paper and formal proof on October 27. The company profile is available here: Anthropic in Eternal Search.
In the proposed algorithm, conditions become vertices in a graph, and shared variables connect those vertices. Counting solutions in separate parts of the graph requires enumerating the values of the connecting variables. The algorithm arranges the graph on a grid and uses algebraic rewrites to reduce their number. According to the paper, it counts all satisfying assignments in time on the order of 2^(δn) for any positive δ. Choosing δ smaller than c gives a bound faster than the hypothesized limit, refuting the hypothesis. The enormous threshold for beating exhaustive search limits the practical use of this bound.
The proof is written in Lean 4, a system for formalizing and checking mathematics. According to the paper, two independent proof checkers accepted it: the Lean kernel and nanoda. Models wrote the code, and other model instances checked it. At publication, the authors knew of no human review of the code.
What remains is to check whether the formal statements accurately capture the intended theorem and refutation. The programs check whether the encoded conclusion follows from the encoded premises. A human must assess whether those statements express the intended mathematical claim. Anthropic's announcement should therefore be read as a claimed refutation with formal verification whose mathematical meaning still needs human review.
Open the related Eternal Search page
Sources
[1] hexagonmath.org
[2] x.com
[3] github.com
[4] openai.com
[5] t.me
[6] github.com
The item gives readers a specific research claim through which to examine Anthropic's public Eternal Search page, while separating formal proof checking from human validation of the theorem's meaning.