OpenAI Proves ETH Is False, and Crypto Twitter Has Questions

Mathematicians are examining a new paper from OpenAI which asserts that the Exponential Time Hypothesis (ETH) is false, a claim that underpins hundreds of existing research papers. This announcement has generated significant discussion among both serious mathematicians and participants on Crypto Twitter.

The ETH, a computer-science conjecture originating in 1999, is what the AI models at OpenAI claim to have found a way to disprove; this is distinct from the "ETH" cryptocurrency that traders are familiar with. Consequently, crypto enthusiasts can remain calm, as the ETH under discussion pertains to the Exponential Time Hypothesis, which has no connection to the price of Ethereum or its co-founder, Vitalik Buterin.

OpenAI released a 67-page document asserting that its AI uncovered a method to circumvent this hypothesis, and the original proponents of the conjecture are now scrutinizing the findings. Francis Zane, along with computer scientists Russell Impagliazzo and Ramamohan Paturi, originally put forth ETH, which posits that a fundamental logic puzzle known as 3-SAT—a task involving finding true-or-false assignments that satisfy a set of rules, with three choices available per rule—cannot be solved significantly faster than by exhaustively checking every possible combination.

According to OpenAI, hundreds of papers rely on ETH to demonstrate that certain problems in fields such as geometry, databases, computational biology, and graph theory cannot be solved rapidly. Essentially, ETH serves as a boundary defining what computers are unlikely to perform quickly, and OpenAI's model has reportedly revised this boundary. The company stated on its blog that "The refutation of the ETH reopens questions about how much faster these tasks could become," and this could assist in steering the search for superior algorithms.

The paper, dated October 17 and subsequently updated on October 25, details a deterministic algorithm—one that involves no randomness—capable of counting every satisfying assignment for such puzzles in subexponential time. This means the computational effort increases more gradually than any exponential function relative to the number of variables. Since counting solutions is inherently more complex than merely determining if a solution exists, solving the harder counting problem effectively provides the solution to the easier decision problem concurrently. OpenAI reported that its AI identified this disproof on October 16, and it was formally documented in Lean, a software tool that mechanically verifies every logical step, on October 17. Both the disproof and the related materials are available on GitHub, following the same path as its 722 math manuscripts released earlier this month, of which only 162 contained a main result verified by a computer.

The independent verification of this work is being led by Ryan Williams from MIT, alongside Impagliazzo and Paturi, who have stressed the limitations of their involvement. In an open letter, the three authors noted, “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.”

Regarding the practical implications, OpenAI mentioned that the company agreed to fund a conference on the outcome and publish all raw data, while also stating that the participants signed no non-disclosure agreements and were not compensated for their work. Furthermore, OpenAI cautioned that "Finding such algorithms, and turning theoretical advances into practical improvements, will require significant further research." The paper itself clarifies that the discovery does not prove that every NP problem can be solved in subexponential time, thus leaving the P versus NP question—which asks if every problem whose solution is easy to verify also possesses an efficient solution—unresolved. To clarify, P represents the set of problems computers can solve efficiently, whereas NP is the set of problems whose proposed answers can be checked efficiently.

In response, Anthropic, seemingly keen not to concede ground in mathematical debates, published a paper attributed to Claude on October 26, titled “A $2^{o(n)}$ Time Algorithm for 3-SAT.” This repository, which also addresses the ETH issue, claims that an internal research model of Claude discovered the algorithm, adding that “the result is purely asymptotic and says nothing about solving formulas in practice.” Terence Tao, a mathematician, had anticipated this type of overlap, noting that Claude formalized Fermat’s Last Theorem in Lean back in September. He commented in September, “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.” OpenAI's recent $5 million donation to the Simons Foundation is intended to support workshops, conferences, and special programs designed to help researchers investigate and develop upon results generated by AI.