# OpenAI and Anthropic Claim to Refute ETH

- Date: 27 Oct 2026 (2026-10-27T17:06:32.000Z)
- Summary: OpenAI and Anthropic have published AI-generated ETH-refutation claims with formal proof artifacts. Researchers stress that proof checking, faithful mathematical statements, and independent community understanding remain distinct requirements.
- Tags: `digest`, `ai-discourse`, `openai`, `anthropic`, `ai-research`, `exponential-time-hypothesis`, `formal-verification`

## Sources

1. [Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams - Message to the TCS Community on ETH](https://docs.google.com/document/d/1adB0IhJgLzsmbfCgoLrtoJTjnlPf74UnyjMo35P5JHo/edit?tab=t.0) (website)
2. [The Next Web - OpenAI says its AI model has disproved the Exponential Time Hypothesis](https://thenextweb.com/news/openai-exponential-time-hypothesis-false-kakeya-yang-mills) (website)
3. [OpenAI - The Exponential Time Hypothesis is False — Lean formalization scope](https://github.com/openai/math/blob/main/lean/docs/378.md) (website)
4. [Anthropic - A 2^o(n) Time Algorithm for 3-SAT](https://github.com/anthropics/formal-math/tree/main/eth) (paper)

## Executive Summary

A foundational assumption about computational difficulty now faces AI-generated refutation claims from two major labs. The consequential development is the publication of arguments and formal proof artifacts that researchers can examine—not an established verdict that a decades-old conjecture has fallen.

OpenAI’s claim has prompted an open examination organized by Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams. Anthropic has also published an ETH-refutation manuscript and Lean formalization, added to its repository on October 27. The researchers’ [message to the theoretical computer science community](https://docs.google.com/document/d/1adB0IhJgLzsmbfCgoLrtoJTjnlPf74UnyjMo35P5JHo/edit?tab=t.0) states the essential qualification: their involvement “should not be taken as certification of the claim.”

## What Happened

OpenAI’s October 26 announcement includes a claimed disproof of the Exponential Time Hypothesis, according to [The Next Web’s account](https://thenextweb.com/news/openai-exponential-time-hypothesis-false-kakeya-yang-mills). ETH concerns whether 3-SAT—a central Boolean satisfiability problem—requires exponential time in the number of variables in the worst case. It underpins many conditional arguments about the limits of efficient algorithms.

The substantive public artifact is more specific than a breakthrough headline. [OpenAI’s formalization description](https://github.com/openai/math/blob/main/lean/docs/378.md) says Lean proves that a deterministic machine can exactly count satisfying assignments for fixed-width Boolean formulas in subexponential time and polynomial space. It also distinguishes the formalized time bound from a sharper bound in the October 25 manuscript. That distinction matters: the scope of a checked statement should not be silently expanded to cover every claim in an accompanying paper.

[Anthropic’s release](https://github.com/anthropics/formal-math/tree/main/eth) attributes its result to an internal research Claude model. It publishes a paper, Lean 4 formalization, theorem statements, and checking instructions. Its claimed algorithm also counts satisfying assignments, rather than merely deciding whether one exists. The repository explicitly says the result is “purely asymptotic” and says nothing about solving formulas in practice.

These are separate published claims. The available material does not establish independent discovery, and neither release should be treated here as an independently validated theorem.

## Why Proof Checking Is Not the Whole Review

Anthropic’s documentation makes a particularly useful boundary explicit: Lean checks proofs, but no machine checks that the theorem-statement file says what the paper says. Readers must inspect that correspondence. The release also describes checks comparing formal statements and rechecking proofs with a second, independently written kernel.

Those are meaningful verification mechanisms, not reasons to dismiss formal methods. But they answer different questions. Does the proof establish the encoded proposition? Does that proposition faithfully express the advertised mathematical result? Can other researchers reconstruct the argument and understand its consequences?

The community letter insists on that broader standard: understanding that others can “reconstruct, question, and build upon.” It invites independent criticism, explanations, simplified proofs, and shared records of gaps and corrections. Organizing that work is not equivalent to endorsing its conclusion.

Nor would a valid ETH refutation by itself settle P versus NP. Subexponential algorithms need not be polynomial-time algorithms, and an asymptotic improvement need not produce a useful practical solver. Claims about immediate cryptographic collapse or sweeping optimization gains run ahead of the evidence presented here.

## The Bigger Story

The researchers’ letter also identifies a problem that capability headlines obscure: who receives credit when generating a candidate result becomes easier than checking and explaining it? Early access can advantage selected researchers; recognition can concentrate around first publication and powerful tools while undervaluing correction, simplification, and teaching.

This sharpens the recurring distinction between model capability and dependable work. In research, a formally checkable output is an important artifact, but shared understanding remains a separate achievement. The next consequential development is whether open examination establishes the claims, clarifies their exact scope, and produces explanations other researchers can use—not another declaration that AI has “solved” a field.