什么是 Hard

在计算机科学领域，“hard”或“NP-hard”是一个术语，用于描述解决特定类型问题的难度。它表示找到该问题的精确解决方案在计算上是不切实际的，即使使用强大且快速的计算机，也要花费不可接受的时间。

NP 复杂度

NP 复杂度类是指一类可以在非确定性图灵机上多项式时间内验证其解决方案的问题。这意味着如果给出了一个候选解决方案，我们可以快速检查其正确性。然而，对于 NP-hard 问题，找到解决方案本身需要花费指数时间。

NP-completeness

NP-completeness 是 NP-hard 问题的子集，它具有一个额外的属性：它们可以将 NP 中的任何其他问题“归约”为它们。这意味着，如果我们能够高效地解决一个 NP-complete 问题，我们就能够高效地解决所有 NP 问题。

NP-hard 问题的例子

NP-hard 问题的例子包括：

• 背包问题：在有限数量的物品中选择一个集合，以最大化其总价值，同时不超过指定的容量限制。
• 旅行商问题：寻找访问一组城市并返回起点的最短路径，同时只能访问每个城市一次。
• 布尔可满足性问题：确定一组布尔变量的赋值，使一组给定的逻辑子句为真。
• 图着色问题：为图中的顶点分配颜色，使相邻的顶点颜色不同。

应对 NP-hard 问题

由于 NP-hard 问题无法在合理的时间内精确求解，因此计算机科学家们已经开发了各种技术来应对它们：

• 近似算法：为 NP-hard 问题找到近似但不是精确的解决方案。
• 启发式算法：使用启发式方法在合理的时间内找到问题的良好解决方案，但不保证其最佳性。
• 枚举：系统地遍历所有可能的解决方案，并选择最优的一个。这仅在问题规模较小的情况下是可行的。
• 并行计算：利用多个处理器或计算机同时求解问题。

NP-hard 问题代表了计算机科学中一个重要且具有挑战性的问题类别。虽然找到它们的精确解决方案在计算上不可行，但计算机科学家们一直在努力开发解决这些问题的实用方法。通过近似算法和启发式算法，我们可以为 NP-hard 问题找到足够好的解决方案，并在合理的计算时间内满足实际应用的需求。