理论计算机科学家 Ryan Williams 长文剖析 P vs NP 三种可能结局
rrwilliams · x · 2026-11-23
MIT 理论计算机科学家 Ryan Williams 在长推中梳理 P vs NP 问题的几种可能走向:
- 若 P≠NP:他认为即使 AI 加速数学研究,短期也几乎不可能证明。需要先解决更"容易"的 P≠PSPACE 或 LOGSPACE≠NP,而这些问题目前进展极少;通过电路下界(证明 SAT 在长度 L 的实例上没有 L^1.01 规模的电路)来证明 NP∉P/poly 则更加遥远。
- 第三种可能:P vs NP 或许无法在 ZFC 等标准数学体系内解决——但他认为这是最不可能的选项,因为看不出该问题在逻辑上为何比 ETH、"SAT 不在线性时间对数空间内"等相关命题更"复杂"。他提到 NP∉P/poly 由于"计算机是无限描述"可能更容易受独立性结果影响,但那是另一个坑。
所属事件:理论计算机学家 Ryan Williams 剖析 P vs NP 三种走向(4 条相关)→
「漫话AGI」频道最新
- Mustafa Suleyman 对谈赫拉利:AI、意识与人类的未来 — krishnan · 2026-11-23
- 黎曼猜想 Lean 证明编译通过,数学界迎来深度学习时刻 — benno_krojer · 2026-11-23
- Polymarket:美国年底前通过 AI 安全法案概率仅 10% — Polymarket · 2026-11-23
- OpenAI 首席科学家警告:2027 年起 AI 研究突破或呈雪崩式加速 — Polymarket · 2026-11-23
- AI 审出顶级经济学论文大量形式缺陷,马斯克转发附议 — elonmusk · 2026-11-23
- AI 冲击学术界争论:资助学术是为正外部性,不是为智性僧侣造饭碗 — shakoistsLog · 2026-11-23