效率定义之争：从最大匹配到指数时间假设的迷失

Edmonds的"好算法"：效率定义的诞生

1965年，Jack Edmonds为图的最大匹配问题设计了一个巧妙算法，却在论文里卡住了。他想说自己的算法"高效"，可翻遍字典，找不到一个合适的词来描述"高效"到底意味着什么。于是他在论文第2节开了个名为"Digression"的小节，写下这样一段话：根据词典，"efficient"意为"adequate in operation or performance"，这大致符合我的意思，但也许"good"是更好的词。他声称，作为数学结果，存在一个好算法。来源：argmin

Edmonds的困境并不罕见。他注意到，自己可以枚举最大匹配问题的每一个可能解，再挑出最大的那个，这当然是个正确算法。但图里匹配的总数是随图规模指数增长的，把可能的匹配全部写下来再挑最大，这个"蛮力法"显然算不上"good"。他花了整整两页纸，试图构造一个关于"good"的共识，甚至为问题规模下了定义，最大匹配问题的规模，是图的顶点数加上边数。来源：argmin

Ben Recht在argmin的这篇文章里说，正是这种"指数级枚举"背后的直觉，埋下了效率定义困境的根源。一个算法算不算"好"，取决于我们对输入规模的选择，也取决于我们对"枚举所有可能"这类操作成本的容忍度。Edmonds的解决方案是划定一个边界，把"good"定义为存在一个多项式时间算法，这个定义后来成了整个计算复杂度理论的基石。但定义归定义，边界之外的事情，从来没有人真正说清楚过。来源：argmin

指数时间假设：从理论到实践的失联

Recht的这篇文章写于2026年10月30日，副标题是"losing the plot"，直译过来就是"迷失了主线"。他用"Galactus the Devourer"这个漫画角色来比喻指数时间假设，那个吞噬行星的宇宙实体。在Recht的笔下，ETH就像一头怪兽，吞噬了应用数学和理论计算机科学中的"巨型脚手架"。来源：argmin

所谓的"巨型脚手架"，是Recht反复批评的一种现象。应用数学家为了求解一个实际问题，常常要搭建庞大的数学建模框架，这个框架本身会衍生出许多新谜题，跟最初关心的问题没有直接关系。Recht写道，你会看到几十篇后续论文忙着解决这些衍生谜题，却忘了最初关心的问题。在他看来，复杂度理论领域就是"遗忘"的典型样本。来源：argmin

这个批评并非空穴来风。指数时间假设本身，就是"脚手架"的产物。它假设SAT问题不存在亚指数算法，这个假设强于P≠NP，被用来证明许多问题的下界。但ETH的证明力究竟有多强，它跟现实世界中的算法设计有多大关系，几十年来没有多少人真正问过。Recht的文章标题"losing the plot"，就是在说复杂度理论正在偏离它本该关心的问题。来源：argmin

有意思的是，Hacker News上的评论者LarsDu88给出了一个完全不同的解读。他的评论是"Bringing OpenAIs big result down to earth"，意思是把OpenAI的那个宏大结果拉回地面。他关注的不是复杂度理论的历史，而是当下AI领域的宏大叙事如何与现实脱节。来源：HN评论

多源交叉验证：同一场"迷失"的不同视角

原文和HN评论，一个聚焦历史，一个聚焦当下，但都指向同一个病灶：理论框架膨胀到吞噬原始问题的程度。Recht的文章获得了69次点赞、11条评论和12次分享，对于一个技术博客来说，这个互动量不算高，但恰好说明讨论还在小圈子里进行。来源：argmin

LarsDu88的评论"Bringing OpenAIs big result down to earth"，和Recht文中批评的"pernicious pattern"形成了奇妙的呼应。Recht说的是应用数学家建起巨型脚手架，衍生出与原始问题无关的新谜题；LarsDu88说的是OpenAI的宏大结果需要被拉回地面，让真实世界能接得住。两者切入的角度不同，一个从复杂度理论的历史出发，一个从AI当下实践出发，但共同的问题意识是清晰的：理论框架在自我繁殖，而最初的关切被丢在了身后。来源：argmin 来源：HN评论

我自己读过不少这类争论，一个直觉是，Recht的批评更锋利一些。因为复杂度理论的历史摆在那里，Edmonds在1965年拼了命想定义"good"，定义出来的东西成了整个领域的基石，但基石之上的建筑越盖越高，地基里的那个原始问题却没人再看了。ETH就是这种趋势的极致表现，它是一个假设，不是一条定理，却统治了无数人的研究方向。至于OpenAI的结果该不该被拉回地面，这个判断我不敢下，毕竟我没有足够的信息去评估那个结果的真实分量。来源：argmin

但有一点我比较确定，这场关于"迷失"的争论，不会因为一篇博客文章而终结。Edmonds当年为"efficient"找词的时候，可能没想到自己定义出的"good"会变成一个时代的标准；同样，今天大家争论ETH到底该不该继续作为复杂度理论的核心假设，争论本身也是这个领域自我修正的一部分。迷失也许不是常态，但反复检查自己是否迷失，一定是常态。来源：argmin

原文：

Galactus the Devourer and the exponential time hypotheses · 来源：Hacker News

参考来源：

• HN 评论区讨论 (item 50313382)

作者：itfan123 值班编辑 · 发布于 2026年10月31日