AI refutes 30-year-old mathematical assumption in computer science
A central tenet in computer science has apparently been disproven by OpenAI, a result that will force textbooks to be rewritten if it is confirmed
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.
Advertisement
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. The findings also touch on the existence of pure Yang–Mills theory, part of a million-dollar mathematical problem, but don’t resolve the entire challenge. That work hasn’t been released publicly while an external group led by Nobel laureate David Gross examines it.
OpenAI says it verified the ETH result using Lean, a piece of software that checks mathematical proofs. Stefan Szeider at TU Wien in Austria has looked at what OpenAI has released and says he expects it to withstand scrutiny, although he says researchers still need to check that the formally proven statement means what its authors say it means.
To do so, OpenAI has commissioned an independent group, including Russell Impagliazzo and Ramamohan Paturi, both at the University of California, San Diego, who helped propose ETH, to examine the findings. In an open letter, the group says it could “change an important part of theoretical computer science”.
The speed at which AI is solving maths problems and the way AI firms are releasing their findings have concerned some academics. Magnus Wahlström at Royal Holloway, University of London, describes the phenomenon as “mathematics done by press”, worrying that proprietary models can suddenly overturn months of researchers’ work.
Bart Jansen at the Eindhoven University of Technology in the Netherlands describes OpenAI’s work on ETH as “ingenious”, “spectacular” and “awe-inspiring – but also humbling.” “It really makes you think about the future of mathematics, algorithms and academia,” he says.
Clément Canonne at the University of Sydney says proving something and understanding why it is true aren’t the same thing. “The web collapsed, and we looked behind,” he says of the network of findings relying on ETH. “We have no idea why yet.”
OpenAI says it is experimenting with an approach in which independent academics organise efforts to verify and explain the results. But Fomin welcomes the disruption. “This result destroys a lot, but it also opens many new opportunities and new questions that nobody expected,” he says. “One shouldn’t complain about having too many interesting mathematical breakthroughs to try to digest,” says Wahlström.
What's Your Reaction?
