OpenAI says AI refuted Exponential Time Hypothesis

OpenAI announces three AI results in math, CS and physics

OpenAI's announcement covers three results its internal models produced: one each in harmonic analysis, complexity theory and quantum field theory. None has been peer reviewed. OpenAI calls the AI-written manuscripts "a form of raw research data" and has asked outside experts to help turn them into results other researchers can trust.

Math and CS outputs are public; physics is up to experts

OpenAI released the AI output for the math and computer science results, and left the physics release to an outside group. The experts OpenAI asked to "shepherd" the results recommended a different approach for each field:

• Math: publish the AI output and let researchers organize their own efforts to explain it
• Computer science: form an outside group to explain the result, and publish the AI output so anyone can examine it
• Physics: form an outside group and let it decide what to release

The computer science group chose to publish the natural-language proof and the Lean formalization right away, and OpenAI put both on GitHub. Lean is a programming language that checks every step of a mathematical proof by machine; formalization means rewriting a human proof so Lean can check it.

The physics group went the other way. It is holding back the AI-produced material and writing up the result itself. OpenAI says it doesn't yet know which of the three approaches will work best.

OpenAI says it won't seek academic credit

OpenAI says it won't take academic credit for what its models found, and it set four principles for the outside groups. The groups, not OpenAI, get credit for the explanations they write.

OpenAI also concedes a weakness in the setup. Choosing the first shepherds decides who gets in early, and that "creates asymmetry of information," in OpenAI's words. Separately, OpenAI has committed $5 million to a new Simons Foundation initiative that will fund workshops, conferences and programs for researchers studying AI-produced results.

What the Exponential Time Hypothesis says

The Exponential Time Hypothesis (ETH) says some logic problems can't be solved without exponential time, however clever the algorithm. OpenAI's preprint claims it is false.

Hundreds of hardness results assume ETH

Most complexity theorists believe ETH, and OpenAI says hundreds of papers use it to argue that certain problems can't be solved quickly. ETH is about SAT, which asks whether a formula's variables can be set to true or false so the whole formula comes out true. 3-SAT is the version where each clause has at most three variables. In its standard form, ETH says 3-SAT on n variables takes exponential time in the worst case, so, roughly, each extra variable multiplies the running time by a constant factor.

Russell Impagliazzo, Ramamohan Paturi and Francis Zane first proposed it. Researchers in graph theory, computational biology, databases and computational geometry have proved results of the form "this problem is hard, assuming ETH." If ETH is false, those conditional results no longer show the problems are hard.

The preprint counts SAT solutions in subexponential time

OpenAI's preprint describes a deterministic algorithm that counts every satisfying assignment of a k-CNF formula in subexponential time. Subexponential time grows more slowly than any exponential function. The bound claimed here still grows faster than any polynomial, and the algorithm needs only a polynomial amount of memory.

Counting is at least as hard as deciding: if the count is above zero, the formula is satisfiable. So an algorithm that counts 3-SAT solutions in subexponential time also decides 3-SAT in subexponential time, which is exactly what ETH rules out.

The preprint, titled "The Exponential Time Hypothesis is False" and credited to OpenAI, is dated October 17, 2026, and was revised on October 25. It also claims subexponential algorithms for counting graph colorings and perfect matchings.

The ETH disproof isn't confirmed yet

No one outside OpenAI has confirmed the ETH refutation yet. According to OpenAI, its AI found a natural-language disproof on October 16, 2026, and OpenAI formalized it in Lean the next day. Two of the three researchers checking it, Impagliazzo and Paturi, also co-proposed ETH.

Lean checked a weaker bound than the main theorem

The Lean proof covers a weaker running-time bound than the preprint's main theorem. OpenAI's note on the scope of the formalization says Lean proves a running time of 2 raised to n(log log n)²/√log n, while the October 25 manuscript claims the sharper 2 raised to n log log n/√log n. Both are subexponential, which is why OpenAI says the ETH refutation itself was verified in Lean.

The sharper main theorem has not been machine-checked. Whether it holds is for the review group and other experts to judge by reading the paper.

Anthropic published its own ETH refutation

Anthropic has published a separate refutation of ETH, found by an internal research Claude model, with a paper and a Lean 4 formalization. It sits in the eth folder of Anthropic's formal-math repository on GitHub, and the README says the algorithm solves 3-SAT in 2^o(n) time (time that grows more slowly than any exponential).

The same README is blunt about what the machine check does not cover. Lean verifies the proofs, but no machine checks that the formal statement says what the paper says, so a person still has to compare the two.

Real-world SAT solving isn't affected yet

Even if ETH is false, practical SAT solvers won't get faster any time soon. Anthropic's README says its result "is purely asymptotic and says nothing about solving formulas in practice." OpenAI writes that turning the theory into practical gains "will require significant further research."

OpenAI's preprint also says the result does not mean general NP problems have subexponential algorithms, so P vs. NP is untouched. OpenAI has pulled AI-generated work before: on October 7, it withdrew three math preprints after a sign error surfaced, a day after posting them (OpenAI math papers withdrawn over one sign error).

OpenAI also claims Kakeya and Yang–Mills results

OpenAI announced a math result and a physics result on the same day as the ETH claim, and both are claims awaiting expert review. The math claim would settle the Kakeya conjecture in every dimension. The physics claim is about whether the theory of the strong nuclear force exists in a rigorous mathematical sense.

Local smoothing proved in every dimension

According to OpenAI, its models produced a proof of Christopher Sogge's 1991 local smoothing conjecture that works in any number of dimensions. Roughly, the conjecture says focused waves can't stay at their most concentrated for long. A correct proof would also resolve the Kakeya conjecture and Stein's restriction conjecture in every dimension.

Until now, only low-dimensional cases had been proved. The 2D case of local smoothing fell to Guth, Wang and Zhang in 2019, and Wang and Zahl settled 3D Kakeya in 2025.

OpenAI got the AI output on October 18, 2026, and had it formalized in Lean the following day. On an expert's advice, it released the output as is, the same way it handled its October 6 batch of math manuscripts.

The physics group is holding back the AI output

On the physics side, OpenAI says its models proved that certain interacting quantum field theories in four dimensions, QCD among them, exist in a mathematically rigorous sense. QCD (quantum chromodynamics) describes the strong force that binds quarks and gluons. Part of the claim is that pure Yang–Mills theory exists, which is one piece of a Clay Mathematics Institute Millennium Prize problem.

According to OpenAI, its models produced the Yang–Mills existence proof on September 9 and the QCD proof on September 18. Because the work is long and complex, OpenAI held off on announcing it until the Lean formalization of Yang–Mills existence finished on October 16.

David Gross, who shared the 2004 Nobel Prize in Physics, leads the group shepherding the physics result, with Michael Douglas, Arthur Jaffe, Igor Klebanov and Nikita Nekrasov. Unlike the math and computer science results, the physics AI output is not being released for now.

What OpenAI's ETH claim means for now

A Lean check doesn't settle the ETH claim; the review group's reading of the paper will. Lean verified a weaker bound than the paper's main theorem, and no machine checks that a formal statement matches the paper it comes from. Because OpenAI and Anthropic each published a refutation, reviewers have two separate write-ups to compare.

Access also differs by field. Anyone can read the AI output for the math and computer science results today. The physics result has a finished Lean formalization of Yang–Mills existence, but outsiders won't see the material until David Gross's group publishes its own write-up.