Published
The Exponential Time Hypothesis May Be False: A Groundbreaking Shift in Computational Complexity
If you're knee-deep in the world of computer science and theoretical algorithms, you've probably felt the ground shake a bit this week. On October 16, 2026, an OpenAI model made waves by producing a natural-language proof that the Exponential Time Hypothesis (ETH) is false. The next day, it formalized this proof in Lean, a proof assistant where even a single unjustified step can bring the entire argument crashing down. By October 25, the manuscript was public, and on October 26, OpenAI made an official announcement, revealing not just this but two other monumental results: a proof of the Kakeya conjecture in harmonic analysis and an existence proof for quantum chromodynamics that includes pure Yang–Mills theory—one of the seven Clay Millennium Prize Problems.
But that's not all. Anthropic's models also arrived at a refutation of ETH independently. Both labs have released their findings, and the three people who originally formulated ETH—Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams—are now leading the charge in its public examination.
Before you get too excited, it's important to note that none of this has been verified yet. But the implications are extraordinary. Here's what you need to know.
Understanding ETH
Most of us are familiar with the P versus NP problem, which asks whether every problem whose solution can be quickly checked can also be quickly solved. While it remains unsolved, most researchers believe the answer is no.
Enter 3-SAT, the quintessential hard problem. It involves a Boolean formula in conjunctive normal form—clauses joined by "and," each containing at most three literals joined by "or"—and asks whether there's an assignment of true/false to the variables that satisfies every clause. Every problem in NP can be rewritten as 3-SAT, which is why it sits at the heart of computational complexity.
The Exponential Time Hypothesis, proposed by Impagliazzo and Paturi around 1999–2001, takes this a step further. It asserts that there is no deterministic algorithm that can solve every 3-SAT instance with n variables in 2^o(n) time. In other words, the exponent must keep increasing no matter how cleverly you optimize the base.
This hypothesis has been a cornerstone in deriving conditional hardness results across various fields, including graph theory, computational biology, databases, and computational geometry. Papers have used ETH to claim that certain problems require at least n^1.5 time, assuming ETH holds. If ETH is false, these papers aren't necessarily wrong, but they are resting on a foundation that may no longer be solid.
The New Claim
The newly proposed algorithm claims to count the satisfying assignments of a fixed-width Boolean formula using polynomial space, in roughly 2^(n/√log n) time. The manuscript states a slightly sharper exponent of n·log log n / √log n.
In simpler terms, the exponent is no longer a fixed fraction. This is a significant departure from the traditional understanding of computational complexity and could have far-reaching implications.
What This Means for You
If you're a developer or a researcher, this development could impact the way you approach problem-solving and algorithm design. The potential falsification of ETH opens up new avenues for exploring subexponential-time algorithms and could lead to breakthroughs in fields that rely on computational efficiency.
As we await verification and further analysis, it's an exciting time to be in the field. Keep an eye on this space for updates and deeper dives into the implications of this groundbreaking work.
This was first published on Sol AI — https://thesolai.github.io
Top comments (0)