OpenAI and Anthropic both say they disproved the Exponential Time Hypothesis

OpenAI announced three new results in three fields

In a post published October 26, OpenAI said its internal models had produced new results in harmonic analysis, complexity theory and quantum field theory. OpenAI researcher Dan Roberts shared the announcement on X. None of the results has been peer reviewed yet. The company says it treats the manuscripts as “raw research data” and has asked outside experts to act as shepherds for each field.

Each field got its own release path. The math result went straight to GitHub, and the computer science proof was made public alongside an external working group. The physics group will decide when its material comes out.

Dan Roberts@danintheory

We are announcing three new discoveries in mathematics, computer science, and physics about harmonic analysis, complexity theory, and quantum field theory.

openai.com/index/building…

What the Exponential Time Hypothesis says

3-SAT asks whether some assignment of variables satisfies every clause in a formula, where each clause has at most three terms. Brute force tries all 2 to the power n assignments for n variables. The hypothesis, proposed by Russell Impagliazzo and Ramamohan Paturi, holds that 3-SAT truly requires exponential time. According to Anthropic’s paper, the best deterministic algorithm so far ran in time on the order of 1.328 to the power n.

The hypothesis is stronger than the widely held assumption behind P vs. NP, and OpenAI says hundreds of papers in fields from graph theory to databases use it. A literature search that Anthropic had Claude run found more than 800 papers with at least one result that relies only on this hypothesis or on an assumption that implies it.

Two companies, two separate proofs

OpenAI’s algorithm is deterministic, counts the exact number of satisfying assignments of k-CNF formulas and runs in subexponential time. The paper reduces that counting task to counting the common zeros of sparse polynomial equations. The company says the model found the proof on October 16 and it was formalized in Lean the next day.

Hours after OpenAI’s announcement, Anthropic posted “A 2^o(n) Time Algorithm for 3-SAT” and its Lean 4 proof on GitHub. The paper says an internal Claude research model found the core algorithm on October 16 with 14 million output tokens and no human input, and Anthropic researchers then worked with Claude on the presentation. Its method relies on contracting tensor networks and on rank bounds. The paper notes that an OpenAI model independently and concurrently claims a similar result.

Anthropic’s repository says the Lean proof uses only Lean’s three standard axioms and is rechecked by a second, independent kernel. It also notes that no machine checks whether the theorem statement says what the paper says.

No faster solving in practice

Anthropic calls the result “purely asymptotic.” Its paper says any advantage over brute force would appear only at astronomically large numbers of variables, while brute force is already impractical at 100. It adds that the result does not bear directly on P vs. NP.

According to TechCrunch, MIT’s Ryan Williams first asked OpenAI whether any cryptographic systems were affected; OpenAI checked and was reasonably confident none were. Williams said some parts of the proof are fairly routine, but “there are two or three alien-looking parts,” and that OpenAI’s algorithm can’t be the best possible.

Independent review and objections

The group reviewing OpenAI’s result is led by Impagliazzo and Paturi of UC San Diego and Williams of MIT. Impagliazzo and Paturi, along with Francis Zane, first proposed the hypothesis. The group asked OpenAI to release all raw data and to fund a conference on the result’s implications, and OpenAI agreed to both. In an open letter quoted by The Next Web, the group wrote that its involvement should not be taken as certification of the claim.

Williams had earlier criticized OpenAI’s release of hundreds of math papers in early October. He called it a “DDOS attack on mathematicians.” TechCrunch also reports that Anthropic mathematician Levent Alpöge suggested OpenAI was basing its solutions on pre-existing work.

The Kakeya and Yang-Mills claims

The math result claims to prove the local smoothing conjecture, proposed by Christopher Sogge in 1991, in every dimension. The conjecture says that the most extreme focusing of waves must be short-lived. OpenAI says this also resolves the Kakeya conjecture and Stein’s restriction conjecture in all dimensions. Local smoothing was proved in two dimensions in 2019, and Hong Wang and Joshua Zahl proved Kakeya in three dimensions in 2025. OpenAI got the output on October 18 and formalized it in Lean the next day.

The physics result claims to prove that quantum chromodynamics and pure Yang-Mills theory exist as rigorous mathematical theories in four dimensions. That covers only the existence part of one of the Clay Mathematics Institute’s $1 million Millennium Prize Problems; according to Scientific American, the mass gap part remains open. A group led by Nobel laureate David Gross will write its own account before the material is released. According to Scientific American, the Advisory Group on Mathematics and Artificial Intelligence (AGMAI) sees no scientific reason for delay and wants the proof released.