Frontier AI实验室声称其模型驳斥了指数时间假说

demo

2026年10月27日 星期二 Tim Fernholz


图片来源：ChatGPT

OpenAI 发布了三个长期困扰研究人员的重大数学难题的解决方案。其中一个令人意外地推翻了指数时间假设（ETH），该假设是计算机科学中一个根深蒂固的假设，对我们理解计算难题起着至关重要的作用。

与以往前沿实验室发布的证据一样，科学界的反应既令人兴奋又令人沮丧。人格心理学家莱文特·阿尔珀格（Levent Alpöge）指出，OpenAI 的解决方案是基于已有的研究成果，几个小时后，人格心理学便发布了对 ETH 的反驳。

然而，OpenAI 的流程正在不断改进。这一次，该实验室针对三个相关学科采取了不同的发布方式：数学家们的工作成果直接发布在 GitHub 上；计算机科学家们组成了一个工作组，要求公开证明过程，并由 OpenAI 资助举办一次会议进行讨论；物理学家们也组成了一个工作组，负责决定如何发布他们的研究成果。

麻省理工学院教授瑞安·威廉姆斯（Ryan Williams）正在组织计算机科学界对这一新发现做出回应。威廉姆斯教授的研究重点是计算复杂性问题，他过去曾批评过OpenAI的做法，并在今年10月初称其公开的证据是“对数学家的DDoS攻击”。

然而，他告诉TechCrunch，他同意与前沿实验室合作，以帮助引导对该领域至关重要的想法。该实验室邀请他与加州大学圣地亚哥分校的计算机科学家Russell Impagliazzo和Ramamohan Paturi一起解读解决方案，后者于1999年首次发表了ETH。

他们的第一步是发表一封公开信，呼吁对这些问题感兴趣的科学家提供反馈，并讨论人工智能对他们工作做出贡献的相关规范。

“OpenAI 的证明中有些部分可以说是常规的，但确实有两三个部分看起来很奇特，正是这些部分让我觉得，哇，这是整个社区需要共同努力的事情，”威廉姆斯告诉 TechCrunch。

你对 P 类与 NP 类有了解吗？

ETH 属于 P 与 NP 这类更广泛的问题范畴，这类问题几十年来一直是计算机科学及其他诸多领域的研究热点。简而言之，研究人员试图理解，任何易于验证其解的问题（NP）是否也易于解决（P）。

一个简单的例子是数独游戏：一旦找到一个解法，就可以很快验证，但找到解法本身却很耗时。这种现象适用于许多重要问题，而密码学系统正是基于此：当你拥有加密信息的密钥时，你可以解密信息，但真正破解一个有效的密码却需要太长时间，以至于无法实际应用。

然而，科学家们尚未证明这是否总是成立。“P=NP 的意思是，你不仅可以验证数独的解是否存在，还可以直接生成它们，”威廉姆斯说。“P=NP 断言，对于你能快速验证的每一个问题，这个结论都成立——如果你能快速验证它，你就能快速解决它。所以这听起来好得令人难以置信。”

这就是为什么大多数科学家都认为 P ≠ NP。ETH 提供了证据来支持这一点。它基本上指出，即使是最快的计算机算法，在特定类型的复杂逻辑谜题中，随着变量数量的增加，找到解决方案所需的时间也会呈指数级增长。

OpenAI 和 Anthropic 声称，他们的模型已经找到了能够在“亚指数级”时间内解决这些难题的算法，这意味着速度比之前认为的可能速度还要快。如果属实，他们或许已经证明了有效未来理论（EFT）是错误的——用科学术语来说，就是驳斥了它——并且可能为通常能够解决 P=NP 问题的算法开辟了道路。

“每位计算机科学家或许都应该更加重视 P = NP 的可能性，但每个人的重视程度可能有所不同，”威廉姆斯说道。“我确实认为这在某种程度上质疑了我们之前对……NP 难题的可解性的一些直觉。我也认为这可能并非最终答案。我不认为 OpenAI 的算法是你能得到的最佳算法。”

计算机科学家接下来的工作

威廉姆斯表示，ETH 的持久性使其在过去十年中被纳入许多科学论文中，如果人工智能实验室声称他们已经证明 ETH 是错误的，那么这些论文就需要重新审视。

“这正是我敦促OpenAI支持召开相关会议的部分原因——它将影响许多研究人员的工作，我们需要弄清楚，除了理解算法之外，接下来会发生什么。我们需要了解，与之前相比，基础架构应该如何改变？”他说道。

在科学问题之前，还有网络安全问题。威廉姆斯表示，改进后的算法可能意味着依赖特定密钥长度的加密系统可能已被破解。因此，他向OpenAI首席科学家丹·罗伯茨提出的第一个问题就是：“他们是否已经确认这会影响任何加密系统……现在是否存在任何不安全的情况？显然，他们已经确认过，并且相当有信心这不会……意味着任何漏洞。”

这种全新的人工智能科学发现范式仍在发展完善中，但威廉姆斯表示，尽管存在一些担忧，尤其是在培养下一代科学家方面，他仍然保持乐观。作为一名从事高等数学研究的计算机科学家，这或许让他比纯数学家更容易适应这种转变。

