[DigitalToday reporter Jinju Hong] OpenAI said its artificial intelligence (AI) model found an algorithm that challenges the Exponential Time Hypothesis (ETH), a long-standing conjecture in computational theory. Independent verification by mathematicians is under way, and further research is needed before it translates into improved real-world computing performance.

On Oct. 27 local time, blockchain media outlet Decrypt reported that OpenAI, in a 67-page paper, presented a deterministic algorithm that can compute solutions to the 3-SAT problem faster than previously expected. ETH is a hypothesis that holds there is no algorithm that can solve certain problems much faster than exponential time. Since it was proposed in 1999, it has been used as an important assumption in research across fields including graph theory and computational biology.

The news also drew attention in the cryptocurrency community. Confusion arose because ETH is the same as the ticker for Ethereum (ETH). On X, formerly Twitter, one user wrote: "Algorithm traders destroyed Ethereum," and jokes also surfaced that Vitalik Buterin had been quiet after the news. But the ETH in this case refers to the Exponential Time Hypothesis, not Ethereum.

At the center is an algorithm that counts how many possible solutions a 3-SAT problem has. 3-SAT is a classic problem of finding a combination of variables that simultaneously satisfies multiple logical conditions. OpenAI presented a way to count the number of solutions within quasi-exponential time that grows more slowly than an exponential function of the number of variables. If the result holds, it could affect existing perspectives on related computational problems.

According to OpenAI, the AI found the result on Oct. 16 and formalised the proof the next day using Lean, software that mechanically verifies mathematical proofs. Related materials were also released on GitHub.

The mathematics community stressed cautious verification. Russell Impagliazzo, Ramamohan Paturi and Massachusetts Institute of Technology (MIT) professor Ryan Williams said in an open letter that participation in the review does not mean the claim is being certified, and that independent reproduction and further review are needed.

Rival Anthropic also released a paper on a 3-SAT-related algorithm on Oct. 26 under the name Claude. It said the result concerns an improvement in theoretical time complexity and is not directly related to real-world problem-solving performance.

OpenAI also said substantial additional research is needed to connect theoretical progress to actual performance improvements. The result does not mean all NP problems can be solved quickly, and the P versus NP problem remains unsolved. The study shows AI's potential for mathematical discovery, but independent verification is needed before its significance can be confirmed.

Vitalik has been real quiet since this came out