10月26日,OpenAI 宣布其内部模型给出了存在27年的"指数时间假设"(ETH)的反驳,公开了一篇67页、署名只有 OpenAI 的论文;几小时后,Anthropic 发布了一篇署名只有 Claude 的论文,用完全不同的方法得出同一结论,两家都附上了经软件逐行核对的 Lean 形式化证明。微博哔哩哔哩
结论要分三层说。ETH 被推翻不等于 P=NP:AI 做到的是把 3-SAT 从"必须指数时间"降到"亚指数时间",而亚指数仍然是超多项式。截至11月22日,独立审查仍在进行,ETH 的两位提出者与 MIT 教授瑞安·威廉姆斯参与组织核验,同时明确"参与核验不等于背书"。第三层更要紧:这次被挑战的是整个细粒度复杂性领域赖以立论的前提,一旦坐实,数百篇论文的下界结论要重估,但这既不意味着 SAT 求解器明天起飞,也不意味着 P vs NP 有了答案。 这条10月的结果在11月下旬重新刷上热榜,导火索是黎曼猜想:11月20日,Anthropic 的数学家 Levent Alpöge 公布了与 Claude 合作得到的 RH 证明——没有论文,只有一个约1700万行的 Lean 代码库,第二天 Lean 与 Mathlib 社区就给出"full confidence"的联合声明。验证一天完成、人类理解为零,"AI 下一个撞开的会不会是 P vs NP"于是重新成了追问的焦点。微博知乎
27年的"承重墙",被推倒的是哪一块
3-SAT 是一道开关谜题:一排只能开或关的开关,配上一批各涉及三个开关的规则,问有没有一种摆法让所有规则同时过关。找答案极难,查答案极易,这正是 P vs NP 问题里 NP 类问题的典型结构。1971年,库克证明 SAT 是 NP 完全问题,于是整个 P vs NP 可以归结为一句话:开关谜题到底能不能"算得快",也就是多项式时间。知乎
ETH 没有断言"必须逐个试完所有配置",它赌的是更硬的一件事:存在常数 δ>0,任何算法求解 3-SAT 都至少需要 2^(δn) 时间,即不存在 2^(o(n)) 的算法。这条1999年提出的假设近30年被当作前提使用:Anthropic 方面统计,至少有一项结果只在这组假设下成立的论文超过800篇;OpenAI 的说法是横跨图论、计算生物学、数据库和计算几何的数百篇。它好用是因为2001年的稀疏化引理:再复杂的 k-SAT 也能拆成数量不多的稀疏公式,团、独立集、顶点覆盖、图着色这些看似无关的难题从此和 3-SAT 拴到同一根绳上,"能否做到亚指数时间"同进同退。哔哩哔哩知乎
四十年间人类算法打的是压底数的接力赛。1985年莫尼恩与施佩肯迈尔以 1.618^n 首次严格跑赢穷举的 2^n;1997年帕图里、普德拉克与扎恩提出 PPZ 算法,底数降到约 1.587;1998年加入萨克斯后升级为 PPSZ,对唯一解公式期望时间约 1.3071^n;2011年赫特利证明 PPSZ 的界对一般 3-SAT 也成立,纪录来到 1.30704^n。此后只在小数点后第五位以后挪动,2026年7月的最新分析停在 1.307031578^n,像在逼近一堵看不见的墙。知乎

亚指数从哪来:两条路线,同一道裂缝
OpenAI 的模型绕开了分治。它把"数开关方案"写成一个带参数 T 的多项式:T=0 时正好是原题,T 取几个特意构造的位置时题目几乎能分组计算,只需额外固定少量组与组之间的共享信息;算出这些点上的数值和若干阶导数,再用多项式插值反推 T=0 处的答案。奇妙的是,这些中间量可以是负数,也可以不是整数——它们不再代表"有多少种开关摆法",只是算账用的数。知乎
Anthropic 的论文把公式看成一张网,走法不同,却同样靠带负号的相消拆网,关键工具是1818年前后被发现的八平方恒等式。两篇论文给出的时间上界都是 n/(log n) 的分数次幂量级:指数部分相对变量数的比例随规模趋于零,意味着底数可以任意接近1,这正是 ETH 说不可能的事。需要留意,OpenAI 的 Lean 版本只证到稍弱的界,与手稿相差一个双重对数因子,但同样足以否定 ETH。知乎