不过，他表示，人工智能“迫使人们对自己所做的工作更有雄心壮志，并更深入地思考，如果我过去所做的一切现在对人工智能来说都轻而易举，那么我该如何提高我想提出的科学问题的门槛呢？”

来自圈子: Demo俱乐部

demo

指数时间假设（Exponential-Time Hypothesis，简称 ETH）是理论计算机科学和计算复杂性理论中的一个著名基础假设。 [1, 2]

1. 什么是 ETH？

• 提出背景：该假设由计算机科学家拉塞尔·因帕格利亚佐（Russell Impagliazzo）和拉马莫汉·帕图里（Ramamohan Paturi）于 1999年 提出。 [1]
• 核心内容：它断言，像 3-SAT（3-可满足性问题，一种经典的NP完全逻辑难题）这样的问题，在最坏情况下无法在“次指数时间”（subexponential time）内解决。 [1, 2]
• 通俗理解：你可以把它想象成在开一个超级复杂的密码锁，随着密码开关数量的增加，需要尝试的组合呈指数级爆炸。ETH 认为，解开这类问题不存在比“指数级增长”快得多的捷径，暴力搜索或类似的大规模计算代价是无法从根本上绕过的。 [1, 2]
  

2. ETH 在计算机科学中的地位

• 地位：在过去近30年里，ETH 被计算机科学界奉为“底层铁律”之一。
• 广泛应用：全球有数百篇甚至上千篇学术论文，都将“ETH 成立”作为默认前提，去推导图论、组合优化、数据库、计算生物学等领域中各种算法的“计算难度下限”。它比著名的 P ≠ NP 猜想更强、更具体。 [1, 2, 3, 4, 5]
  

3. 近期重大动态（2026年10月）

• 被 AI 宣称证伪：2026年10月26日，OpenAI 与 Anthropic 分别宣布，其内部人工智能模型独立发现了一种可以在“次指数时间”内解决 3-SAT 问题的全新算法，并同步给出了使用 Lean 形式化验证工具检查过的证明，声称推翻了 ETH。 [1, 2]
• 学界现状：这一宣称在计算机科学界引发了巨大的震动与审视。目前该成果仍在全球相关理论计算机科学家（如 Ryan Williams 等人）的严格复核与检验之中，如果最终经受住同行检验并成立，将深刻重塑整个复杂性理论的研究图景。 [1, 2, 3, 4, 5]
• （注：这并不等于证明了 P = NP，也不会直接导致现有主流加密系统瞬间被破解。）
  

demo

• P 问题（Polynomial Time，多项式时间问题）：指那些可以用计算机在“多项式时间”内解决的问题（即计算时间随问题规模 n 增大的速度不会太快，比如 n² 或 n³）。 [1]
• NP 问题（Nondeterministic Polynomial Time，非确定性多项式时间问题）：指那些如果有人给你一个答案，你可以在多项式时间内验证这个答案对不对的问题。例如数独：让你从头解出来很难，但把填好的答案给你，你检查一遍很快就能知道对不对。 [1]
  
• P 与 NP 的关系（P vs NP）：这是计算机科学最著名的未解之谜——“容易验证的问题，是不是也容易解决？”。绝大多数科学家认为 \(\mathbf{P\ne NP}\)（即：有些问题验证起来容易，但想把它解出来注定非常慢）。 [1, 2]
  
• ETH（Exponential-Time Hypothesis，指数时间假设）：由学者 Russell Impagliazzo 和 Ramamohan Paturi 于 1999 年提出，是一个比“P ≠ NP”更强、更具体的假设。它猜想：像 3-SAT（布尔可满足性问题）这样经典的棘手问题，绝对不可能在“次指数时间”（subexponential time，即快过2^o(n) 内被解决，最坏情况下必须付出接近指数级的代价。
  
  

逻辑联系

• 从 P ≠ NP 到 ETH：
  
  • 如果 P=NP 成立，意味着所有能在多项式时间内验证的问题都能在多项式时间内被解开，那么 ETH 必定不成立。
  • 反过来，如果 ETH 成立，那么它自然会强力推导出 P ≠ NP（因为如果连更强的指数级门槛都无法逾越，它当然更不可能缩短到多项式时间）。 [1]
    
• ETH 的作用：
  
  • 在过去近 30 年里，理论计算机科学界、图论、组合优化等领域的数百篇论文，都把“ETH 成立”当作公认的地基，去推导各种复杂性问题的下界。 [1]
    
  
  
  

---

最新重磅动态（2026年10月）

• AI 挑战 ETH：2026年10月26日，OpenAI 与 Anthropic 几乎同时宣称，其内部 AI 模型独立发现并证明了 ETH 是错误的（即给出了针对 3-SAT 问题的次指数时间算法）。 [1, 2]
• 这等于 P=NP 了吗？：并没有。
  
  • 推翻 ETH 只是说明 3-SAT 的求解速度可以比传统的纯指数级稍快一点点（处于次指数区间），但依然远慢于多项式时间（P）。
  • 因此，即使 ETH 被证伪，P ≠ NP 仍然没有被解决，整个互联网的安全加密体系也不会在一夜之间崩塌。
  • 目前这些 AI 给出的证明正处于全球学术界与形式化验证工具（如 Lean 4）的密集复核与审视当中，尚未完全盖棺定论。 [1, 2, 3, 4]