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.