OpenAI 证明文档首现超线性电路下界,复杂度界仍难啃
thomasahle · x · 2026-11-22
作者 thomasahle 在讨论中指出,OpenAI 公开的证明文档(proof dump)展示了首个超线性电路下界结果——从此前 3.1n 提升到 n√(log n)。他自纠:该下界是针对 E^NP 中一个问题(在 P 中是否开放未知),而非直接的 P 下界,并感叹复杂度下界的进展依然缓慢;要真正解决问题还需推进到 n² 乃至 2^n。
所属事件:OpenAI 证明文件首现超线性电路下界(2 条相关)→
「研究」频道最新
- 一张图测八款 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
- 帽子矩阵一句话讲透:最小二乘拟合中每个数据点权重几何 — RobertTLange · 2026-11-22