AI refutes 30-year-old mathematical assumption in computer science

OpenAI announced three new discoveries in mathematics, computer science and physics Samuel Boivin/NurPhoto via OpenAI, the maker of ChatGPT, claims its AI models have disproven the exponential time hypothesis – a fundamental assumption that underpins computer science. “This came as a complete surprise, a shock,” says Fedor Fomin at the University of Bergen in Norway. “Nobody I know expected it.” Proposed nearly 30 years ago, the exponential time hypothesis (ETH) tries to put a limit on how quickly computers can solve certain logical puzzles. The simplest way would be to try every possible combination of true or false for each part of the puzzle. ETH proposes that, although it may be possible to do this quicker with shortcuts, the amount of work needed has to grow exponentially as the puzzle gets bigger. OpenAI, however, says its models have devised an algorithm that can beat the previously assumed speed limit for solving logical puzzles, apparently proving ETH false. “Assuming that it is confirmed, this is an enormous breakthrough,” says Leslie Goldberg at the University of Oxford. Many computer science findings assume ETH is true. If it isn’t, the conclusions they establish about computational limits become useless. “It would require a complete revision of several areas of algorithms and complexity,” says Fomin, who says a textbook he wrote on the subject would become obsolete if the finding holds. ETH is linked to a long-standing maths problem known as P versus NP, which concerns 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 was no. But disproving ETH wouldn’t mean the answer is yes. “This doesn’t have a direct impact on P versus NP, so we should not view it as progress towards P versus NP,” says Goldberg. The result was announced alongside other breakthroughs in maths and physics in a blog post on 26 October. In mathematics, OpenAI says its AI has proved a 1991 conjecture that waves cannot remain intensely focused for long. If confirmed, this would also answer enduring questions about how thin a shape can be while also containing line segments that point in every direction, as well as how waves spread. In theoretical physics, OpenAI claims to have proven that quantum field theories – including quantum chromodynamics, which describes the strong force holding quarks together – make sense mathematically, rather than just producing predictions that match experiments.