公开证明、机器验证与人类理解,走到哪一步
时间线不能压缩成"今天已坐实"。OpenAI 称自然语言反驳产于10月16日,次日完成形式化,公开 PDF 标注10月25日修订,公告是10月26日;Anthropic 披露其 Claude 模型也在10月16日独立找到核心算法,过程中没有人工参与。微博
机器验证覆盖的范围需要抠字眼:官方范围说明明确区分了两个层次——Lean 覆盖的是规范编码输入上的精确计数、次指数时间和多项式空间,10月25日手稿给出的更紧上界不在其中,两者指数项相差一个双重对数因子。还有一处缺口:OpenAI 没有把从自身计算模型到标准图灵机模型的归约步骤形式化,这一环节由其他研究者在11月2日至5日用 Lean 补上。知乎
审查机制本身是这次事件里最值得记录的部分。三位审查学者不签保密协议、不取报酬,要求 OpenAI 公开全部原始数据并资助相关学术会议,两项要求都得到同意;他们同时在公开信中说明,组织审查不应被当作对主张的认证。另一个团队得出同类结论,与外部研究者成功复核第一份论证是两种不同的证据——两份证明是否共享关键思路、是否存在相同盲点,仍需要比较。福特诺在博客里写,他没有亲自验证,但认为现在可以比较放心地认为 ETH"完蛋了",并提醒大家:那些以 ETH 为前提的结论并没有被证伪,只是失去了依据。知乎知乎

亚指数离多项式,还差着一个数量级
ETH 倒了不等于 P=NP,甚至不等于所有 NP 问题都能亚指数求解。 次指数仍可能比任何多项式增长得快,这一主张不能被读成已经解决 P 与 NP;而把别的难题归约成 3-SAT 时,题目规模往往会膨胀得比原题大得多,SAT 上的次指数保证未必能还原成原问题上的次指数保证。知乎
用一个只用于区分类别的例子能说明这道台阶有多宽:2^(√n) 属于次指数,它依然不是多项式时间。在百万开关量级的题目上,AI 做到的这一步只是让工作量翻倍所需的开关间隔比眼下多出"寥寥几个",而多项式时间要求这个间隔一口气涨到几十万个开关。知乎微博
渐近优势也不等于现实可用。Anthropic 论文自己算过:对规则数为 5n 的公式,这个上界要到变量数 n 超过 10 的 10000 次方才能胜过穷举,而可观测宇宙的原子总数不过约 10 的 80 次方;论文直言,这一结果对实际求解什么也说明不了。知乎

承重墙倒了,为什么 P vs NP 反而更需要新方法
P vs NP 至今没有答案,不是缺算力,而是缺能跨过证明障碍的工具。标准复杂性理论已经找出三道横在证明路上的障碍:相对化、自然证明、代数化——无论最终答案是 P=NP 还是 P≠NP,都必须发明绕开它们的新方法。这次 AI 的成果恰好落在障碍管不到的那一侧:它给出的是算法上界,而不是下界。上界可以构造出来逐行检查,下界要否定所有可能的算法,这才是撞上那三堵墙的方向。福特诺11月的态度代表了这种区分:他已经不猜 AI 下一个会证明什么,但仍认为 P vs NP 需要新的方法。知乎知乎
同一个突破在两侧同时生效。按 Anthropic 的统计,800多篇论文至少有一项结论依赖这组假设,“k-团几乎只能逐一尝试”“树宽算法已经最优"这类判断要重新找依据;反过来,团、独立集、顶点覆盖第一次从"只能这么慢"里放出来,获得了比 2^(δn) 更快的空间,δ 可以任意小。威廉姆斯多年前建立的联系此时显出价值:足够快的 SAT 算法可以用来反推电路规模下界,若这次的构造成立,就能推出某些问题所需电路规模无法被输入长度的任何固定倍数限制住——一边让过去的"不可能"失去依据,一边又证明新的"不可能”。知乎
至于 P=NP 本身,威廉姆斯对 TechCrunch 的说法代表了学界主流的判断:这次结果动摇了不少直觉,每个计算机科学家都该给"P=NP 可能成立"多留一点心理空间,但他同样认为 AI 给出的解法大概还不是终点,P=NP 依然像"天上掉馅饼的美事,美好得不太可能成真"。作为克雷数学研究所的千禧年大奖难题之一,P vs NP 截至11月22日仍被官方标注为未解决。微博知乎
短期内谁会受影响,以及该盯什么
对普通用户和工业界,短期影响接近于零。芯片验证、物流排程每天依赖的 SAT 求解器处理的是现实中带有特定规律的问题,靠的是日积月累的工程技巧;福特诺的评价同样适用于此:新解法的思路有希望,但不会给工业界的实际软件带来多大改变。真正被推到台面上的是科研流程本身——这次由 AI 给出反例、机器先行验证、人类理解滞后,"发现—形式化—公开审查"这条科研链路被整个推到了一个新的位置:值得围观的不只是一个假设会不会倒,而是它被推到了什么位置。微博
值得盯的观察信号有三个:三人审查小组是否给出正式结论;手稿更紧上界是否补齐 Lean 形式化;这套代数改写与带负号相消的技术能否迁移到别的 NP 难题上。ETH 的价值在于它用27年教会学界把几百个问题拴到同一根绳上,现在绳头被 AI 剪断,地图需要重画——而 P vs NP 仍是这张地图之外最宽的那道鸿沟。
当前文章无评论,是时候发表评论了