OpenAI says an artificial-intelligence model has found a way to disprove the Exponential Time Hypothesis (ETH), a computer-science conjecture proposed in 1999. The claim has no connection to Ethereum, the cryptocurrency that trades under the ticker ETH, or to Ethereum co-founder Vitalik Buterin.

The announcement nevertheless prompted jokes across Crypto Twitter. “Damn algo traders just slaughtered $ETH,” user Takumi posted on X, while Andrew Jiang wrote, “Vitalik has been real quiet since this came out.”

The ETH at issue was proposed by computer scientists Russell Impagliazzo, Ramamohan Paturi and Francis Zane. It holds that the logic problem known as 3-SAT cannot be solved substantially faster than by examining every possible combination of variables. In 3-SAT, the objective is to determine whether true-or-false assignments can satisfy a collection of rules, with each rule containing three variables.

Hundreds of academic papers have relied on the hypothesis to establish that certain problems in graph theory, computational biology, databases and geometry cannot be solved quickly, according to OpenAI. The company said that disproving ETH could reopen questions about how much faster those tasks might be solved and help researchers search for improved algorithms.

“The refutation of the ETH reopens questions about how much faster these tasks could become,” OpenAI wrote in its blog post, “and may help guide the search for better algorithms.”

OpenAI’s 67-page paper, dated October 17 and revised October 25, describes a deterministic algorithm—one that does not use randomness—that counts every satisfying assignment for these puzzles in subexponential time. That means the amount of work increases more slowly than any exponential function of the number of variables. Because counting the number of solutions is harder than determining whether at least one solution exists, the result also resolves the decision problem.

OpenAI said its AI discovered the disproof on October 16 and that the result was formalized in Lean, software that mechanically verifies each logical step, on October 17. The paper and formalization are available on GitHub. OpenAI said this followed the release of 722 mathematical manuscripts earlier in the month, of which only 162 included a computer-checked main result. That machine-checkable format is what allows independent researchers to verify each step of the argument for themselves.

Impagliazzo, Paturi and MIT professor Ryan Williams are leading an independent examination of the claim. In an open letter, they cautioned that their participation should not be interpreted as an endorsement.

“Our involvement should not be taken as certification of the claim,” the three wrote, adding that “a result of this significance requires careful, independent scrutiny and an understanding that others can reconstruct, question, and build upon.”

OpenAI said the participants signed no non-disclosure agreements and are working without pay. The company also agreed to publish all raw data and finance a conference focused on the result.

The practical implications remain uncertain. “Finding such algorithms, and turning theoretical advances into practical improvements, will require significant further research,” OpenAI wrote. The paper also says the result does not establish that every problem in the complexity class NP can be solved in subexponential time.

That means the P versus NP problem remains open. P consists of problems that computers can solve efficiently, while NP consists of problems for which proposed solutions can be checked efficiently. The unresolved question is whether every problem whose answer can be checked efficiently can also be solved efficiently.

Anthropic entered the discussion on October 26 with a paper credited to Claude and titled “A 2^o(n) Time Algorithm for 3-SAT.” The repository, which also addresses the ETH problem, says an internal research Claude model discovered the algorithm. It adds that “the result is purely asymptotic and says nothing about solving formulas in practice.”

Claude formalized Fermat’s Last Theorem in Lean in September. Mathematician Terence Tao had warned about the possibility of overlapping AI efforts, writing 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 contribution to the Simons Foundation will support workshops, conferences and special programs intended to help researchers examine and build on results produced with AI.

Source: Decrypt