文章指出，人们常误以为NP难问题在现实中无法解决，但实际上理论上的最坏情况并不影响大多数实际应用。许多NP难问题（如依赖解析、类型检查）在绝大多数输入上都能快速求解，因此不应被理论吓倒。

标题：NP问题被高估了

如果你在大学学过NP难问题，你大概会得出这样的结论：NP难问题理论上可解，但实际计算成本高得离谱，基本上已被证明不存在高效算法。至少我当初是这么理解的，和我聊过的人以及网上许多人也这么认为。我经常看到“不行，这做不到，因为它是NP难问题”之类的讨论。这种误解很普遍，但这些难题并非无法解决。

当时，我的教授在最后一节课上以戏剧性的话语结束（我稍作转述）：“现在你们知道了，几乎所有有趣的问题都是不可判定的，而剩下的问题中，几乎全是NP难问题。这对计算机科学项目来说，等于钉上了最后一颗棺材钉。” 这种悲观的表述或许解释了为什么误解如此根深蒂固。

理论本身没错，但在实践中往往无关紧要。当然，任何算法在某些输入上都会崩溃，但你可能在99.9%的输入上得到快速解，或者100%的相关输入上都能高效运行。理论并不排除这种可能性。正如本杰明·布鲁斯特所说：“理论上，理论和实践没有区别；但实践中，区别是存在的。”

几个著名的NP难问题包括：依赖解析（如包管理器）、类型检查（并非所有类型系统）、调度问题、旅行商问题以及布尔可满足性问题（SAT）。对于前两者，最坏情况几乎不会出现。安装包或类型检查可能慢，但在我职业生涯中从未见过灾难性崩溃。调度和旅行商问题本质上是优化问题，大家都知道可以用启发式方法处理，但不必牺牲最优性。我们有工具能在合理时间内找到可证明的最优解，这并非魔法或量子计算，而是通过更深入的思考和更优的算法实现的。事实上，过去几十年算法加速已超过硬件性能提升。一篇论文指出，1991年至2015年间，算法速度提升了4500亿倍。

最后，即使是NP难问题的典型代表SAT，也能大规模常规求解。亚马逊每天解决十亿个SMT问题（SMT是SAT的更难版本）。SAT算法已如此出色，以至于它现在被视为容易的部分。万一遇到最坏情况怎么办？你不需要等待宇宙热寂。HTTP请求有时也会超时。加个超时设置，显示错误信息——你知道该怎么做。

根据评论内容，总结如下：

核心观点：NP难问题在实践中并非不可解决，关键在于放松约束或利用问题结构。

1. 理论上的NP难不等于实际不可解 - 多数评论认为，NP难问题的理论最坏情况在实践中很少出现。实际应用中的问题往往具有特殊结构，可通过启发式方法或近似算法高效求解。 - 关键引用： - "The general version of a problem being NP-complete doesn't mean that cases of practical interest are all necessarily intractable." (WCSTombs) - "What makes NP-hard problems difficult is almost always the combinatorial explosion related to specific problem configurations... But for most practical problems you don't reach those explosive configurations." (andrewla)

2. 实践中的常见策略：放松约束、使用启发式、限制问题空间 - 评论指出，解决NP难问题的常用方法包括：放弃最优性（使用近似算法）、限制问题子集（如包管理器简化依赖条件）、利用启发式剪枝、以及针对特定问题设计高效算法。 - 关键引用： - "Package managers are designed the way they are because of the inherent NP-hardness, not despite it... NPM, yarn etc drop 3) which makes it not NP hard. Go limits itself to minimum version selection which admits a linear time solution." (porridgeraisin) - "Once you admit approximations the theoretical problem trades places with a more interesting one: what is the Pareto frontier of loss vs complexity?" (esafak) - "In many cases NP-Hard problems may be approximated with a guaranteed lower bound of accuracy." (hingler36)

3. 对文章观点的批评：过度乐观 - 部分评论认为，文章在纠正“NP难=不可解”的误解时，走向了另一个极端，错误地声称可以“不牺牲最优性”地解决NP难问题。实际上，实践中必须牺牲最优性或通用性。 - 关键引用： - "The author justifiably attacks the notion that 'NP-hard' == 'too hard to solve in practice', but then makes the opposite error... You have to sacrifice optimality." (sfink) - "No, we absolutely do not [have tools that can find provably optimal solutions in reasonable time]. Again, not unless someone has secretly come up with a constructive proof of P=NP." (sfink)

4. 现实案例：包管理器、类型检查、正则表达式等 - 评论列举了多个实际例子，说明NP难问题在特定场景下可能遇到困难（如Swift类型检查、旧版Debian的aptitude），但通常通过设计约束（如Go的MVS）或启发式方法得以解决。 - 关键引用： - "Swift was infamous of having exponential time type inference that made expressions like "foo" + "bar" + "baz" + "qux" + 123 take literal minutes to fail with a compiler error." (murderfs) - "Sometimes aptitude needs to downgrade a package... its search strategy is genuinely intractable if you don't help it along." (tux3)

5. 对NP难理论价值的肯定 - 有评论强调，NP完全性理论的价值在于指导算法设计者选择正确方向（如放弃精确算法、转向启发式或近似算法），而非阻止实践。 - 关键引用： - "The primary application of the theory of NP-completeness is to assist algorithm designers in directing their problem-solving efforts toward those approaches that have the greatest likelihood of leading to useful algorithms." (tzs, 引用Garey & Johnson)

总结： 评论普遍认为，NP难问题在实践中可通过放松约束（如近似、启发式、限制问题空间）有效解决，但文章对“不牺牲最优性”的表述过于乐观。理论NP难性应指导实践策略，而非成为障碍。