Fortnow 撰文回顾 3SUM/APSP/ETH 猜想在复杂性理论中的角色
fortnow · x · 2026-11-02
理论计算机科学家 Lance Fortnow 在 Computational Complexity 博客发文，借旧文重刊讨论 3SUM、APSP 与指数时间假设（ETH）等经典猜想为何被广泛相信。
- 3SUM 问题：给定整数数组判断是否存在和为 0 的三元组，已知最优算法 O(n²)，普遍猜想不存在 subquadratic 算法；约有 15-20 个 3SUM-complete 问题，要么全部可亚平方求解、要么全部不行，学界相信是后者。
- 类比 P≠NP 的论证方式：长期无数人攻而不下、归约链的普适含义，这类「非数学证据」支撑着猜想共同体。
- 文章开头以「假设 OpenAI 与 Anthropic 近期结果中的证明成立」为前提，显示作者将 AI 产出的数学证明纳入讨论框架，探讨了以历史视角理解当下证明复杂性问题的意义。
「研究」频道最新
- 引用 Thurston 1994 年旧文：定理署名文化或阻碍数学进步 — alexbilz · 2026-11-02
- AI 文本检测研究:输入输出长度比对漏检率影响最多 5% — amplifiedamp · 2026-11-02
- 博主提出持续学习架构设想：rollout 中更新权重+周期性离线精炼 — joey072shx · 2026-11-02
- L3G-World：单图实时生成无限世界，3D 高斯记忆保一致性 — Crazy-Repeat-2006 · 2026-11-02
- LLM 可控性成生物设计利器，通用模型胜过专用模型？ — chaitjo · 2026-11-02
- Epoch AI 图表产出年增 1.6 倍，11 月却归零被调侃"撞墙" — SamuelAlbanie · 2026-11-02