理论计算机学家 Ryan Williams 剖析 P vs NP 三种走向
MIT 理论计算机科学家 rrwilliams(Ryan Williams)针对 P vs NP 问题给出三种可能走向:若在几个月内被解决,几乎必然是 P=NP,且意味着「多项式时间」不符合直觉、需要重新定义更贴切的概念;若 P≠NP,则即使 AI 将数学文献积累加速几个数量级,短期也几乎不可能证明,需先攻克进展寥寥的 P≠PSPACE 或 LOGSPACE≠NP 等更「容易」的问题。
2026-11-23 ~ 2026-11-23 · 4 条相关
- 复杂度研究者 rrwilliams 下注:给出 P vs NP 走向的三种判断 — rrwilliams · 2026-11-23
- rrwilliams:若 P vs NP 近期解决,多半是 P=NP 且「多项式时间」概念需重定义 — rrwilliams · 2026-11-23
- rrwilliams:P≠NP 短期难证,AI 或可将相关文献积累加速几个数量级 — rrwilliams · 2026-11-23
- 理论计算机科学家 Ryan Williams 长文剖析 P vs NP 三种可能结局 — rrwilliams · 2026-11-23