OpenAI 论文宣称推翻指数时间假说，给出 3-SAT 亚指数算法
burny_tech · x · 2026-10-29
OpenAI 发布论文《The Exponential Time Hypothesis Is False》，声称推翻计算复杂性理论中的指数时间假说（ETH）——该假说认为判定 n 变量 3-SAT 在最坏情况下需要 2^{Ω(n)} 时间。要点：
- 核心结果：给出一个确定性算法，对任意 k-CNF 公式精确计数满足赋值。对每个固定 k≥2，在 n 变量、m 子句上，运行时间为 (n+m)^{Ok(1)} · 2^{n/(log n)^{1/2+o(1)}}，空间为多项式级，即亚指数时间。
- 意义：计数为零即意味着公式不可满足，因此该算法同时解决了 3-SAT 判定问题，直接反驳 ETH。这是渐近最坏情形界的理论证明，而非实测运行时间。
- 技术思路：将精确计数重组为可从按组的小规模求和恢复的形式，利用共享线性摘要（shared linear summaries）、构造低度替代形式、稀疏多项式方程公共零点计数等手段（论文 64 页，附多个附录）。
- alphaXiv 用「100 个开关约 1.27 万亿万亿万亿种组合」的比喻科普了 3-SAT/ETH 为何重要；该声明若成立将动摇大量以 ETH/SETH 为基础的复杂性结论，学界尚待检验。
「研究」频道最新
- 仿真满分真机 0 成功:商汤等团队评测 GPT-6-Astra 揭具身分数水分 — jiqizhixin · 2026-10-29
- GPT 复核论文数据:DeepSeek 第二阶段涨幅被严重低估 — teortaxesTex · 2026-10-29
- 给冻结的 72B 模型插“知识卡带”：拔掉后 AI 诚实地答不知道 — Nearby_Indication474 · 2026-10-29
- 鸡尾酒会反向图灵测试:人类词准确率 0.71,最强语音模型 0.54 追不上 — cloud_kj · 2026-10-29
- K-Dense 开源 177 项科学技能,把 Claude Code 变成科研助手 — alvelda · 2026-10-29
- 斯坦福团队发布 SOTA 提示词优化框架与无监督提示性能度量 — BrihiJ · 2026-10-29