OpenAI 证明文件现超线性电路下界,Fortnow 称 P vs NP 仍远未解决

thomasahle · x · 2026-11-22

理论计算机科学家 Lance Fortnow(@fortnow)重申其例行提醒:今秋一系列戏剧性进展并未真正推进 P vs NP 问题,反而印证了破解该问题的难度。

用户 thomasahle 在回复中指出,OpenAI 的证明文件(proof dump)确实给出了首个超线性电路下界——从已知的 3.1n 提升到 n√(log n),他认为只要继续推进到 n² 乃至 2^n,问题就能解决。

这是 P vs NP 进展讨论中「乐观派」与「悲观派」的一次交锋:前者看到下界突破的路径,后者认为距离真正破解仍遥遥无期。

所属事件:OpenAI 证明文件首现超线性电路下界(2 条相关)→

原文链接 →

「研究」频道最新

更多「研究」频道 AI 资讯 →