OpenAI 证明文档首现超线性电路下界,复杂度界仍难啃

thomasahle · x · 2026-11-22

作者 thomasahle 在讨论中指出,OpenAI 公开的证明文档(proof dump)展示了首个超线性电路下界结果——从此前 3.1n 提升到 n√(log n)。他自纠:该下界是针对 E^NP 中一个问题(在 P 中是否开放未知),而非直接的 P 下界,并感叹复杂度下界的进展依然缓慢;要真正解决问题还需推进到 n² 乃至 2^n。

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

原文链接 →

「研究」频道最新

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