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 条相关)→
「研究」频道最新
- OpenAI 证明文档首现超线性电路下界,复杂度界仍难啃 — thomasahle · 2026-11-22
- 一张图测八款 VLA:仅 3 个答对,ERQA 基准遭质疑题目本身存疑 — giffmana · 2026-11-22
- Fleuret:AI 是神谕而非解释者,人类能懂的数学将微不足道 — francoisfleuret · 2026-11-22
- Vovk 新论文证明概率非随机对象在通用测度下趋近于零 — _onionesque · 2026-11-22
- AI 生成黎曼猜想证明,AI 又自动生成了驳论文:学术圈争论全自动化 — zetalyrae · 2026-11-22
- François Fleuret 灵魂发问:梯度是不是日本人——被问了绝不沉默 — francoisfleuret · 2026-11-22