In a startling development, OpenAI has claimed to have refuted the Exponential Time Hypothesis (ETH), a cornerstone assumption in computational complexity theory. Released on October 26, 2026, the work was produced by an internal model and formally verified using the Lean proof assistant. A group of the original proposers of ETH—Russell Impagliazzo, Ramamohan Paturi—and MIT’s Ryan Williams are now overseeing independent review of the findings. If validated, this could force a rethinking of many results in algorithms, cryptography, and theoretical computer science.
What is ETH and what’s being claimed
The Exponential Time Hypothesis, now over 25 years old, posits that solving 3-SAT (boolean satisfiability where each clause has 3 variables) cannot be done in subexponential time—that is, that time complexity must grow exponentially with the size of the input.
OpenAI’s paper presents a deterministic algorithm that, for any fixed width k-CNF formula, counts the number of satisfying assignments exactly using polynomial space and in subexponential time. The manuscript states the running time bound as roughly 2 raised to O(n log log n / √log n), while the version formally checked in Lean shows a similar but slightly weaker bound: about 2 raised to O(n (log log n)² / √log n). Either result, however, undercuts the exponential lower bound predicted by ETH.
How the research was released—and who is evaluating it
OpenAI reports that the internal model first generated the natural-language draft on October 16, then formalized the proof in Lean the next day, October 17. The public release happened October 26, with both the manuscript and Lean files posted to GitHub.
To validate the claim, OpenAI has enlisted ETH’s original proposers, Impagliazzo and Paturi, along with Williams, to lead a working group. Their job is not endorsement—but to help the community inspect the proof, assess the precise definitions, running time constants, and whether formal statements truly correspond to the version of ETH used historically.
Implications and limitations
These findings could ripple across theoretical computer science. Hundreds of complexity results assume ETH to establish hardness of problems in areas like graph algorithms, parameterized complexity, and query optimization. If ETH is indeed false, many theorems built on it may lose their foundation or need to be reformulated.
That said, the claim does not settle P vs NP. Subexponential time is still far from polynomial time. ETH’s refutation means the exact-SAT decision problems may be easier than thought in some cases—but the general reachability of P=NP remains unproven. Also, current cryptographic systems generally rely on specific problem hardness, not ETH per se, so there is no indication yet of broken encryption.
What’s being watched
First, the external working group’s findings—do the formal proofs and running time bounds precisely correspond to the mathematical ideal of ETH? Experts are scrutinizing definitions, asymptotic bounds, and whether the proof’s statements align with those assumed in prior ETH-based work.
Also of interest is how long before practical algorithms leverage this result. Even if ETH is false, the improvement in exponents is slow growing—only meaningful beyond astronomically large instance sizes. So any real-world speedups will probably take significant engineering.
By having AI produce both natural-language and formally verified work in complexity theory, this marks a pivotal moment: algorithms once thought intractable under ETH may need serious reconsideration. Whether this shifts how crypto, algorithm design, and theoretical CS behave in practice depends entirely on whether OpenAI’s proofs survive intense peer review—and whether researchers can build faster, more practical methods based on them.
