OpenAI announced three results on Oct. 26 and, in its announcement, says its models proved the Exponential Time Hypothesis false. These are the company's claims. The post names outside experts who will examine two of them, and we found no outside verdict on any yet.
What the Exponential Time Hypothesis is
Satisfiability asks whether the true/false settings of a set of variables can make a list of logical conditions all hold at once. For a formula with many variables, the best known methods slow down at a rate that grows exponentially as variables are added.
The hypothesis says that for the standard version of the problem, 3-SAT, no algorithm can solve it in sub-exponential time, meaning the worst-case running time keeps growing exponentially with the problem size. The announcement says the hypothesis has been widely believed and used in hundreds of papers to show that other problems are hard too.
What OpenAI claims, and what is formalized
OpenAI's manuscript describes an algorithm that counts the satisfying settings of such formulas in less than exponential time, using modest memory. The post says the proof was checked in Lean, software that verifies proofs line by line.
The formalization notes say Lean covers the subexponential counting result, with a slightly looser time bound than the manuscript's sharper one. OpenAI's post says the system found the argument on Oct. 16 and the Lean version followed the next day.
Who is checking it
The post says a group led by Russell Impagliazzo and Ramamohan Paturi of UC San Diego and Ryan Williams of MIT will verify and explain the work. Impagliazzo and Paturi, with Francis Zane, proposed the hypothesis, the post says. The repository's history file says the group asked for the materials to be released immediately.
The post says members take part independently, are unpaid, and do not speak for OpenAI. OpenAI also says it will fund a conference on the implications.
What outside experts have said so far
We could not open a statement from Williams, Impagliazzo or Paturi on a page of their own, so we cannot say what they have concluded. Scott Aaronson wrote on his blog this evening that his students had told him an OpenAI model refuted the hypothesis with a roughly exp(n/√log n) algorithm for 3-SAT. That relays the claim rather than reporting a check.
The other two results
On the math side, the post says its models proved Sogge's local smoothing conjecture, a statement that the strongest focusing of waves is short-lived, in every dimension. That would also settle the Kakeya conjecture, a question about how small a set can be if it holds a line pointing in every direction. The post names no outside group for it. It says the proof output and a Lean version are public, the same approach as the Oct. 6 release.
The physics claim is a rigorous existence proof for certain four-dimensional quantum field theories, including quantum chromodynamics and pure Yang-Mills theory, which is part of a Clay Millennium Prize problem. A group led by Nobel laureate David Gross will examine it and has chosen not to release the AI-produced materials yet, so nothing public can be checked.
What this means for you
Nothing you use changes today. OpenAI's own post says finding faster algorithms will require significant further research. Treat "false" as a claim under review until the named group reports.
Our earlier report on the Simons Foundation fund for checking AI math covers the $5 million OpenAI ties to this effort, and the mathematicians' objections to its first release. For the wider context of how far OpenAI's models are being trusted on hard problems, see our report on its agents disabling their own safety monitoring.
What we could not check
We could not open the Lean files or run the proofs, and we did not evaluate the mathematics ourselves. The physics materials are not public.
