OpenAI announces the falsification of the important theory "Exponential Time Hypothesis (ETH)" that has been used in the computer science field for over two decades.

BlockBeats news, October 27 - OpenAI recently announced that its AI model has "cracked" ETH—a development that quickly sparked heated discussion in both the tech and crypto communities. However, it must be specially noted that the ETH here is not Ethereum, widely known in the cryptocurrency space, but rather an important conjecture that has existed in computer science for over two decades: the Exponential Time Hypothesis (ETH).

The core question of the Exponential Time Hypothesis is: those problems that appear "especially hard to compute"—just how hard are they?

Take the "SAT problem" (the Boolean satisfiability problem), which some may have heard of, as an example. It asks: given a set of logical conditions, can you find an assignment that makes all conditions hold simultaneously? As the problem size grows, the best known methods today can essentially only try possible answers one by one, and the time cost grows exponentially with the size—what is commonly called "exponential time." ETH further asserts that such problems fundamentally cannot be substantially accelerated, and that no truly "sub-exponential time" efficient algorithm exists.

Since this hypothesis was proposed in 1999, it has been an important cornerstone of theoretical computer science. Hundreds of papers rely on it to prove that "such-and-such problem is hard" and that "such-and-such algorithm is already close to optimal." If ETH were overturned, it would mean that many problems we believe are "almost impossible to solve faster" might in theory have better solutions.

OpenAI this time claims that its model has found a deterministic algorithm that can exactly count the number of solutions to the k-SAT problem in sub-exponential time, and that it has been formally verified with Lean. If this result ultimately withstands expert review, it would directly shake the Exponential Time Hypothesis.