Algorithm, Not Altcoin: OpenAI’s AI ‘Refutation’ Isn’t About $ETH

OpenAI published a 67-page paper claiming its AI found a deterministic algorithm that refutes ETH, the Exponential Time Hypothesis, a computer-science conjecture from 1999 with no connection to Ethereum, its price or co-founder Vitalik Buterin. The paper, dated October 17 and revised October 25, describes counting every satisfying assignment of 3-SAT puzzles in subexponential time, meaning the work grows more slowly than any exponential in the number of variables. OpenAI says its AI found the disproof on October 16 and formalized it in Lean, software that verifies every logical step mechanically, on October 17.

Crypto Twitter reacted as if the acronym referred to Ethereum: “Damn algo traders just slaughtered $ETH,” Takumi posted on X, while Andrew Jiang quipped: “Vitalik has been real quiet since this came out.” ETH was proposed by computer scientists Russell Impagliazzo and Ramamohan Paturi with Francis Zane. It says 3-SAT—finding true-or-false settings that satisfy a pile of rules, three options at a time—cannot be solved much faster than trying every combination. Hundreds of papers assume the hypothesis to show that problems in graph theory, computational biology, databases and geometry cannot be solved quickly, according to OpenAI.

OpenAI wrote on its blog: “The refutation of the ETH reopens questions about how much faster these tasks could become,” adding that “and may help guide the search for better algorithms.” Counting solutions is harder than deciding whether one exists, so the harder operation also provides the easier decision problem.

The paper and its Lean formalization sit on GitHub, the same route used for OpenAI’s 722 math manuscripts earlier this month, of which only 162 came with a computer-checked main result. Impagliazzo, Paturi and MIT’s Ryan Williams are leading an independent examination. In an open letter, the three wrote: “Our involvement should not be taken as certification of the claim,” adding that “a result of this significance requires careful, independent scrutiny and an understanding that others can reconstruct, question, and build upon.”

OpenAI said participants signed no non-disclosure agreements, worked unpaid, and that the company agreed to publish all raw data and fund a conference on the result. The company cautioned: “Finding such algorithms, and turning theoretical advances into practical improvements, will require significant further research.” The paper says the result does not show that every NP problem can be solved in subexponential time, so P versus NP remains open.