OpenAI 推翻一項電腦科學假設,但目前還沒有實際應用
A.I. Just Blew Up a Key Tenet of Computer Science
電腦科學家長期認為,有些問題很難快速解出來,即使答案一旦找到就很容易檢查。
- OpenAI 表示,它用 AI 推翻了相關的「指數時間假設」。
- 這項結果不等於解開了「P vs. NP」,也不代表電腦現在就能快速破解加密或設計新藥。研究者認為,這可能指出找到更快演演算法的方向,甚至幫助電腦設計更好的晶片。
- 但眼下的快速解法仍只存在理論上,還沒有直接的實際應用。
AI 伴隨問答
針對這篇報導有疑問?可直接點選快捷問題或向 AI 追問背景脈絡與技術細節:
這項結果動搖了「某些問題無法快速求解」的假設,但目前仍只有理論意義,實際應用還需要多年工程工作。

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.
Credit...Erik Carter
Listen
· 6:09 min
By 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.
Published Nov. 6, 2026Updated Nov. 10, 2026
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.”
Cade Metz is a Times reporter who writes about artificial intelligence, driverless cars, robotics, virtual reality and other emerging areas of technology.
Advertisement