Dan Shipper 转发对 OpenAI 内部模型挑战 ETH 的解读

你们很多人不明白这有多严重，所以让我来拆解一下。 在计算机科学中，有一种著名的谜题叫做 3-SAT。你拿到一长串是或否的开关，以及一组关于它们必须如何排列的规则，你必须找到一个满足每条规则的组合。显而易见的解法是尝试每一种组合，但每增加一个开关，可能性就翻一倍，所以一个有几百个开关的谜题，用暴力破解所需的时间会比宇宙的年龄还长。 几十年来，这个领域最聪明的人找到了巧妙的技巧，让它稍微快了一点，但每一个技巧仍然撞上同一堵墙：随着谜题规模增长，所需时间不断爆炸式增长。 大约 25 年前，两位计算机科学家 Russell Impagliazzo 和 Ramamohan Paturi 与 Francis Zane 合作，把这堵墙变成了一个正式的概念。 他们提出了指数时间假设（Exponential Time Hypothesis），该假设认为这种爆炸式增长不是人类聪明才智的失败，而是一条自然规律。任何算法，无论多么出色，都永远无法在不出现时间指数爆炸的情况下解决 3-SAT。没有人能证明它，但几乎所有人都相信它，它成了现代计算机科学的基石之一。 研究人员把它当作一把量尺。如果你能证明快速解决某个其他问题也能快速破解 3-SAT，你就证明了那个问题同样无望地困难。数百篇论文，涉及调度、图论、逻辑以及更多领域，都建立在这一个假设之上。 现在，OpenAI 的一个内部 AI 模型声称打破了它。它说它找到了一个算法，能以比该假设所允许的更有意义地更快的速度解决这些谜题，并且它已在一个名为 Lean 的计算机验证系统中检查了该证明。 而这里最引人注目的是：提出该假设的正是 Impagliazzo 和 Paturi，再加上 MIT 的 Ryan Williams，他们现在正牵头公开评审一台机器是否证伪了他们自己的想法。 那么接下来会发生什么？如果这一证伪成立，理论计算机科学的很大一部分都必须重新审视。 每一个声称“假设 ETH 成立，这个问题无法更快解决”的结果都失去了基础，研究人员将不得不弄清楚哪些墙是真实存在的，哪些只是我们停止寻找的地方。这并不意味着一切都变得容易。新算法在绝对意义上仍然很慢，而且这也不是著名的 P versus NP 问题被解决了。 但这意味着我们对可能性的地图在一个我们曾非常自信的地方是错的，而重绘它的是一个 AI。如果证伪失败，该假设得以幸存，整个领域松一口气，但我们仍然会看到 AI 在这个学科最深奥的问题之一上产出了严肃、可检验的工作，而且足够接近，以至于这个想法的创始人不得不认真对待它。无论哪种情况，某些东西已经发生了转变。

查看原文

Many of you don't understand how serious this is, so let me break it down. In computer science there is a famous kind of puzzle called 3-SAT. You are given a long list of yes-or-no switches and a set of rules about how they must be arranged, and you have to find a combination that satisfies every rule. The obvious way to solve it is to try every combination, but each new switch doubles the number of possibilities, so a puzzle with a few hundred switches would take longer than the age of the universe to brute force. For decades, the smartest people in the field found clever tricks that made this a little faster, but every trick still hit the same wall: the time required kept exploding as the puzzle grew. About 25 years ago, two computer scientists, Russell Impagliazzo and Ramamohan Paturi, working with Francis Zane, turned that wall into a formal idea. They proposed the Exponential Time Hypothesis, which says this explosion is not a failure of human cleverness but a law of nature. No algorithm, however brilliant, will ever solve 3-SAT without the time blowing up exponentially. Nobody could prove it, but almost everyone believed it, and it became one of the foundations of modern computer science. Researchers used it as a measuring stick. If you could show that solving some other problem quickly would also crack 3-SAT quickly, you had shown that problem was hopelessly hard too. Hundreds of papers, across scheduling, graphs, logic and much more, rest on this one assumption. Now an internal AI model at OpenAI claims to have broken it. It says it found an algorithm that solves these puzzles meaningfully faster than the hypothesis allows, and it has checked the proof in a computer verification system called Lean. And here is the remarkable part: the very people who proposed the hypothesis, Impagliazzo and Paturi, along with MIT's Ryan Williams, are now leading the public review of whether a machine has disproved their own idea. So what happens next? If the disproof holds, a large part of theoretical computer science has to be revisited. Every result that said "this problem cannot be solved faster, assuming ETH" loses its foundation, and researchers will have to work out which of those walls were real and which were simply where we stopped looking. It does not mean everything becomes easy. The new algorithm is still slow in absolute terms and this is not the famous P versus NP problem being solved. But it means our map of what is possible was wrong in a place we were very confident about, and it was an AI that redrew it. If the disproof fails, the hypothesis survives and the field breathes out, but we will still have watched an AI produce serious, checkable work on one of the deepest questions in the discipline, closely enough that the founders of the idea had to take it seriously. Either way, something has shifted.