OpenAI Proves ETH Is False, and Crypto Twitter Has Questions

OpenAI says ETH is false, and Crypto Twitter reacted exactly the way you would expect. “Damn algo traders just slaughtered $ETH,” a user called Takumi posted on X, while Andrew Jiang quipped: “Vitalik has been real quiet since this came out.”

But chill out, degens, the ETH in question is the Exponential Time Hypothesis, a computer-science conjecture from 1999 that has nothing to do with Ethereum, its price, or co-founder Vitalik Buterin. So, crypto bros, you can breathe.

OpenAI published a 67-page paper claiming its AI found a way around the hypothesis, and the people who proposed it are now checking the work.

Computer scientists Russell Impagliazzo and Ramamohan Paturi proposed ETH with Francis Zane, and it says a classic logic puzzle called 3-SAT (finding true-or-false settings that satisfy a pile of rules, three options at a time) cannot be solved much faster than by trying every combination. Hundreds of papers assume it to show that problems in graph theory, computational biology, databases and geometry cannot be solved quickly, per OpenAI.

In other words, ETH is a map of what computers will probably never do fast, and OpenAI says its model just redrew it. “The refutation of the ETH reopens questions about how much faster these tasks could become,” the company wrote on its blog, “and may help guide the search for better algorithms.”

The paper, dated October 17 and revised October 25, describes a deterministic algorithm (one with no randomness) that counts every satisfying assignment of such puzzles in subexponential time, meaning the work grows more slowly than any exponential in the number of variables. Counting solutions is harder than deciding if one exists, so the harder job brings the easier one along for free.

OpenAI says its AI found the disproof on October 16 and that it was formalized in Lean, software that verifies every logical step mechanically, on October 17. Both sit on GitHub, the same route as its 722 math manuscripts earlier this month, of which only 162 came with a computer-checked main result.

Impagliazzo, Paturi, and MIT’s Ryan Williams lead the independent examination, and they are careful about their role. “Our involvement should not be taken as certification of the claim,” the three wrote in an open letter, adding that “a result of this significance requires careful, independent scrutiny and an understanding that others can reconstruct, question, and build upon.”

BitcoinBTC · USD

$80,917−2.63%

24H7D1M1YYTD

Oct 20Oct 22Oct 24Oct 26Oct 27

$84.8k$83.1k$81.3k$79.6k

24h HighHigh$80,727

24h LowLow$79,416

VolVol$1.1B

→

$50$100$500

Buy

OpenAI says participants signed no non-disclosure agreements and work unpaid, and the company agreed to publish all raw data and fund a conference on the result.

Practical payoffs are far off: “Finding such algorithms, and turning theoretical advances into practical improvements, will require significant further research,” OpenAI wrote. The paper itself says the result does not show that every NP problem can be solved in subexponential time, so P versus NP, the question of if every problem with an easy-to-check answer is also easy to solve, stays open.

In simple terms, P is the class of problems that computers can solve efficiently, while NP is the class of problems whose proposed solutions can be checked efficiently. So P versus NP — the question of whether every problem whose answer is easy to check is also easy to solve — stays open.

Anthropic, not wanting to lose the math wars, then posted a paper credited to Claude titled “A 2^o(n) Time Algorithm for 3-SAT” and dated October 26. The repository, which also tackles the ETH problem, says an internal research Claude model discovered the algorithm, and “the result is purely asymptotic and says nothing about solving formulas in practice.”

Claude formalized Fermat’s Last Theorem in Lean in September, and Terence Tao saw this kind of overlap coming. “We have now seen that even the rumor of someone working on a problem can trigger a massive amount of AI-powered effort to flatten it before the original research project has time to reach its full potential,” the mathematician wrote in September.

OpenAI’s recent $5 million contribution to the Simons Foundation will fund workshops, conferences and special programs to help researchers examine and build on AI-produced results.