NP-hard 问题真的无解吗？
NP-Overrated
大学里我们常被灌输 NP-hard 问题在理论上可解但实践中无望的定论，仿佛这是计算机科学的墓志铭。但现实并非如此。在依赖解析、类型检查、调度甚至 SAT 问题上，最坏情况极少发生。现代优化工具如 Gurobi、SCIP 和 Google Optimization 能在合理时间内找到最优解。算法速度的提升甚至远超硬件进步，1991 到 2015 年间实现了 4500 亿倍的加速。就连 Amazon 每天也能处理十亿个 SMT 查询。遇到极端情况？加个超时机制就好，就像处理偶尔失败的 HTTP 请求一样。NP-hard 并非不可逾越的障碍，只是需要更聪明的算法和更务实的工程思维。
理论上，理论与实践没有区别；但在实践中，二者截然不同。
HN 评论区
175- pron
1. 复杂度类的研究目的并不是劝退人们去写某些程序，而是为了理解计算的本质和理论极限。就实践而言，它可以用来指出哪里需要启发式方法。说它被高估了，就像说微积分被高估了，因为大多数人并不需要每天使用它。顺便一提，许多重要问题属于被认为比 NP 难得多的复杂度类（即 NP 完全问题是著名难解复杂度类中最容易的）。例如，我见过有些人吹嘘某种配置语言易于机械分析，因为它不是图灵完备的，而事实上分析它至少是 PSPACE-hard 的。
2. 当某个 NP-hard 问题存在大量在实践中可处理的实例时（如 SAT），其重要性在于这里存在一个非 NP-hard 的子集。事实上，SAT 是 FPT（固定参数可处理 [1]），这是一种“更容易”的 NP 类型，分解法对其有帮助。相比之下，图着色问题被认为不是 FPT。
- Guvante
我觉得这篇文章并没有真正触及使用最广泛的解决方案：
别允许那些难解的情况出现。
依赖管理器往往会直接屏蔽一大类情况，从而实际上消除了整个 NP-hard 空间。
类型系统同样被明确地隔离开来。
诀窍不在于“无论如何都要做”，除非你定义上必须这么做；而在于承认一般问题是“不可能”的，所以要么尽力而为，要么开始排除那些不可能的情况。
- andrewla
非常正确！NP-hard 问题之所以困难，几乎总是与特定问题配置相关的组合爆炸有关——你可以构造出某些实例，配合近似启发式或分支定界求解器，会导致其出现指数级膨胀。但对于大多数实际问题，你并不会遇到那些爆炸性的配置。
对于特定类别的 NP-hard 问题，可能在某种意义上存在某种量化描述。
有趣的是，许多算法（尤其是密码学中的算法）是专门设计用来制造这些组合边缘情况的。一个 SAT 求解器在处理生活中和编程中出现的普通问题时表现会非常出色。但一个 SAT 求解器面对 SHA256 时，表现就不那么好了。事实上，可以说开发密码系统的科学，就是寻找那些对启发式近似具有抵抗力的指数级爆炸的科学。
- tux3
> 对于（1）和（2），最坏情况根本不会发生。我的意思是，安装包和类型检查当然可能很慢。但至少在我的职业生涯中，我从未见过银河系级别的爆炸。
NP-hard 问题很难精确求解，但通常可以高效地获得相当不错的近似解。但有些搜索问题就是非常难，即使是近似求解。如果你曾通过 aptitude 在 Debian 上进行重大升级并保留旧的安装，你就会经常看到它迷失在深远的搜索空间中。
有时 aptitude 需要降级一个包、卸载一个包，或者不安装推荐的包，才能找到正确的解决方案。有许多可能的包可以尝试降级，而每一个都会制造出带有新可能性的全新混乱。这是其他包管理器所没有的，如果你不通过手动找出造成所有困难的那一小部分包来协助它，它的搜索策略确实是不可处理的。
- jvanderbot
我喜欢这个脑洞大开的观点，秉承 TFA 的精神：“你知道吗，旅行商问题在一大类图上是 O(N) 的？”
另一个见解：我经常发现，巧妙的 O(log n) 解决方案会被几个几乎无分支的 O(N) 预扫描彻底碾压，随后是计算机更喜欢的操作，比如连续内存访问和向量运算。
- chupasaurus
> 我的意思是，安装包和类型检查当然可能很慢。但至少在我的职业生涯中，我从未见过银河系级别的爆炸。
上次我遇到 apt 求解器的银河系级别爆炸（Debian Testing 64 位时间转换的最后阶段），内存消耗仅为每分钟 2 GiB。
- not2b
我的职业生涯都在电子设计自动化领域度过，那里几乎所有有趣的问题都是 NP-hard 的，但我们必须解决它们，或者至少近似解决它们。因为现实生活中的问题往往具有结构，只要方法得当，即使理论复杂度很高，非常大的问题也能被精确求解；而当无法找到精确解时，通常也能找到一个不错的界限，这往往是可以接受的解决方案。
销售人员仍然需要规划行程，尽管找到最优解是 NP-hard 的（举一个例子）。没关系，有不错的启发式方法。
- lennoff
有时你并不需要精确解。旅行商问题的度量版本存在近似解，其复杂度为 O(n^3)，产生的结果不会比最优解差 50%；而对于一般情况，存在 O(n^2) 的算法，产生的结果成本至多为最优解的两倍。