NP-高估

NP 难题 2026 年 8 月 13 日 如果您在大学学习过 NP 难题，您的收获可能是这样的：NP 难题在理论上是可以解决的，但在实践中却代价高昂。基本上证明不存在好的算法。至少那是我拿走的。几乎所有与我交谈过的人。而且网上人很多。我不断看到“不，你做不到。这是 NP 难的。等等”的讨论。这个神话很普遍，但这些问题并不棘手。当时，我的教授用戏剧性的话语结束了最后的讲座（我稍微解释一下）： 现在你已经知道，几乎所有有趣的问题都是不可判定的，而剩下的问题，几乎都是 NP 难问题。对于计算机科学项目来说，这就是棺材上的最后一颗钉子。谢什。不确定是否每个人都经历过如此可怕的框架，但这可以解释。这个理论并没有错，但在实践中它往往是无关紧要的。当然，你能想到的任何算法都会在某些输入上崩溃。但您可能会针对 99.9% 的输入获得快速解决方案。或者 100% 的远程相关输入。该理论并不排除这种可能性。从理论上讲，理论和实践没有区别。但在实践中，是有的。 -- Benjamin Brewster 一些突出的 NP 难题： 依赖解析（在包管理器中） 类型检查（并非所有类型系统） 调度旅行商布尔可满足性 (SAT) 对于 (1) 和 (2)，最坏的情况不会发生。我的意思是，安装包和类型检查肯定会很慢。但是，至少在我的职业生涯中，我从未见过银河系爆炸。 (3)和(4)是技术上的优化问题。每个人都知道您可以通过启发式方法来解决这些问题，但您不必牺牲最优性。我们绝对拥有可以在合理的时间内找到可证明的最佳解决方案的工具。没有魔法。没有量子计算机。只是更加努力地思考并提出更好的算法。这就是人们所做的。事实上，在过去的几十年里，算法加速已经超过了硬件的提升。总而言之，本文提到 1991 年至 2015 年间加速了 4500 亿倍。最后但并非最不重要的一点是：NP 难问题的原型甚至 (5) 也经常得到大规模解决。亚马逊每天解决十亿个 SMT 问题。 SMT 是 SAT 的更难版本。 SAT 算法已经变得非常好，现在它被认为是简单的部分。但如果遇到最坏的情况怎么办？你不必等待宇宙的热寂。 HTTP 请求有时也不会返回。添加超时，显示错误消息，...您知道该怎么做。