To understand the latest shocking development in A.I.-generated math, it helps to think about Sudoku.
Solving one of those nine-box number puzzles, especially at the highest difficulty levels, can be fiendishly time-consuming. But once you have a solution, it’s easy to double-check that you got it right: Just scan each row, column and box and confirm that each integer appears exactly once.
It’s an analogy that Russell Impagliazzo, a professor of computer science at the University of California, San Diego, invokes to explain a high-profile math question called “P vs. NP.” For years, Dr. Impagliazzo explains, he and other computer scientists have assumed that math and computer science obey that apparent truth about Sudoku: Solving a problem is much, much harder than checking that a solution is correct.
Sitting at the intersection of mathematics and theoretical computer science, “P vs. NP” is among the million-dollar Millennium Prize problems laid down by the Clay Mathematics Institute 25 years ago. In non-math speak, “P” represents computational problems that can be solved quickly, while “NP” represents problems whose solutions can be checked easily.
Common sense says that checking solutions should be much easier than finding solutions. “If P and NP follow intuition, then they should definitely not be equal,” said Ryan Williams, a professor of engineering and computer science at the Massachusetts Institute of Technology.
On Oct. 26, OpenAI, the maker of ChatGPT, cast doubt on that seemingly obvious argument. While the broader problem of “P vs. NP” remains unsolved, the company announced that its newest artificial intelligence technology had refuted a related conjecture called the exponential time hypothesis, or E.T.H., which Dr. Impagliazzo proposed in 1998 with his colleague Ramamohan Paturi and a Bell Labs researcher named Francis Zane. Similar to the argument that P can’t equal NP, the E.T.H. held that certain problems must always remain hard for computers to solve quickly.
OpenAI’s result indicates that isn’t the case. It hints that machines could in theory solve Sudoku puzzles just as quickly as they could check their solutions — even when the grid spans 1,000 rows or more. The finding also suggests that computers could rapidly design new algorithms and new electrical circuits for new kinds of computers, helping to create their own successors.
“If you have a really fast algorithm for Sudoku solving,” Dr. Impagliazzo said, “you could use it to design optimal circuits.”
Among many other mind-bending scenarios, OpenAI’s proof could point to a future in which computers rapidly crack the encryption that guards the world’s secrets or design new medicines by optimizing the behavior of proteins in the body. All of this is theoretical. But machines are already moving in this direction, with new approaches that could turbocharge chip design, drug discovery and other areas.
OpenAI’s announcement is just one of nearly 400 scientific findings that the company and its A.I. rivals released in recent weeks, claiming to answer important questions in math, physics and computer science that have bedeviled human experts for decades. Just after OpenAI’s announcement, Anthropic, its primary rival, said that it too had disproved the E.T.H.
(The New York Times sued OpenAI and Microsoft in 2023, claiming copyright infringement of news content related to A.I. systems. The two companies have denied those claims.)
For decades, computer scientists have wondered whether powerful machines could find hidden shortcuts that allowed them to solve hard problems with surprising speed. As Dr. Impagliazzo puts it: “Are there very impressive shortcuts that can avoid actually enumerating all the possible solutions and just get to the best without going through all the rest?” OpenAI’s disproof of his hypothesis hints that those shortcuts might exist after all — a finding that Dr. Impagliazzo called “very shocking news.”
“It is also a shock,” he added, “that the work was not done by a human being.”
Although OpenAI’s result is enormously unsettling for experts like Dr. Impagliazzo, it has no real effect on today’s technologies: For now, the magic shortcuts are possible only in theory.
“Immediate, practical applications? There aren’t any,” Dr. Williams said.
But he and others believe that OpenAI’s result could point to new applications in the future. This kind of theoretical result often requires years, or even decades, of engineering to realize its potential.
In the mid-1980s, theoretical computer scientists proposed something called an interactive proof. But the idea did not deliver a practical application until the 2010s, when it helped power the blockchain technologies that underpin bitcoin and other cryptocurrencies.
The most intriguing potential application could involve artificial intelligence itself: In using A.I. to debunk the exponential time hypothesis, OpenAI and Anthropic raised the possibility that machines could one day have the power to improve themselves in extraordinarily efficient ways. And that is exactly the phenomenon, called recursive self-improvement, that companies like OpenAI and Anthropic are now trying to unlock.
“This could lead to better A.I.,” Dr. Impagliazzo said, “in all sorts of ways.”
The post How A.I. Just Blew Up a Key Tenet of Computer Science appeared first on New York Times.
