Anthropic Publishes a Claude ETH Refutation Claim. It Is Not P = NP.

The Anthropic ETH story is not a mistaken attribution of OpenAI’s announcement. The specified commit of Anthropic’s formal-math repository contains a 49-page paper titled “A 2^o(n) Time Algorithm for 3-SAT,” attributed to Claude and Anthropic, alongside Lean statements and proof entry points.

That establishes that a substantive Anthropic research artifact exists. It does not establish that Developer312 independently verified the result. The claim is a refutation of the Exponential Time Hypothesis, not a solution to P versus NP and not a working attack on deployed cryptography.

What ETH says

A 3-SAT formula consists of Boolean variables and clauses containing at most three literals. The decision problem asks whether some assignment satisfies every clause. Checking a proposed assignment is easy; finding one in the worst case is the hard part.

The Exponential Time Hypothesis says, roughly, that solving arbitrary instances requires an exponential dependence on the number of variables: there is some positive constant in the exponent that no general algorithm can beat away entirely. Improving one exponential base to a smaller constant base does not refute it.

Anthropic’s paper claims something stronger: a deterministic subexponential algorithm. Its main result counts the satisfying assignments, rather than merely deciding whether at least one exists. For fixed clause width, the stated variable-based runtime is 2 raised to O(n log log n / sqrt(log n)). The coefficient of n in that exponent tends toward zero as n grows.

That remains different from polynomial time. A runtime can be subexponential yet vastly larger than any polynomial. The paper explicitly says its result does not bear directly on P versus NP.

The actual algorithmic claim

The October 26 paper gives a more general counting bound for k-CNF formulas, expressed using both the number of variables and the number of clauses. Its formulas treat the input as a set of clauses, without duplicate clauses. Its strongest variable-based formulation concerns variables that actually occur.

Those details are not decorative. A runtime stated only in the number of variables needs a clear input convention: arbitrarily many duplicated clauses would otherwise make even reading the input incompatible with the stated bound. The repository’s formal statement explains the encoding and restrictions explicitly.

The proof overview routes counting through sums of products and tensor networks. It describes a decomposition of a crossing into a signed sum of pieces, allowing different contraction orders for different terms. The authors emphasize that this escapes a more restricted single-contraction-tree model. That is the proposed mechanism behind the improvement, not a claim that a language model simply guessed answers to SAT instances faster.

The paper says practical speedups are absent

Anthropic’s README is unusually direct: the result is purely asymptotic and says nothing about solving formulas in practice. The paper likewise states that its bounds do not yield practical algorithms for NP-complete problems.

This is not an outside critic adding a pessimistic interpretation. It is a limit declared by the authors of the claimed breakthrough. The useful implication, if validated, is that a foundational hardness hypothesis would fail and research built conditionally on it would need reassessment.

A failed hypothesis also does not make every theorem that mentioned it simply false. A statement proved under ETH remains a conditional implication; what changes is whether that premise describes the computational world. Nor does one refutation automatically settle every distinct hypothesis in fine-grained complexity. The paper specifically says its result does not refute the Orthogonal Vectors hypothesis.

What we found in the Lean materials

The main statement file defines the claims using Mathlib’s deterministic multi-stack Turing machines with finite alphabets. It spells out input encodings, step counts, the meaning of ETH, and the counting theorem.

The separate Solution file supplies theorem bodies through imported developments. A Challenge file contains two sorry placeholders, but it is explicitly a target specification and is not imported by the solution. Those placeholders alone are not evidence that the claimed proof is incomplete.

The README provides build and axiom-reporting commands, pins Lean and Mathlib to version 4.33.1, and describes a fuller Comparator check that rechecks proofs with the independently written nanoda kernel. These are reproducibility instructions and claimed expected outputs, not checks Developer312 performed.

The same README states a crucial limitation: no machine checks that the readable statement file means what the paper says. Human review must bridge that semantic boundary. The proof index also documents differences between the printed argument and formal proof, including cost models and intermediate steps. Formalization is evidence worth examining, not a reason to stop examining.

Anthropic and OpenAI are distinct claims

The paper says an internal Claude research model found the core algorithm on October 16, using 14 million output tokens with no human input at that stage. It then says Anthropic researchers worked with Claude to improve the presentation. Both provenance assertions are the authors’ account, not independently reconstructed logs.

It also explicitly acknowledges a similar result claimed independently and concurrently by an internal OpenAI model. OpenAI’s own announcement dates its ETH natural-language output to October 16 and formalization to October 17, and names an academic group to examine its work.

Those matching dates do not establish identical algorithms, shared discovery, or independent confirmation of one proof by the other. Comparing the results requires examining both constructions, not counting two company announcements as replication.

What deserves attention next

For researchers, the next tasks are precise: reproduce the pinned build, inspect axiom dependencies and comparator checks, verify that formal statements capture the intended theorem, and explain the algorithm’s implications for conditional lower bounds.

For builders, there is no basis here to replace a production SAT solver or declare encryption obsolete. The signal is a concrete, inspectable research claim with a substantial proof package and explicit limits. That is stronger than a screenshot, and still different from independent scientific acceptance.

AI assistance disclosure: This draft was researched and written with a GPT-class language model. Human editorial review is pending.