rrwilliams:P≠NP 短期难证,AI 或可将相关文献积累加速几个数量级

rrwilliams · x · 2026-11-23

rrwilliams 第二分支:即便 AI 加速研究,P≠NP 也几乎不可能很快被证明。需先解决更「容易」的 P≠PSPACE 或 LOGSPACE≠NP,而这两者进展寥寥;通过电路下界证 NP 不属于 P/poly 更遥远。他建议先证长度 L 的 SAT 实例没有 L^1.01 规模电路,并认为 AI 能把这块几乎空白的文献积累加速几个数量级。

所属事件:理论计算机学家 Ryan Williams 剖析 P vs NP 三种走向(4 条相关)→

原文链接 →

「漫话AGI」频道最新

更多「漫话AGI」频道 AI 资讯 →