OpenAI 的突破：50 年问错问题
Efficient algorithms, the Exponential Time Hypothesis, and losing the plot
计算机科学家 Jack Edmonds 在 1965 年试图定义什么是“好”算法，却留下了一个不完美的“多项式时间”标准。这个标准催生了复杂性理论，也导致了“银河算法”的泛滥——那些理论上成立但实际无法运行的算法。最近，OpenAI 宣称在 Satisfiability 问题上取得了“亚指数时间”的突破，被吹捧为 50 年来理论计算机科学的最大时刻。然而，深入分析发现，该算法仅在变量数量超过宇宙原子总数无数倍的荒谬阈值下才有效，对于任何实际问题，它本质上仍是指数级搜索。这暴露了我们过去半个世纪可能一直在回答错误的问题，所谓的效率定义早已脱离了计算现实。
有时候你需要先得到答案，才会意识到自己其实想要的是别的东西。
HN 评论区
46- emil-lp
关于 ETH：现在很多人说 ETH 只是被表述得过于强硬，正确的指数时间假设应该是 SH（可满足性假设）。
它和 ETH 几乎一样，但允许指数项中出现非多项式的改进（这正是 Clause/ChatGpt 所证明的）。
推荐阅读：
- inkysigma
我见过不少对时间复杂度分析实用性的批评，但从未见过哪篇文章描述过我们应该用什么来取代它。时间复杂度分析，就其现有形式而言，即便不完美，也为无限的问题动物园提供了一定的结构，而且组合性相对较好，也相对简单。它也是可处理的，具有数学结构，并且常作为启发式方法很实用（人们通常遇到或想到的算法在这种分析下通常是合理的）。要成为合适的替代品，某物必须满足所有这些特性。如果没有这样的替代品，我们就回到了没有任何框架来分析问题及其复杂性的状态，这似乎比仅仅记住“有时大 O 并不实用”更糟糕。
我所知的唯一更实用的候选者是针对缓存无关算法的缓存复杂度，但那要复杂得多。
- simiones
这位作者似乎严重误解了复杂性理论及其重要性。选择“指数=坏”和“多项式=好”最初可能有些随意，但后来找到了更坚实的基础。
当你算法的逻辑是“生成一个可能的解，验证它是否正确，如果不正确则重复”时，你自动得到的是指数复杂度。而当你面对的问题本身具有某种结构，让你能够直接构造解，或者生成一个相对于问题规模非常小的候选解集（需要人工检查）时，你得到的是多项式复杂度。
现在，确实，对于所有实际的解决问题目的而言，