OpenAI, the company behind ChatGPT, says its AI models have disproven the Exponential Time Hypothesis, a foundational assumption that underpins much of computer science. The claim, if it holds up, would overturn a conjecture proposed nearly 30 years ago and force researchers to reconsider a range of conclusions built on it.
The Exponential Time Hypothesis, or ETH, sets a limit on how quickly computers can solve certain logical puzzles. The simplest approach is to test every possible combination of true or false values for each part of a puzzle. ETH proposes that, although shortcuts may speed this up, the amount of work required must still grow exponentially as the puzzle becomes larger. OpenAI says its models have devised an algorithm that beats that assumed speed limit for solving such puzzles, which would apparently prove the hypothesis false.
The reaction from academics has been striking. Fedor Fomin at the University of Bergen in Norway described the result as a complete surprise. "Nobody I know expected it," he said. Leslie Goldberg at the University of Oxford called it an enormous breakthrough, provided it is confirmed. Many findings in computer science assume ETH is true, and if it is not, the conclusions those findings establish about computational limits lose their force. Fomin said that would require a complete revision of several areas of algorithms and complexity, and that a textbook he wrote on the subject would become obsolete if the finding holds.
ETH is also linked to P versus NP, a longstanding problem in mathematics that asks whether a problem whose answer is easy to check is also easy to solve. If ETH were true, it would have implied that the answer to P versus NP is no. Disproving ETH, however, does not establish that the answer is yes. Goldberg cautioned that the result has no direct impact on P versus NP and should not be viewed as progress toward it.
OpenAI announced the ETH result in a blog post on 26 October, alongside other claimed breakthroughs in mathematics and physics. In mathematics, the company says its AI proved a 1991 conjecture that waves cannot remain intensely focused for long. If confirmed, that would also answer longstanding questions about how thin a shape can be while still containing line segments pointing in every direction, and about how waves spread. In theoretical physics, OpenAI claims to have shown that quantum field theories, including quantum chromodynamics, which describes the strong force that holds quarks together, make mathematical sense rather than simply producing predictions that match experiments. The company says these findings also touch on the existence of pure Yang–Mills theory, part of a well-known million-dollar mathematics problem, but do not resolve that challenge. That work has not been released publicly while an external group led by Nobel laureate David Gross examines it.
OpenAI says it verified the ETH result using Lean, software that checks mathematical proofs. Stefan Szeider at TU Wien in Austria has reviewed what the company released and expects it to withstand scrutiny, though he noted that researchers still need to confirm that the formally proven statement means what its authors say it means. To that end, OpenAI has commissioned an independent group that includes Russell Impagliazzo and Ramamohan Paturi, two of the researchers who helped propose ETH. In an open letter, they said the result could "change an important part of theoretical computer science."
The speed at which AI is tackling mathematics problems, and the way companies release their findings, have also concerned some academics. Magnus Wahlström at Royal Holloway, University of London, described the phenomenon as "mathematics done by press," warning that proprietary models can suddenly overturn months of researchers' work. Bart Jansen at Eindhoven University of Technology in the Netherlands called OpenAI's ETH work ingenious, spectacular and awe-inspiring, but also humbling. Clément Canonne at the University of Sydney made a further distinction: proving something is not the same as understanding why it is true. "The web collapsed, and we looked behind," he said of the network of results that rely on ETH. "We have no idea why yet."
OpenAI says it is experimenting with an approach in which independent academics organize efforts to verify and explain the results. Fomin, despite the upheaval, welcomed the development. "This result destroys a lot, but it also opens many new opportunities and new questions that nobody expected," he said. Wahlström offered a similar view: one should not complain about having too many interesting mathematical breakthroughs to digest.
11
