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」频道最新
- Josh Purtell 反驳:250k 页不等于证明不优雅 — JoshPurtell · 2026-11-23
- 一张图概括 AI 社区最大的分歧:某个经典观点交锋 — Neurogence · 2026-11-23
- 网友喊话 Anthropic:公开 agent 攻克千禧年难题的完整对话轨迹 — _arohan_ · 2026-11-23
- LeCun 引苏格拉底反书写典故回应 AI 会损害人类能力的担忧 — ylecun · 2026-11-23
- ENIGMA 问答实录:开放数据为何让阿尔茨海默 AI 分类快速突破 — PTenigma · 2026-11-23
- Mustafa Suleyman 对谈赫拉利:AI、意识与人类的未来 — krishnan · 2026-11-23