Ben Recht 长文溯源：复杂性理论如何忘了最初要解的问题

paraschopra · x · 2026-11-14

这是上条 3SAT 争议的原始出处：Ben Recht 在 arg min 博客发表《Galactus the Devourer》，讨论计算机科学史上「未能严格定义效率」的问题。文章从 1965 年 Jack Edmonds 为最大匹配算法寻找「高效」的数学语言讲起，指出应用数学常见的一种模式：为解决原问题搭建的数学脚手架会催生新谜题，随后大量后续论文只顾解谜题却忘了原始问题——复杂性理论就是最典型的例子。文章借此批评 OpenAI 近期 3SAT 亚指数时间证明的实际意义：其优势仅在远超物理可存在的输入规模上成立。