NP ， NP-Complete和NP-Hard 有什么区别？
我知道网上有很多资源。我想阅读你的解释，原因是它们可能与那些不同，或者有些东西我不知道。
我假设您正在寻找直观的定义，因为技术定义需要相当长的时间才能理解。首先，让我们记住一个初步需要的概念来理解这些定义。
现在，让我们定义那些复杂性类 。
P 是一个复杂性类，表示可以在多项式时间内求解的所有决策问题的集合 。
也就是说，给定问题的实例，可以在多项式时间中确定答案是或否。
例
给定连通图G ，它的顶点是否可以使用两种颜色着色，以便没有边缘是单色的？
算法：从任意顶点开始，将其着色为红色，其所有邻居为蓝色并继续。当你用完顶点时停止，或者你被迫使边缘的两个端点都是相同的颜色。
NP 是一个复杂性类，表示所有决策问题的集合，其中答案为 “是” 的实例具有可在多项式时间内验证的证据。
这意味着如果有人向我们提供了问题的实例和证书（有时称为证人），答案是肯定的，我们可以检查它在多项式时间内是否正确。
例
整数因子分解在 NP 中。这是给定的整数问题n和m ，是否有一个整数f与1 < f < m使得f划分n （ f是小因子n ）？
这是一个决策问题，因为答案是肯定的或不是。如果有人向我们提出问题的实例（因此他们将整数n和m交给我们）和1 < f < m的整数f ，并声称f是n的因子（证书），我们可以检查答案通过执行除法n / f 多项式时间 。
NP-Complete 是一个复杂度类，它表示 NP 中所有问题X的集合，在多项式时间内可以减少任何其他 NP 问题Y到X
直观地说，这意味着如果我们知道如何快速解决X ，我们可以快速解决Y准确地说， Y还原为X ，如果存在一个多项式时间算法f变换实例y的Y到实例x = f(y)的X在多项式时间，与该回答该属性y是肯定的，当且仅如果f(y)的答案是肯定的。
例
3-SAT 。这是我们给出 3 个子句析取（OR）的连接（ANDs）的问题，形式的陈述
(x_v11 OR x_v21 OR x_v31) AND
(x_v12 OR x_v22 OR x_v32) AND
... AND
(x_v1n OR x_v2n OR x_v3n)其中每个x_vij是一个布尔变量，或者是来自有限预定义列表(x_1, x_2, ... x_n)变量的否定。
可以证明， 每个 NP 问题都可以减少到 3-SAT 。这方面的证据是技术性的，需要使用 NP 的技术定义（ 基于非确定性图灵机 ）。这被称为库克定理 。
NP 完全问题的重要之处在于，如果可以找到确定性多项式时间算法来解决其中一个问题，那么每个 NP 问题都可以在多项式时间内解决（一个问题就是将它们统一起来）。
直觉上，这些问题至少与 NP 完全问题一样困难 。请注意，NP 难题不必在 NP 中 ，并且它们不一定是决策问题 。
这里的精确定义是问题X是 NP 难的，如果存在 NP 完全问题Y ，使得Y在多项式时间内可简化为X
但由于任何 NP 完全问题可以在多项式时间内减少到任何其他 NP 完全问题，所以所有 NP 完全问题都可以在多项式时间内减少到任何 NP 难问题。然后，如果在多项式时间内存在一个 NP 难问题的解，则在多项式时间内存在所有 NP 问题的解。
例
停止问题是 NP 难问题。这是给出程序P和输入I ，它会停止吗？这是一个决策问题，但它不在 NP 中。很明显，任何 NP 完全问题都可以简化为这个问题。作为另一个例子，任何 NP 完全问题都是 NP 难的。
我最喜欢的 NP 完全问题是扫雷问题 。
这是计算机科学中最着名的问题，也是数学科学中最重要的突出问题之一。事实上， 克莱研究所提供了 100 万美元用于解决问题的方法（ 斯蒂芬库克在克莱网站上的写作非常好）。
很明显 P 是 NP 的子集。悬而未决的问题是 NP 问题是否具有确定性多项式时间解。人们普遍认为他们没有。这是一篇关于 P = NP 问题的最新（和重要性）的最新文章： P 与 NP 问题的状态 。
关于这个主题的最好的书是 Garey 和 Johnson 的计算机和难以理解的书。
我一直在环顾四周，看到许多长篇解释。这是一个小图表，可能有助于总结：
注意难度从上到下增加：任何NP 都可以减少到 NP-Complete ，任何NP-Complete 都可以减少到 NP-Hard ，全部在 P（多项式）时间内。
如果你能在 P 时间内解决一个更难的问题，那就意味着你找到了如何在 P 时间内解决所有更容易的问题（例如，证明 P = NP，如果你弄清楚如何解决任何 NP-Complete 问题 P 时间）。
____________________________________________________________ | Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty ___________________________________________________________| | | P | Yes | Yes | | | NP | Yes | Yes or No * | | | NP-Complete | Yes | Unknown | | | NP-Hard | Yes or No ** | Unknown *** | | ____________________________________________________________ V
关于Yes或No条目的说明：
我还发现这个图非常有用，可以看到所有这些类型如何相互对应（更多地关注图的左半部分）。
这是对所提问题的非正式回答。
3233 可以写成另外两个大于 1 的数字的乘积吗？有没有办法绕过柯尼斯堡的所有七座桥，而不需要两次搭桥？这些是具有共同特征的问题的示例。如何有效地确定答案可能并不明显，但如果答案为 “是”，那么有一个简短快速的检查证据。在第一种情况下，51 的非平凡因子分解; 在第二个，走桥梁的路线（适应约束）。
决策问题是具有是或否答案的问题集合，这些答案仅在一个参数中变化。说问题 COMPOSITE = {“Is n composite”： n是整数} 或 EULERPATH = {“图G是否有欧拉路径？”： G是有限图}。
现在，一些决策问题有助于提高效率，即使不是很明显的算法。欧拉在 250 多年前发现了一种有效的算法来解决诸如 “柯尼斯堡的七桥” 之类的问题。
另一方面，对于许多决策问题，如何得到答案并不明显 - 但如果你知道一些额外的信息，很明显如何证明你已经得到了正确答案。 COMPOSITE 是这样的：试验除法是明显的算法，它很慢：要算出一个 10 位数的数字，你必须尝试类似 100,000 个可能的除数。但是，例如，如果某人告诉你 61 是 3233 的除数，那么简单的长除法是一种有效的方法，可以看出它们是正确的。
复杂性类NP是一类决策问题，其中 “是” 答案具有简短状态，快速检查证据。像 COMPOSITE 一样。一个重要的一点是，这个定义并没有说明问题的严重程度。如果您有一个正确，有效的方法来解决决策问题，那么只需写下解决方案中的步骤就足够了。
算法研究仍在继续，并且一直在创建新的聪明算法。你今天可能不知道如何有效解决的问题可能会在明天有一个有效的（如果不是显而易见的）解决方案。事实上，直到2002 年 ，研究人员才找到了有效的 COMPOSITE 解决方案！随着所有这些进步，人们真的不得不怀疑：这有点短暂的证据只是一种幻觉吗？也许每个有助于高效校对的决策问题都有一个有效的解决方案吗？ 没人知道 。
也许对这一领域的最大贡献来自于发现一种特殊的 NP 问题。通过玩弄电路模型进行计算，斯蒂芬 · 库克发现的 NP 品种，这是可证明为硬或比所有其他 NP 问题更难决策问题。 布尔可满足性问题的有效解决方案可用于为 NP 中的任何其他问题创建有效的解决方案。不久之后，理查德卡普表明，其他一些决策问题也可以达到同样的目的。从某种意义上说，这些问题是 NP 中 “最难” 的问题，被称为NP 完全问题。
当然，NP 只是一类决策问题。许多问题不是以这种方式自然陈述的：“找到 N 的因子”，“找到访问每个顶点的图 G 中的最短路径”，“给出一组使下面的布尔表达式为真的变量赋值”。虽然可以非正式地谈论一些这样的问题是 “在 NP 中”，从技术上说这没有多大意义 - 它们不是决策问题。其中一些问题甚至可能与 NP 完全问题具有相同的能力：这些（非决策）问题的有效解决方案将直接导致任何 NP 问题的有效解决方案。像这样的问题被称为NP-hard 。