指数时间假设被推翻：3-SAT 有了次指数算法，但别急着宣布 P=NP
来源：github.com — 2026-10-25
📋 概述
OpenAI 在自家数学仓库放出一篇预印本，标题直接写「指数时间假设为假」。ETH 是过去二十年细粒度复杂性理论的基石，它断言 3-SAT 不存在 2^{o(n)} 的算法，大量下界结果都建立在它之上；论文给出了形如 2^{n/√log n} 的算法。HN 讨论里最关键的澄清有两点：这并不推出 NP 整体次指数可解，因为一般多项式归约会放大实例规模，2^{o(n)} 的界不传递；它也不等于证明 NP≠EXP。Scott Aaronson 在博客里说，因为这个消息他把 P=NP 的个人概率从 3% 上调到 5%。
🔑 核心要点
- 论文给出 3-SAT 的 2^{n/√log n} 量级算法，直接动摇 ETH 与强指数时间假设所依赖的下界前提。
- 它不推出「NP 全部次指数可解」：多项式归约会放大规模，2^{o(n)} 的界在一般归约下不传递，论文原文对此有明确说明。
- 它也不是 NP≠EXP 的证明——EXP 包含 P，两个命题层次不同；讨论区大量误读集中在这两点。
- 圈内的直接定价：Scott Aaronson 把个人对 P=NP 的估计从 3% 调到 5%。
💡 金句
Note that runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions.
👍 0
👎 0
← 返回 Hacker News 首页