Cade Metz, The New York Times; How A.I. Just Blew Up a Key Tenet of Computer Science
A longstanding hypothesis held that some problems would always be hard for computers to solve quickly. But OpenAI disproved it — raising the possibility of radical new efficiencies.
"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."
