复杂度研究者解读 ETH 证伪：比 P≠NP 更强，但实际影响有限
burny_tech · x · 2026-10-27
针对 OpenAI 系统「证伪指数时间假设（ETH）」的声明，bzogrammer 给出技术性解读：
- ETH 是比 P≠NP 更强的命题，它被证伪有点意外，但并不会推翻太多既有结论。
- 新算法的界在技术上属于亚指数级，但形如 2^n 除以复杂 log√ 表达式，仍非常接近指数。
- SAT 求解器几十年来实践表现极好，且早有被证明复杂度低于 O(2^n) 的求解器，因此界略紧并不算太出乎意料。
- 实际含义：对任意 O(k^n)，存在某个算法在 n 足够大时优于任意固定 k——结果很漂亮，但业界早已知道许多 NP 问题实践比理论容易，n 不需要很大该结论在实践上就趋于无意义。
被引用的原始声明指出，该结果已在 Lean 中通过形式化验证，其自然语言证明由系统自行给出。
「研究」频道最新
- 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
- 八校联合提出 Work Agents 统一框架：模型加运行时执行数字任务 — Zishan Xu · 2026-10-27
- OpenAI 称模型已攻克三个数学与量子场论难题,学界正在验证 — billhilf · 2026-10-27