Fortnow 撰文探讨算法结果何时「大概率已最优」
fortnow · x · 2026-10-26
计算复杂性学者 Lance Fortnow 撰文讨论「一个结果何时可能是最优的」这一方法论问题，以多个经典算法为例：
- Metric TSP：1976 年 Christofides 与 Serdyukov 独立给出 1.5-近似多项式算法，很多人试图证明 1.5 是最优（甚至猜测更优近似会导致 P=NP）。但 2020 年 Karlin、Klein、Gharan、Oveis 证明存在 1.5−1/10^36 的多项式近似算法，打破了这一「漂亮数字」信念。Klein 认为真正的下界可能是 4/3。
- 矩阵乘法：作者讨论矩阵乘法指数 ω 的定义细节，指出可能不存在「最小指数」，并对比了矩阵乘法与整数乘法中「漂亮运行时间」与「丑陋运行时间」的结果反差。
文章核心观点：数字是否「漂亮」（如 1.5、4/3）并不能作为最优性的证据，历史上多次被证伪。
「研究」频道最新
- EMNLP 论文用 LLM 规模化测量文本歧义,源自哈贝马斯机器项目 — sebkrier · 2026-10-26
- ELLIS 2026 博士项目开放申请，10月31日截止 — CSProfKGD · 2026-10-26
- 损失曲线对比:换个架构归纳偏置,训练效率差出一截 — mike64_t · 2026-10-26
- 把 LLM 跑给你看:Qwen3.8-27B 全 64 层 3D 可视化 — gamedevsam · 2026-10-26
- Domingos 炮轰 gdb：维数灾难指输入维度而非参数量 — AlexTensor · 2026-10-26
- EuroSafeAI 发布多智能体集群对齐议程：7 大开放问题 — ZhijingJin · 2026-10-26