OpenAI says its AI disproved the Exponential Time Hypothesis for 3-SAT
The proof and Lean code are public. ETH's own co-creators will vet the claim and say their involvement isn't an endorsement.
OpenAI said Monday (Oct. 26) that one of its internal models has refuted the Exponential Time Hypothesis, a conjecture from 1999 about how hard it is to solve Boolean satisfiability problems such as 3-SAT.
The company's announcement bundled the claim with two others: a proof of a major conjecture in harmonic analysis and an existence proof for quantum chromodynamics. But the computer science result is the one that reaches into textbooks, and into a lot of published papers.
ETH "has been widely believed to be true, and has been used in hundreds of papers to derive conditional computational hardness results," OpenAI wrote, across graph theory, computational biology, databases and computational geometry. "Surprisingly, our system has recently proved that the ETH is false, a result that was subsequently verified in Lean," a language that checks proofs by machine.
The hypothesis, proposed by Russell Impagliazzo and Ramamohan Paturi with Francis Zane, says 3-SAT can't be solved in subexponential time: the work must grow exponentially with the number of variables. The fastest previously known general 3-SAT algorithm runs in about 1.307n time, according to a preprint the new paper cites.
OpenAI's 67-page paper, credited only to "OpenAI," describes a deterministic algorithm that exactly counts the satisfying assignments of any k-CNF formula using polynomial space. Its running time is about 2 raised to n divided by the square root of log n. That's still superpolynomial, but it grows more slowly than any 2cn bound, which is what ETH ruled out.
The paper says the same algorithm also refutes the Strong Exponential Time Hypothesis (SETH) and two related variants, Gap-ETH and NSETH.
Complexity theorist Scott Aaronson summed it up on his blog: "my students just came to my office to tell me that an OpenAI model has now refuted the Exponential Time Hypothesis, by giving an algorithm to solve 3SAT in an amount of time that scales roughly like exp(n/√log(n))."
The people who proposed ETH will check it
According to OpenAI, its model found the disproof on Oct. 16, and the company formalized it in Lean the next day. It has posted the model's write-up and the Lean proof on GitHub.
Impagliazzo and Paturi, both at UC San Diego, will lead an independent review with MIT's Ryan Williams. "An internal model at OpenAI has produced a claimed refutation of ETH!" Williams wrote on Bluesky, adding that the three "signed no NDAs and will receive no compensation."
The group asked OpenAI to release all of its raw data on the result and to sponsor a conference for the research community, and OpenAI agreed to both, Williams and OpenAI said.
In an open letter, the three researchers stressed that their role isn't an endorsement. "Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny," they wrote, as quoted by The Next Web. "If the claim is correct, it will change an important part of theoretical computer science."
If it holds, the result does not mean P equals NP. The paper itself says it "does not imply that general NP problems admit subexponential time algorithms." It also doesn't hand anyone a faster SAT solver yet. OpenAI said turning the theory into practical improvements "will require significant further research."
What it does shake is a large body of conditional results. SETH has been a common basis for arguing that problems developers know well, like edit distance, longest common subsequence and regular-expression matching, can't be solved much faster than quadratic time.
The paper says its result "removes one basis for the hardness claims," though some of those bounds also follow from weaker conjectures that may still hold, such as the Orthogonal Vectors Conjecture.
OpenAI's other two claims are just as large. Its models proved Christopher Sogge's 1991 local smoothing conjecture in every dimension, the company said, which would also settle the Kakeya conjecture and Stein's restriction conjecture in all dimensions. Mathematicians had proved local smoothing in two dimensions in 2019 and Kakeya in three dimensions in 2025.
In physics, OpenAI says its models produced a rigorous existence proof for certain four-dimensional quantum field theories, including quantum chromodynamics. That work includes the existence of pure Yang–Mills theory, which OpenAI described as part of a Clay Mathematics Institute Millennium Prize problem. The Clay problem also requires proving a mass gap, which OpenAI's post doesn't claim.
A group led by Nobel laureate David Gross is reviewing the physics work and has chosen not to release the AI's material yet.
The announcement comes less than a month after OpenAI's Oct. 6 release of hundreds of AI-generated math manuscripts. This time, OpenAI asked outside experts to act as "shepherds." It said it doesn't "seek academic credit for the discoveries produced by our internal models."
Not everyone likes the shepherd model. The AGMAI panel of math advisers that OpenAI assembled had said on Sunday that "we recommend that AI companies do not adopt" the practice of picking certain people to see results first, The Verge reported.
For now, the ETH proof is out in the open, and two of the people checking it for holes are the ones who proposed the hypothesis in the first place.
