OpenAI 宣称推翻指数时间假设：给 k-SAT 计数找到次指数算法
来源：files.mathhelm.org — 2026-10-25
📋 概述
这是一篇署名 OpenAI 的 67 页论文（10 月 17 日定稿，25 日修订）。它给出一个确定性算法：对任意固定的 k≥2，在 n 个变量、m 个子句的 k-CNF 上精确计算满足赋值的个数，用多项式空间，时间为 (n+m)^{O_k(1)}·2^{n/(log n)^{1/2+o(1)}}；在 m≤Dn 的固定密度情形下进一步收紧到 2^{O(n/√log n)}。由于 #F>0 的判定就等价于 SAT，这直接否证了断言 3-SAT 最坏需要 2^{Ω(n)} 的指数时间假设（ETH）。论文还给出若干推论：独立集、q-着色与完美匹配的计数可在 2^{o(v)} 时间内确定性完成，Max-k-SAT 得到任意精度的次指数近似算法，并在 ENP 上导出一个 Ω(n√log n) 量级的电路下界；作者同时提醒 2^{o(n)} 的界无法通过一般多项式归约传递，因此并不推出 NP 整体可次指数求解。
🔑 核心要点
- 主结果是一条计数算法：对每个固定 k≥2，确定性、多项式空间、时间 2^{n/(log n)^{1/2+o(1)}}，而判定 #F>0 就是 SAT
- 命中要害的对象是 ETH 与 SETH：它们都建立在 k-SAT 需要 2^{Ω(n)} 最坏时间这一前提上
- 技术路线由三块拼成：共享线性摘要的快速计数、低次替换型的构造、以及稀疏多项式方程组公共零点的计数
- 推论覆盖面很广：独立集与 q-着色计数能到 2^{o(v)}，完美匹配能到 2^{o(v+e)}，Max-k-SAT 可任意精度次指数近似
- 还顺手拿到电路下界：存在 ENP 中的语言，其非输入门数在无穷多个 n 上大于 c·n√log n
- 作者明确划定边界：2^{o(n)} 这类界不能经一般多项式归约传递（需要 2^{n^{o(1)}}），所以并不等于 NP 整体可次指数求解
💡 金句
对每个固定的 k≥3，k-SAT 都是标准的 NP 完全问题，而它的指数时间复杂度正是指数时间假设与强指数时间假设的基础。本文通过给出一个次指数时间、多项式空间的确定性计数算法，否证了 ETH。
👍 0
👎 0
← 返回 Lobsters 首页