OpenAI 声称 3SAT 亚指数算法，Ryan Williams 等拓扑学家牵头独立评审
AIFlow_ML · x · 2026-10-27
OpenAI 宣称其模型得出 3SAT 界：n 变量问题可在约 exp(n/(log n)^{1/2+o(1)}) 时间内解决——渐近低于任何 2^(cn)，但并非多项式，论文本身也声明这并未使所有 NP 问题亚指数化。
评审安排由 Impagliazzo 和 Paturi（ETH 复杂度假设提出者）以及 Ryan Williams 牵头。评审信明确表示「我们的参与不应被视为对该结论的认证」，且不签 NDA、无报酬、原始数据公开。AIFlowML 评价称这就是独立评审应有的样子。
所属事件:OpenAI 宣布 AI 连获数学、复杂性理论与物理三项重大发现(63 条相关)→
「研究」频道最新
- AI 推翻指数时间假说?附图对比声称的次指数算法与 2ⁿ 增长曲线 — robleclerc · 2026-10-27
- OpenAI 疑似进展触及 3-SAT，指数级难题被指遭挑战 — micoolcho · 2026-10-27
- Google 发布 StreamVibe：能主动捕捉隐含意图的流式视频 agent — google · 2026-10-27
- Qwen-Image-PE：两阶段训练学会视觉设计，prompt 增强提升 7.81 分 — Qwen · 2026-10-27
- OPTIC 实现逐层嵌入千倍压缩，性能几乎无损 — Jiacheng Liu · 2026-10-27
- 蚂蚁国际与西湖大学提出 Trajectory2Gym:为工具使用智能体构造决策可溯源的训练数据 — ant-intl · 2026-10-27