NP 被高估了吗？实践中的 NP-hard 问题并非不可解
NP 被高估了吗？
NP-overrated
NP过度评价
Aug 13, 2026
2026年8月13日
If you learned about NP-hard problems in university, your takeaway was probably this:
如果你在大学学过NP难问题，你得到的结论可能是这样的：
NP-hard problems are solvable in theory but it's hopelessly expensive in practice. It's basically proven that no good algorithms exist.
NP难问题在理论上是可解的，但在实践中代价高得离谱。基本上已经证明不存在好的算法。
At least that's what I took away. And almost everyone I've talked to. And many people online. I keep seeing "No you can't do it. It's NP-hard. Blah blah" discussions. The myth is pervasive but these problems are not intractable.
至少这是我得到的结论。而且我交谈过的几乎所有人，以及网上的许多人也是如此。我不断看到“不，你做不到。这是NP难的。等等等等”的讨论。这个神话无处不在，但这些问题并非难以处理。
At the time, my professor closed the final lecture with dramatic words (I'm paraphrasing slightly):
当时，我的教授以戏剧性的话语结束了最后一堂课（我稍微转述一下）：
And now you've learned that almost all interesting problems are undecidable and of the remaining ones, almost all are NP-hard. For the project of computer science, that puts the final nail in the coffin.
现在你们已经学到了，几乎所有有趣的问题都是不可判定的，而在剩余的问题中，几乎所有的都是NP难的。对于计算机科学这个项目来说，这给棺材钉上了最后一颗钉子。
Sheesh. Not sure if everyone got such a dire framing but that would explain.
天哪。我不确定是否每个人都得到了如此悲观的框架，但这可以解释。
The theory is not wrong, but in practice it's often irrelevant. Sure, any algorithm you can come up with will blow up on some inputs. But you might get a fast solution on 99.9% of inputs. Or 100% of the remotely relevant inputs. The theory does not rule that out.
这个理论并没有错，但在实践中它常常无关紧要。当然，你能想到的任何算法都会在某些输入上爆炸。但你可能会在99.9%的输入上得到快速解决方案。或者在100%的远程相关输入上。理论并不排除这一点。
In theory, there is no difference between theory and practice. But in practice, there is.
理论上，理论与实践之间没有区别。但在实践中，是有区别的。
-- Benjamin Brewster
-- 本杰明·布鲁斯特
A few prominent NP-hard problems:
几个著名的NP难问题：
- Dependency resolution (in package managers)
- Type checking (not all type systems)
- Scheduling
- Traveling Salesman
- Boolean Satisfiability (SAT)
- 依赖解析（在包管理器中）
- 类型检查（并非所有类型系统）
- 调度
- 旅行商问题
- 布尔可满足性问题（SAT）
For (1) and (2), the worst-case just doesn't occur. I mean, installing packages and type checking can surely be slow. But, at least in my career, I've never seen a galactic blow-up.
对于（1）和（2），最坏情况根本不会发生。我的意思是，安装包和类型检查肯定可能会慢。但至少在我的职业生涯中，我从未见过灾难性的爆炸。
(3) and (4) are technically optimization problems. Everyone knows you can tackle those with heuristics, but you don't always have to sacrifice optimality. We absolutely have tools that can often find provably optimal solutions in reasonable time. There's no magic. No quantum computers. Just thinking harder and coming up with better algorithms. And that's what people have done. In fact, algorithmic speedup has outpaced hardware gains in the last decades. Taken together, this paper cites a 450-billion-fold speedup between 1991 and 2015.
（3）和（4）在技术上是优化问题。每个人都知道你可以用启发式方法来解决这些问题，但你并不总是必须牺牲最优性。我们绝对有工具可以在合理的时间内经常找到可证明的最优解。没有魔法。没有量子计算机。只是更努力地思考并提出更好的算法。而人们已经这样做了。事实上，在过去的几十年里，算法加速已经超过了硬件进步。综合来看，这篇论文引用了1991年至2015年间4500亿倍的加速。
Last but not least: even (5), the archetype of NP-hard problems, is routinely solved at scale. Amazon is solving a billion SMT problems a day. SMT is an even harder version of SAT. The SAT algorithms have gotten so good, it's now considered the easy part.
最后但同样重要的是：即使是（5），NP难问题的典型代表，也经常被大规模解决。亚马逊每天解决十亿个SMT问题。SMT是SAT的一个更难版本。SAT算法已经变得如此之好，以至于现在被认为是容易的部分。
But what if you run into the worst-case? You don't have to wait for the heat-death of the universe. An HTTP request also doesn't come back sometimes. Add a timeout, show an error message, ... you know the drill.
但如果你遇到最坏情况怎么办？你不必等到宇宙热寂。HTTP请求有时也不会返回。添加超时，显示错误消息，...你知道该怎么做。
Comments on Hacker News
Hacker News上的评论
更进一步：量化金融体系
看懂新闻只是起点——沿量化金融路径，把它变成能交付的工程能力