NP、NP-Complete 和 NP-Hard 有什么区别？
NP、NP-Complete 和 NP-Hard 有什么区别？
我知道网上有很多资源。我想阅读您的解释，原因是它们可能与外面的不同，或者有些我不知道。
我假设您正在寻找直观的定义，因为技术定义需要相当长的时间来理解。首先，让我们记住理解这些定义所需的初步概念。
决策问题：回答是或否的问题。
现在，让我们定义这些复杂性类。
磷
是一个复杂性类，表示可以在多项式时间内解决的所有决策问题的集合。
也就是说，给定一个问题的实例，答案是或否可以在多项式时间内确定。
例子
给定一个连通图 G，它的顶点可以用两种颜色着色，从而没有边是单色的吗？
算法：从任意顶点开始，将其着色为红色并将其所有邻居着色为蓝色并继续。当您用完顶点或被迫使边的两个端点都具有相同颜色时停止。
NP
NP 是一个复杂性类，表示所有决策问题的集合，其中答案为“是”的实例具有可以在多项式时间内验证的证明。
这意味着如果有人给我们一个问题实例和一个证明（有时称为见证人）的答案是肯定的，我们可以在多项式时间内检查它是否正确。
例子
整数分解 在 NP 中。这就是给定整数 n 和 m 的问题，是否存在一个整数 f 和 1 < f < m，使得 f 除以 n（f 是 n 的一个小因数）？
这是一个决策问题，因为答案是肯定或否定。如果有人递给我们一个问题实例（所以他们递给我们整数 n 和 m）和一个带有 1 < f < m 的整数 f，并声称 f 是 n 的因数（证书)，我们可以通过执行除法 n / f 在 多项式时间 中检查答案。
NP-完全
NP-Complete 是一个复杂性类，它表示 NP 中所有问题 X 的集合，可以在多项式时间内将任何其他 NP 问题 Y 简化为 X。
直观地说，这意味着如果我们知道如何快速解决 X，我们就可以快速解决 Y。准确地说，如果有一个多项式时间算法 f 在多项式时间内将 Y 的实例 y 转换为 X 的实例 x = f(y)，则 Y 可简化为 X，其性质为y 的答案是肯定的，当且仅当 f(y) 的答案是肯定的。
例子
3-SAT。这是一个问题，其中我们给出了 3 子句析取 (OR) 的合取 (AND)，形式为
(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-hard 问题不一定是 NP 问题，也不一定是决策问题。
这里的精确定义是问题 X 是 NP 难的，如果存在 NP 完全问题 Y，则 Y 在多项式时间内可简化为 X。
但是由于任何 NP 完全问题都可以在多项式时间内归约为任何其他 NP 完全问题，因此所有 NP 完全问题都可以在多项式时间内归约为任何 NP 难题。那么，如果在多项式时间内有一个 NP-hard 问题的解决方案，那么在多项式时间内就有所有 NP 问题的解决方案。
例子
halting problem 是一个 NP 难题。这是给定程序 P 和输入 I 的问题，它会停止吗？这是一个决策问题，但它不在 NP 中。很明显，任何 NP 完全问题都可以简化为这个问题。再举一个例子，任何 NP 完全问题都是 NP 难的。
我最喜欢的 NP 完全问题是 Minesweeper problem。
P = NP
这是计算机科学中最著名的问题，也是数学科学中最重要的突出问题之一。事实上，Clay Institute 出价 100 万美元来解决这个问题（Stephen Cook 在 Clay 网站上的 writeup 非常好）。
很明显，P 是 NP 的子集。悬而未决的问题是 NP 问题是否具有确定性多项式时间解。人们普遍认为他们没有。这是最近一篇关于 P = NP 问题的最新（和重要性）的杰出文章：The Status of the P versus NP problem。
关于该主题的最佳书籍是 Garey 和 Johnson 所著的 Computers and Intractability。
我一直在环顾四周，看到许多冗长的解释。这是一个小图表，可能有助于总结：
注意难度是如何从上到下增加的：任何 NP 都可以简化为 NP-Complete，任何 NP-Complete 都可以简化为 NP-Hard，所有这些都在 P（多项式）时间内完成。
如果你能在 P 时间内解决更难的一类问题，那意味着你找到了如何在 P 时间内解决所有更简单的问题（例如，证明 P = NP，如果你在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 条目的注释：
* 一个也是 P 的 NP 问题可以在 P 时间内解决。
** 一个也是 NP-Complete 的 NP-Hard 问题在 P 时间内是可验证的。
*** NP-Complete 问题（所有这些都是 NP-hard 的一个子集）可能是。其余的 NP 硬不是。
我还发现 this diagram 在查看所有这些类型如何相互对应时非常有用（请多注意图表的左半部分）。
P（多项式时间）：顾名思义，这些都是可以在多项式时间内解决的问题。
NP（非确定性多项式时间）：这些是可以在多项式时间内验证的决策问题。这意味着，如果我声称某个特定问题存在多项式时间解，那么您要求我证明这一点。然后，我会给你一个证明，你可以在多项式时间内轻松验证。这类问题称为 NP 问题。请注意，这里我们不是在讨论这个问题是否存在多项式时间解。但是我们谈论的是在多项式时间内验证给定问题的解决方案。
NP-Hard：这些至少与 NP 中最难的问题一样难。如果我们能在多项式时间内解决这些问题，我们就可以解决任何可能存在的 NP 问题。请注意，这些问题不一定是 NP 问题。这意味着，我们可能/可能不会在多项式时间内验证这些问题的解决方案。
NP-Complete：这些是 NP 和 NP-Hard 的问题。这意味着，如果我们能够解决这些问题，我们就可以解决任何其他 NP 问题，并且这些问题的解决方案可以在多项式时间内得到验证。
这是对所提问题的非常非正式的回答。
3233 可以写成其他两个大于 1 的数字的乘积吗？有没有什么方法可以绕着所有的 Seven Bridges of Königsberg 走一条小路，而不用走两次桥？这些是具有共同特征的问题示例。如何有效地确定答案可能并不明显，但如果答案是“是”，那么就有一个简短而快速的检查证明。在第一种情况下，61 的非平凡因式分解（53 是另一个素数）；第二，一条走桥的路线（符合约束条件）。
决策问题是一组问题的集合，它们的答案只有一个参数是肯定的或否定的。说问题 COMPOSITE={"Is n 复合": n 是整数} 或 EULERPATH={"图 G 有欧拉路径吗？": G 是有限图}。
现在，一些决策问题适用于高效的算法，即使不是显而易见的算法。欧拉在 250 多年前发现了一种有效的算法来解决像“柯尼斯堡七桥”这样的问题。
另一方面，对于许多决策问题，如何得到答案并不明显——但如果你知道一些额外的信息，那么如何去证明你的答案是正确的就很明显了。 COMPOSITE 是这样的：试除法是显而易见的算法，而且速度很慢：要分解一个 10 位数字，您必须尝试大约 100,000 个可能的除数。但是，例如，如果有人告诉你 61 是 3233 的除数，那么简单的长除法是一种有效的方法来判断它们是否正确。
复杂性类别 NP 是一类决策问题，其中“是”的答案很简短，可以快速检查证明。像复合材料。重要的一点是，这个定义并没有说明问题的难度。如果你有一个正确、有效的方法来解决决策问题，只需写下解决方案中的步骤就足够了。
算法研究仍在继续，新的聪明算法一直在创造。您今天可能不知道如何有效解决的问题明天可能会变成有效（如果不明显）的解决方案。事实上，直到 2002，研究人员才找到 COMPOSITE 的有效解决方案！随着所有这些进步，人们真的不得不怀疑：这是否只是一种幻觉？也许每一个适合于有效证明的决策问题都有一个有效的解决方案？ Nobody knows。
也许对这一领域的最大贡献是发现了一类特殊的 NP 问题。通过使用用于计算的电路模型，Stephen Cook 发现了一个 NP 类型的决策问题，该问题被证明与所有其他 NP 问题一样难或更难。 boolean satisfiability problem 的有效解决方案可用于为 NP 中的任何其他问题创建有效解决方案。不久之后，理查德·卡普展示了许多其他决策问题也可以达到同样的目的。这些问题，在某种意义上是 NP 中“最难”的问题，被称为 NP-complete 问题。
当然，NP 只是一类决策问题。许多问题并不是自然地以这种方式陈述的：“找到 N 的因数”、“找到图 G 中访问每个顶点的最短路径”、“给出一组变量赋值，使以下布尔表达式为真”。尽管人们可能会非正式地谈论“在 NP 中”存在的一些此类问题，但从技术上讲，这并没有多大意义——它们不是决策问题。其中一些问题甚至可能具有与 NP 完全问题相同的能力：对这些（非决策）问题的有效解决方案将直接导致对任何 NP 问题的有效解决方案。像这样的问题称为 NP-hard。
除了其他很好的答案之外，这里是人们用来显示 NP、NP-Complete 和 NP-Hard 之间区别的 typical schema：
https://i.stack.imgur.com/te3OR.png
在不涉及技术细节的情况下解释 P v. NP 等的最简单方法是将“单词问题”与“多项选择问题”进行比较。
当您尝试解决“文字问题”时，您必须从头开始找到解决方案。当您尝试解决“多项选择问题”时，您有一个选择：要么像解决“单词问题”一样解决它，要么尝试插入给您的每个答案，然后选择合适的候选答案。
通常情况下，“多项选择题”比相应的“单词问题”要容易得多：替换候选答案并检查它们是否合适可能比从头开始寻找正确答案所需的努力要少得多。
现在，如果我们同意花费多项式时间“简单”的努力，那么 P 类将由“简单的单词问题”组成，而 NP 类将由“简单的多项选择问题”组成。
P v. NP 的本质是一个问题：“有没有像单词问题那样简单的多项选择题”？也就是说，是否存在容易验证给定答案的有效性但很难从头开始找到答案的问题？
既然我们直观地理解了 NP 是什么，我们就必须挑战我们的直觉。事实证明，存在“多项选择问题”，从某种意义上说，它们是所有问题中最难的：如果一个人能找到解决这些“最难的”问题之一的方法，那么他就能找到所有问题的解决方案。 NP问题！当库克在 40 年前发现这一点时，完全出乎意料。这些“最难的”问题被称为 NP-hard。如果您找到其中一个的“文字问题解决方案”，您将自动为每个“简单的选择题”找到一个“文字问题解决方案”！
最后，NP-complete 问题是那些同时是 NP 和 NP-hard 的问题。按照我们的类比，它们同时是“简单的选择题”和“最难的都是单词问题”。
NP 完全问题是既属于 NP-Hard 又属于复杂性类别 NP 的问题。因此，要证明任何给定的问题都是 NP 完全的，您需要证明该问题既属于 NP 问题，又属于 NP-hard 问题。
NP 复杂性类别中的问题可以在多项式时间内非确定性地解决，并且可以在多项式时间内验证 NP 中问题的可能解决方案（即证书）的正确性。
k-clique 问题的非确定性解决方案的示例如下：
1) 从图中随机选择 k 个节点
2) 验证这 k 个节点是否形成了一个 clique。
上述策略在输入图的大小上是多项式的，因此 k-clique 问题在 NP 中。
请注意，在多项式时间内确定性可解决的所有问题也在 NP 中。
表明一个问题是 NP-hard 通常涉及使用多项式时间映射从其他一些 NP-hard 问题简化为您的问题：http://en.wikipedia.org/wiki/Reduction_(complexity)
我想我们可以更简洁地回答它。我回答了 related question，并从那里复制了我的答案
但首先，NP-hard 问题是我们无法证明多项式时间解存在的问题。某些“问题-P”的 NP-hardness 通常通过在多项式时间内将已经证明的 NP-hard 问题转换为“problem-P”来证明。
要回答剩下的问题，您首先需要了解哪些 NP-hard 问题也是 NP-complete。如果一个 NP-hard 问题属于集合 NP，那么它是 NP-complete。要属于集合 NP，一个问题需要是 (i) 一个决策问题，(ii) 问题的解决方案的数量应该是有限的，并且每个解决方案应该是多项式长度，并且 (iii) 给定一个多项式长度的解决方案，我们应该可以说这个问题的答案是否是yes/no 现在，很容易看出可能有许多不属于集合NP并且更难解决的NP-hard问题。作为一个直观的例子，我们需要找到实际时间表的旅行商的优化版本比我们只需要确定长度 <= k 的时间表是否存在的旅行商的决策版本更难。
对于这个特定的问题，确实有很好的答案，所以没有必要写我自己的解释。因此，我将尝试提供有关不同类型计算复杂性的优秀资源。
对于认为计算复杂度仅与 P 和 NP 相关的人，here is the most exhaustive resource 是关于不同的计算复杂度问题。除了 OP 提出的问题外，它还列出了大约 500 个不同类别的计算问题，并且描述得很好，还列出了描述该类别的基础研究论文。
找到一些有趣的定义：
https://i.stack.imgur.com/rzV6Q.png
据我了解，np-hard 问题并不比 np-complete 问题“更难”。事实上，根据定义，每个 np-complete 问题都是：
在 NP np-hard 中
- 介绍。致 Cormen、Leiserson、Rivest 和 Stein 的算法 (3ed)，第 1069 页
条件 1. 和 2. 翻译成英文：
语言 L 在 NP 中，每个 NP 语言都是多项式时间可约简为语言 L。
关注公众号
不定期副业成功案例分享
I超过n个变量作为输入，尝试对变量的所有2^n个可能的赋值，如果一个满足命题则停止，否则进入无限循环。我们看到，当且仅当I可满足时，该算法才会停止。因此，如果我们有一个多项式时间算法来解决停机问题，那么我们可以在多项式时间内解决 SAT。因此，停机问题是 NP 难的。