A.I. Just Blew Up a Key Tenet of Computer Science

Source: nytimes.com
25 points by doener 3 hours ago on hackernews | 22 comments

You have a preview view of this article while we are checking your access. When we have confirmed access, the full article content will load.

A drawing of a purple key against a bright blue background.
Credit...Erik Carter

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.

Cade Metz

Cade Metz has written about A.I. for more than 15 years. But he has never solved a 1,000-row Sudoku puzzle.

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.


Thank you for your patience while we verify access. If you are in Reader mode please exit and log into your Times account, or subscribe for all of The Times.


Thank you for your patience while we verify access.

Already a subscriber? Log in.

Want all of The Times? Subscribe.

Related Content

Advertisement

SKIP ADVERTISEMENT