OpenAI says its AI disproved the Exponential Time Hypothesis

AI research illustration: a microscope over a red sample beside node diagrams

On October 26, OpenAI announced three research results produced by its AI models, spanning theoretical computer science, harmonic analysis and mathematical physics. The most significant is a proof that the Exponential Time Hypothesis (ETH) is false. The company did not say which model was used, referring only to "OpenAI's AI models," and noted that all three results still need further independent confirmation from the academic community.

ETH: the foundation under hundreds of papers

The Exponential Time Hypothesis concerns how hard it is to solve the Boolean satisfiability problem (3-SAT). Roughly speaking, it asserts that such problems cannot be solved in subexponential time. It is stronger than "P does not equal NP" and also more practical to use, and for decades it has served as a default assumption: hundreds of papers in graph theory, computational biology, databases and computational geometry derive their lower bounds from it.

According to the timeline OpenAI published, the model generated a natural-language proof on October 16 and a Lean formalization was completed the next day. The collaborators were Russell Impagliazzo and Ramamohan Paturi of the University of California, San Diego, and Ryan Williams of the Massachusetts Institute of Technology. The first two are among the people who originally proposed ETH.

As disclosed, the scholars put two conditions to OpenAI: release all the raw data, and fund an academic conference devoted to discussing what the result means for computer science. OpenAI agreed to both. If the proof holds up, every paper that takes ETH as its premise will have to be reassessed one by one, to see which conclusions merely lose their conditions and which can be rescued under a different assumption. That is no small undertaking.

The Kakeya conjecture: a line of work familiar to Chinese mathematicians

The second result proves the local smoothing conjecture in all dimensions, and from it derives the Kakeya conjecture and the Stein restriction conjecture in all dimensions. The key ingredient is an auxiliary partial differential equation constructed by the model. OpenAI says it obtained the proof on October 18 and finished the Lean formalization the following day; both the natural-language version and the Lean files have been posted on GitHub.

This line of research is well known among Chinese-speaking readers. The local smoothing conjecture was posed by Christopher Sogge in 1991. In 2019, Larry Guth, Hong Wang and Ruixiang Zhang proved the two-dimensional case, and in 2025 Hong Wang and Joshua Zahl proved the Kakeya conjecture in three dimensions, which was seen at the time as one of the most important advances in harmonic analysis in years. Going from three dimensions to all dimensions is an enormous leap, and no public assessment from outside mathematicians is available yet.

Yang–Mills: read by experts only

The third result is in mathematical physics. The work proves, in the rigorous mathematical sense, that certain interacting quantum field theories in four dimensions containing both gauge fields and fermions do exist, a class that includes quantum chromodynamics, and along the way settles a sub-problem of the existence of pure Yang–Mills theory. The existence and mass gap of pure Yang–Mills theory is one of the Clay Mathematics Institute's Millennium Prize Problems.

The method follows Tadeusz Balaban's constructive quantum field theory program. Because the Standard Model cannot be extrapolated directly to arbitrarily short distance scales, the proof targets the simplest grand unified theory containing the Standard Model's gauge fields and fermions. The review was led by Nobel laureate David Gross, with Michael Douglas, Arthur Jaffe, Igor Klebanov and Nikita Nekrasov taking part. This result has not been formally verified.

From May to October

Strung together, OpenAI's math announcements this year show both a faster pace and a shifting target. In May it was an 80-year-old Erdős problem. In September it was the smoothness problem for the Navier–Stokes equations, which also came with Lean files, but no mathematician had completed an independent check at the time. This time the target is a computational-complexity hypothesis that a great deal of downstream work depends on, and for the first time the people who proposed the hypothesis were brought onto the collaborator list.

The verification approaches also diverge: the two mathematics results come with machine-checkable Lean proofs, while the physics result can only rely on human review. Lean can guarantee that the derivation has no gaps, provided the statement of the claim was not distorted during formalization. That point can only be confirmed once independent teams have read the files line by line.

Sources: OpenAI research announcement, CocoLoop, ITHome; the publicly posted Lean formalization files on GitHub were checked for the proof targets and verification methods.