NP 被高估
有人质疑把 NP-hard 问题说成“无可救药地难”是否过头，并举出包管理器、类型系统、SAT 求解器和运筹学等例子：现实中的实例常常通过启发式、近似方法或对问题空间加以约束而被快速求解。讨论者强调，NP-hardness 是一种最坏情况、渐近意义上的概念：它证明的是不存在对所有输入都同样快速的算法，而不是说实际输入就无法求解；它往往只是提醒设计者去简化模型或接受“足够好”的方案。与此同时，也有评论指出 Swift、Debian 的 aptitude 以及正则引擎中确实存在真正的指数级爆炸，因此理解复杂性理论对于判断这些边界仍然至关重要。
关于 NP-hard 的误解
- 几位评论者认为，很多人把“NP-hard”不准确地等同于“在实践中毫无希望”。
- 也有人反驳说，理论表述很明确：NP-hard 的意思是，尚未知道存在一个对 所有 输入都能在多项式时间内运行的算法，而不是说实际子集就一定无解。
- NP-complete 的价值被概括为：它告诉你何时该停止追求通用最优算法，转而寻找启发式方法、特殊情形或近似算法。
最坏情况 vs 典型情况
- 许多 NP-hard 问题只会在少见的、精心构造的实例上爆炸，例如密码学构造、SHA-256 编码上的 SAT、以及某些包依赖图。
- 现实世界中的实例通常具有结构（平面性、低树宽、N 较小、领域约束），这使它们可处理。
- 文中还提到了“相变”和病态边界情况，尤其是在 SAT 和约束问题中。
包管理器与依赖解析
- 形式化模型表明，当你要求单版本约束以及丰富的负约束/版本边界时，依赖解析会变成 NP-hard。
- 各个生态通过以下方式避开困难：
- 放弃唯一性（npm/yarn 支持多个版本）。
- 使用受限策略，比如最小版本选择（Go）。
- 允许有限的多重性（Cargo），再配合启发式方法和兜底机制。
- 在实践中，大多数解析都很快，但某些系统（Debian aptitude、pip、conda）确实会出现“银河级爆炸”。
类型系统与类型检查
- 一些高级类型系统（双向推断、重载、trait）在一般情况下是 NP-hard 或不可判定的。
- 许多语言通过设计来避免最坏行为；另一些语言（尤其是 Swift，但在复杂情况下 C++/Rust/TypeScript 也包括在内）会出现严重的编译时变慢。
- 实现者依赖启发式方法、截断以及设计限制，而不是求解完整的一般问题。
近似、启发式与参数化
- 文中强调了近似算法和启发式方法：TSP、集合覆盖、调度、运动规划、整数规划和课程表编排都有不错的“足够好”方法。
- 固定参数可处理性被特别提到：对于某些 NP-hard 问题，运行时间对一个小参数呈指数级、但对输入规模呈多项式级，这往往非常有效。
- 运筹学、SMT/MIP 求解器以及现代 SAT 求解器被视为成熟技术，常常能在大型真实实例上找到精确或近似最优解。
安全、正则表达式与拒绝服务
- 强大的正则引擎可以编码 NP-hard 行为；灾难性回溯是一种已知的 DoS 向量。
- 有人建议设置超时，但这一点存在争议；许多人主张对不受信任输入使用具有可保证线性时间语义的正则引擎。