OpenAI claims proofs that disprove a complexity conjecture

OpenAI says its models have produced three proofs, and one of them disproves a conjecture that hundreds of papers use to derive hardness results. The claims span mathematics, computer science and physics. OpenAI's announcement is dated 26 October, according to Unite.ai.

The computer science claim concerns the Exponential Time Hypothesis (ETH). OpenAI says its system disproved it. The natural-language disproof was produced on 16 October and formalised in Lean on 17 October. The formalisation documentation states the result for fixed k ≥ 2: a deterministic machine counts satisfying assignments of a k-CNF formula in subexponential time and polynomial space.

In mathematics, OpenAI says its models proved the local smoothing conjecture in every dimension. According to the company, that also resolves the Kakeya conjecture and Stein's restriction conjecture in all dimensions. The output was obtained on 18 October, formalised in Lean the next day, and published on GitHub with a natural-language writeup.

In physics, OpenAI says its models give a rigorous existence proof for certain four-dimensional interacting quantum field theories with gauge fields and fermions, including QCD and a unified completion of the Standard Model. It also reports a proof of pure Yang–Mills existence, part of a Clay Millennium Prize problem. The Yang–Mills proof is dated 9 September, QCD 18 September, and the Lean formalisation was finished on 16 October. The physics group, led by David Gross, decided to write up the result itself. The physics release has been delayed, while the maths and computer science proofs are already public.

A group led by Russell Impagliazzo and Ramamohan Paturi of UC San Diego will verify and shepherd the ETH work. None of the claims has been independently verified yet.

Researchers whose hardness results depend on ETH are the most exposed. If the disproof holds, those results rest on an assumption that OpenAI says no longer stands, and the UC San Diego group's check will show how far that reaches. The conjecture's reach across the literature makes this a question for the whole complexity theory field, not one lab.

For the market, the story is about verification rather than the announcement. Watch whether the UC San Diego group confirms the ETH work, whether the maths results hold up under independent review, and when the physics write-up arrives, since that release is already delayed.