NP-hard 问题真的无解吗？
NP-Overrated
大学里我们常被灌输 NP-hard 问题在理论上可解但实践中无望的定论，仿佛这是计算机科学的墓志铭。但现实并非如此。在依赖解析、类型检查、调度甚至 SAT 问题上，最坏情况极少发生。现代优化工具如 Gurobi、SCIP 和 Google Optimization 能在合理时间内找到最优解。算法速度的提升甚至远超硬件进步，1991 到 2015 年间实现了 4500 亿倍的加速。就连 Amazon 每天也能处理十亿个 SMT 查询。遇到极端情况？加个超时机制就好，就像处理偶尔失败的 HTTP 请求一样。NP-hard 并非不可逾越的障碍，只是需要更聪明的算法和更务实的工程思维。
理论上，理论与实践没有区别；但在实践中，二者截然不同。