Tech • AI • Robotics • Game
The One Thing Holding Theoretical CS Together Just Broke... Kinda
7/10TL;DR
A new algorithm for 3-SAT appears to run in subexponential time, potentially disproving the Exponential Time Hypothesis that has underpinned hundreds of lower-bound results in theoretical computer science since 1999.
KEY POINTS
A core complexity assumption may have fallen
The Exponential Time Hypothesis, or ETH, was formulated in 1999 by Russell Impagliazzo, Ramamohan Paturi, and Francis Zane at UC San Diego. It asserts that 3-SAT cannot be solved in subexponential time as the number of variables grows. While stronger than the conjecture that P ≠ NP, ETH became a standard working assumption because it let researchers prove hard limits for many other problems.
Why 3-SAT matters
In 3-SAT, the task is to assign true or false values to variables so that each clause of three literals is satisfied. The problem is a classic NP-complete benchmark: a fast general algorithm for it would have sweeping consequences across optimization, verification, and cryptography. Decades of work improved exact algorithms from naive 2^n search to roughly 1.3^n, but still with exponential growth.
A new result claims a subexponential algorithm
A 67-page paper by Dan Roberts, a physicist at OpenAI, describes an algorithm for 3-SAT with running time about 2^(n / sqrt(log n)). That is still enormous in practice, but it is subexponential in n. If the proof holds, ETH is false by definition.
The technique departs from standard search
Rather than searching directly for a satisfying assignment, the method reframes the problem around counting solutions. It breaks a large global sum into parts, adjusts the formula so constraints become more separable, counts solutions within those pieces, and then reconstructs the exact answer using Hermite interpolation, a mathematical tool dating to the 19th century. Researchers highlighted that this route was unusual enough that many had not considered it a plausible path.
The practical impact is near zero for now
The algorithm does not beat brute force at realistic scales. Estimates indicate it would only become favorable when n exceeds roughly 10^10,000, far beyond any imaginable real instance. That means no immediate acceleration for satisfiability solvers, route planning, or cryptographic attacks.
The theoretical impact could be large
ETH has been used to justify lower bounds across a wide range of problems, including k-clique and exact exponential algorithms for variants of the traveling salesman problem. More than 800 papers are said to rely on the assumption in some form. Those results are not automatically wrong, but any theorem whose hardness bound depends specifically on ETH may need to be revisited or weakened.
Leading theorists reacted with surprise
The result triggered unusually strong reactions among complexity researchers. Scott Aaronson reportedly learned of it from graduate students rushing into his office and said it materially changed his personal estimate of the odds that P = NP, moving from 3% to 5%. He also noted that ETH may simply have been stated too aggressively, suggesting weaker versions could survive.
Independent checking is now central
OpenAI asked Impagliazzo and Paturi to help verify the proof. They were not reported to be under contract or paid for the review. Early drafts were described as difficult to read, and substantial rewriting was needed before broader circulation, underscoring that the current focus is not on implementation but on whether the argument is mathematically sound.
CONCLUSION
If the proof stands, a foundational assumption in modern complexity theory will have been overturned without producing any immediate practical speedup. The real consequence would be a major rewrite of how computer scientists argue that certain hard problems cannot be solved significantly faster.
Ask a question