OpenAI says it has overturned the Exponential Time Hypothesis, not Ethereum’s ETH
OpenAI said on Oct. 26 U.S. time that one of its internal models had proved the Exponential Time Hypothesis, or ETH, false — a result tied to computational complexity, not Ethereum. The announcement centers on SAT and k-SAT, classic logic problems used to study how quickly hard problems can be solved. According to OpenAI, the proof has been formally verified in Lean and the materials have been published on GitHub, while an outside review group is still examining the claim. The paper, titled “The Exponential Time Hypothesis is False,” describes a deterministic algorithm that exactly counts the number of solutions to k-SAT for any fixed k ≥ 2 using only polynomial memory. OpenAI said that because counting solutions also determines whether a solution exists, the method also solves 3-SAT. The time bound is subexponential, which the company says contradicts ETH and also knocks down related assumptions including SETH, Gap-ETH, NSETH, and #ETH. OpenAI added that the result does not mean software will suddenly become faster in practice. It said substantial work is still needed to turn the theoretical breakthrough into usable algorithms. The external verification group includes ETH co-authors Russell Impagliazzo and Ramamohan Paturi, along with MIT’s Ryan Williams. As of publication, the group had not released its conclusion.


