指数时间假设是错误的 [pdf]
一篇来自 OpenAI 的新预印本声称通过为 3-SAT 这一标志性的 NP 完全问题给出次指数时间算法，推翻了指数时间假设。评论者指出，这是一项重大的理论突破，推翻了一个被广泛使用的困难性假设，并且在一定程度上削弱了人们对 P≠NP 的信心，但它距离实用或多项式时间解法仍相去甚远，也并未排除大多数 NP 问题仍可能需要指数时间。讨论的核心围绕着这个时间界到底意味着什么、为什么它不会自动让所有 NP 问题都变成次指数，也不会破坏密码学，以及像这样“银河级”的算法为何仍可能改变我们对可行算法种类的直觉。
与 P vs NP 的重要性及关系
- 许多评论者认为这是一个巨大的理论结果，“与 P vs NP 同一级别”，但强调它并 没有 解决 P vs NP。
- ETH 被推翻意味着一个被广泛使用的假设失效了；很多依赖 ETH/SETH 的既有工作可能需要重新审视。
- 有人将其解读为削弱了对 P≠NP 的信心；也有人认为它其实并没有真正改变什么，只是说明我们对“难”问题的直觉是错的。
结果实际声称了什么
- ETH 认为 k‑SAT（通常是 3‑SAT）需要 约为 2^{Ω(n)} 的时间。
- 这篇论文给出了一个次指数算法，大致为 2^{n / √log n}，因此 ETH 是错误的。
- 讨论串反复纠正一个误解：这 并不能 证明 NP≠EXP 或 NP⊊EXP。
归约以及为什么不能证明 NP 是次指数的
- 关键细节：NP 问题可以在多项式时间内归约到 SAT，但多项式归约可能会使实例规模膨胀。
- 形如 2^{o(n)} 的界并不会自动通过任意多项式归约传递下去；需要的是 2^{n^{o(1)}}。
- 因此，3‑SAT 是次指数的，并 不 意味着所有 NP 问题都是次指数的。
- 但它确实会传递到那些可以线性归约到 SAT 的问题上（例如论文中列出的一些计数问题）。
面向普通人的解释与复杂度直觉
- 多条评论用通俗语言解释了 SAT、NP 和 ETH，强调：
- NP = 可以高效验证（给出一个提示），而不一定能高效求解。
- 次指数时间仍然可能大到不可思议；多项式时间和指数时间之间存在巨大的鸿沟。
实际影响与“银河级”算法
- SAT 求解器专家称这些算法为“银河级（galactic）”：常数项大得离谱，现实中的实例仍然更适合现有求解器。
- 真实的 SAT 实例通常比最坏情况容易得多；预计不会立刻带来性能提升。
更广泛的影响与反应
- 有人认为这会让直觉稍微偏向“也许存在我们尚未想到的巧妙算法”，与较早的看法相吻合，即许多问题可能存在更快的算法。
- 也有人担心复杂度理论中的“高效”是否真的符合现实世界中的效率概念，认为 P vs NP 可能并不是衡量实际效率的一个恰当代理。
- 大家对它对密码学的影响感到好奇并进行猜测，不过讨论串指出，目前还没有明显的密码系统会因这一结果而被破解。