Ben Recht 长文:从 Edmonds 的「好算法」看复杂性理论如何遗忘最初的问题
beenwrekt · x · 2026-10-30
Berkeley 教授 Ben Recht 在 arg min 博客发表技术长文,探讨计算机科学史上「未能严格定义效率」的教训。
- 起点:1965 年 Jack Edmonds 提出图最大匹配的巧妙算法,需要论证它是「高效」的,却发现当时没有描述算法效率的语言,只能在论文「Digression」一节中用「good algorithm」来表述
- 由此引出指数时间假说(ETH)与复杂性理论的历史脉络
- 核心批判:应用数学的常见模式——为解决问题搭起巨大的数学建模脚手架,脚手架衍生出新谜题,随后大量后续论文去解谜题,却忘了最初要解决的问题;复杂性理论是这种「遗忘」的最佳案例
- 作者延续其关于傅里叶变换的系列写作风格,技术性强但力求可读
「研究」频道最新
- LIFT 架构让 Transformer 带回循环，数据效率翻倍 — megamor2 · 2026-10-30
- 高斯头替代扩散层:仅用 0.02% 数据让机器人策略推理快至 2 倍 — francoisfleuret · 2026-10-30
- 西北大学Hullman：验证不等于知识，AI科学产出需有人能负责 — JessicaHullman · 2026-10-30
- Humansand 发布 &Tutor：先建「学习者模型」再训教学模型 — techNmak · 2026-10-30
- CATT 基准揭示归因方法为何追溯不到模型的训练数据 — cindy_x_wu · 2026-10-30
- Soham 发布个性化癌症疫苗制造平台，将生产 100+ 种 mRNA 疫苗 — jajoosam · 2026-10-30