什么是 hard

在计算机科学中，hard 是指一个问题或计算任务很难在多项式时间内解决。该概念由库克和莱文在 1971 年提出，他们提出了 NP 完全性理论，该理论刻画了最困难的 hard 问题类别。

NP 完全性

在 NP 完全性理论中，问题被分为以下两类：

NP 问题：可以通过非确定性图灵机在多项式时间内解决的问题。

NP 完全问题：NP 问题中，在多项式时间内可被任何其他 NP 问题归约的问题。

换句话说，NP 完全问题是在 NP 中最困难的问题，因为它们可以用于解决任何其他 NP 问题。目前已知的 NP 完全问题有数千个，涉及各种领域，如组合优化、图论、数论和加密学。

hard 问题的例子

以下是一些著名的 hard 问题的例子：

旅行商问题

给定一组城市及其之间的距离，找到访问每个城市恰好一次并返回起始城市的最小总距离。

背包问题

给定一组物品，每个物品都有重量和价值，以及一个容量限制的背包，决定将哪些物品放入背包中以实现价值最大化。

子集和问题

给定一组整数，确定是否存在一个非空子集其元素之和为零。

并非所有问题都是 hard

值得注意的是，并非所有计算任务都是 hard。一些问题可以在多项式时间内求解，这意味着可以使用高效算法在合理的时间内找到解决方案。

例如，排序一组数字、查找字符串中的特定模式或求解一元一次方程组都是可以在多项式时间内解决的问题。

解决 hard 问题的技术

虽然 hard 问题无法在多项式时间内有效求解，但有几种技术可用于近似解决方案或处理其复杂性：

• 启发式算法：用于在合理的时间内找到近似最优解的算法。
• 近似算法：提供解决方案，其质量与最优解决方案之间的差异在可接受的范围内。
• 参数化复杂性：分析 hard 问题的可解决性的方法，将问题分解为更小的、更容易解决的部分。

理解 hard 的概念对于计算机科学和解决复杂计算问题至关重要。通过意识到某些问题的固有难度，我们可以寻找创新方法来处理它们的复杂性并开发有效且实用的解决方案。