OpenAI announced it has disproven the Exponential Time Hypothesis, a key theory in computer science that has been widely used for over two decades.

OpenAI recently announced that its AI model has "cracked" ETH, a news that quickly sparked heated discussions in both the tech and crypto communities. It is important to note that the ETH here is not the widely known Ethereum cryptocurrency, but rather a key conjecture in computer science that has existed for over two decades: the Exponential Time Hypothesis (ETH). The core question of the Exponential Time Hypothesis is: how "extremely difficult" are problems that appear computationally hard? Take the SAT problem (Boolean satisfiability problem), which many have heard of, as an example: it asks, given a set of logical conditions, can you find an assignment that satisfies all conditions at the same time? As the problem scale grows, the best known approach basically has to test all possible answers one by one, with time complexity increasing exponentially with the scale—this is what we commonly call "exponential time". The Exponential Time Hypothesis further asserts that such problems are inherently incapable of being significantly accelerated, and no truly efficient "sub-exponential time" algorithm exists for them. Since its proposal in 1999, this hypothesis has been a cornerstone of theoretical computer science. Hundreds of papers have used it as a basis to prove that "certain problems are hard" and "certain algorithms are near-optimal". If the Exponential Time Hypothesis is disproven, it would mean that many problems we thought were "almost impossible to solve faster" might theoretically have better solutions. OpenAI claimed that its model has found a deterministic algorithm that can accurately count the number of solutions to the k-SAT problem in sub-exponential time, and has conducted formal verification via Lean. If this result ultimately passes expert review, it will directly undermine the Exponential Time Hypothesis.