人工智能刚刚颠覆了计算机科学的一个关键信条
A.I. Just Blew Up a Key Tenet of Computer Science

原始链接: https://www.nytimes.com/2026/11/06/science/ai-exponential-time-hypothesis.html

OpenAI 最新的 AI 技术据报道反驳了指数时间假说,该假说是与未解的 P 与 NP 问题相关的猜想。文章用数独来说明求解可能比验证解法更难。P 表示可快速求解的问题,NP 表示解法容易验证的问题。P 与 NP 问题询问这两个类别是否相等,许多计算机科学家认为它们并不相等。1998 年提出的指数时间假说同样认为某些问题对计算机来说必须保持难以快速求解。OpenAI 的结果挑战了这一假设,但它本身并没有解决 P 与 NP 问题。

Hacker News 帖子链接到一篇纽约时报文章,称 AI 被指推翻指数时间假设,被描述为挑战计算机科学的一个关键信条。该帖有 17 点和 7 条评论。评论者持怀疑态度:有人称文章是旧闻或过度炒作,指出 OpenAI 的证明未经验证,并表示 ETH 被证伪对 P 与 NP 问题没有实际影响。其他人讨论 P=NP 不一定意味着可有效求解,引用 Aaronson 将其对 P=NP 的概率从 3% 提高到 5%,并批评 AI 炒作。该帖还包含先前讨论和归档文章的链接。
相关文章

原文

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.

联系我们 contact @ memedata.com