Last updated: November 5, 2026
OpenAI said on October 26, 2026 that an internal model produced a proof that the Exponential Time Hypothesis (ETH) is false, using a deterministic subexponential algorithm for counting k-SAT solutions, with a Lean proof published on GitHub. The claim has not yet been independently verified, and the experts involved said their involvement “should not be taken as certification of the claim.”
OpenAI said on October 26 that one of its internal models produced three new research results. The one getting the most attention is a claimed proof that the Exponential Time Hypothesis (ETH), a decades-old assumption in theoretical computer science, is false. The other two are a proof of the local smoothing conjecture in every dimension, which would also settle the Kakeya conjecture, and a rigorous existence proof for quantum chromodynamics (QCD) that includes pure Yang–Mills theory.
The ETH paper and Lean proof are public on GitHub. By Tuesday morning the OpenAI announcement was the top story on Hacker News, with the paper itself right below it. Here’s what is actually claimed, what has been checked, and what hasn’t.
What OpenAI is claiming
ETH says, roughly, that 3-SAT (deciding whether a Boolean formula with three-variable clauses can be satisfied) can’t be solved meaningfully faster than exponential time. OpenAI says ETH has been used in hundreds of papers to prove conditional hardness results in graph theory, computational biology, databases and computational geometry.
The paper, dated October 17 and revised October 25, goes further than deciding satisfiability. It claims a deterministic algorithm that exactly counts the satisfying assignments of k-CNF formulas for any fixed k, using polynomial space and time of roughly 2n/(log n)1/2+o(1). That is subexponential. The paper says the same result also refutes the Strong ETH (SETH), Gap-ETH, NSETH and the counting version, #ETH.
According to OpenAI, the model found the disproof on October 16, and the company formalized it in Lean on October 17. A group led by Russell Impagliazzo and Ramamohan Paturi of UC San Diego and Ryan Williams of MIT will verify and explain the result. Impagliazzo and Paturi proposed ETH in the first place, together with Francis Zane.
The experts are not endorsing it (yet)
That group has been careful. In an open letter quoted by The Next Web, the three wrote: “Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny.” They also wrote: “If the claim is correct, it will change an important part of theoretical computer science.” Williams called it “a claimed refutation” in his own post.
OpenAI says the group signed no NDAs and is unpaid, and that OpenAI agreed to the group’s requests to make all raw data public and to fund a conference on what the work means for the field.
My take: “claimed” is the right word here, and anyone writing “AI proves ETH false” as settled fact is ahead of the evidence.
Why it matters, and what it doesn’t mean
It is not P = NP. A subexponential algorithm is still superpolynomial. 2n/√log n grows far faster than any polynomial, so the P versus NP question is untouched.
It is not a practical speedup yet. The savings sit in a √log n term in the exponent, and log n grows very slowly. OpenAI itself says turning this into practical improvements “will require significant further research.” Don’t expect your SAT solver to change next week.
It does shake up a lot of theory. Many fine-grained lower bounds, including SETH-based limits for problems like edit distance, rest on these hypotheses. The paper notes that some of those bounds still follow from weaker assumptions, such as the Orthogonal Vectors Conjecture, so not everything falls at once. Sorting out which results survive will take months.
What “verified in Lean” does and doesn’t tell you
Lean is a proof assistant: if Lean accepts a proof, a machine has checked every step. That is a big deal, but it only proves the statement that was actually typed into Lean. Bill Gasarch made this point on the Computational Complexity blog after OpenAI’s earlier release: the risk is not bugs in Lean, it’s that coding a theorem into Lean may be done incorrectly, so Lean could end up verifying something other than what you meant.
There is already a visible gap. OpenAI’s own Lean notes for the ETH result say the formal proof establishes a slightly weaker time bound than the paper’s headline, with a (log log n)2 factor. That bound is still subexponential and would still refute ETH, but it shows why experts need to read the formal statement line by line and confirm that it matches the English claim.
OpenAI also has a track record to keep in mind. On October 7 it withdrew three papers over a sign error and revised 14 others from its earlier batch of 722 manuscripts. Lance Fortnow’s rule from the same blog applies here: he reads a new proof assuming it is wrong until he’s convinced otherwise.
The other two results
In math, OpenAI says its models proved Sogge’s 1991 local smoothing conjecture in every dimension, which would also resolve the Kakeya and Stein restriction conjectures. The write-up and a Lean proof are public.
In physics, OpenAI says it formalized the Yang–Mills existence proof in Lean on October 16. But the expert group led by Nobel laureate David Gross decided to hold off on releasing the AI-produced artifacts and will write the work up themselves. Pure Yang–Mills existence is only part of the Clay Millennium Prize problem, so outsiders can’t check any of this yet.
Not everyone likes the process. The Verge reports that an independent advisory group had advised against handing results to designated early recipients, and more than 1,000 mathematicians have joined an association pledging to avoid working with AI companies.
What this means for you
- Don’t touch your security assumptions. ETH is a worst-case statement about SAT. Mainstream encryption isn’t built on it: RSA relies on the difficulty of factoring, and the paper’s listed consequences are about algorithms and circuit lower bounds, not attacks on RSA or AES.
- Watch the expert review, not the headlines. The Impagliazzo–Paturi–Williams group and the promised conference are where this gets confirmed or broken. Until then, treat it as a claim.
- Verify AI-generated proofs and code. Even with machine checking, the hard part is confirming the spec matches the intent. The same goes for AI-written code. Our guide on why AI models make things up covers the habits that help, and if you run agents, checkpoints and logs matter more than ever.
- Keep model choice grounded. A research result from an internal model doesn’t change which product model is best for your work. Use a practical checklist instead.
This post reports OpenAI’s claims and early expert reactions as of October 27, 2026. None of the three results has completed independent peer review. We’ll update this post as the review group and other researchers weigh in.



