NP，NP-Complete和NP-Hard之间有什么区别？
NP ， NP-Complete和NP-Hard之间有什么区别？
我知道整个networking上的许多资源。 我想读你的解释，其原因是他们可能会有所不同，那里有什么，或者它在外面，我不知道。
我认为你正在寻找直观的定义，因为技术定义需要相当长的一段时间才能理解。 首先，让我们记住一个初步的必要概念来理解这些定义。
- 决策问题 ：答案是 否定的问题。
现在，让我们定义这些复杂类 。
P
P是一个复杂等级，表示可以在多项式时间内解决的所有决策问题的集合 。 也就是说，给定一个问题的实例，答案是或否可以在多项式时间内决定。
例
给定一个连接G的图，它的顶点是否可以使用两种颜色进行着色，以便没有边是单色的？
algorithm：从一个任意的顶点开始，将其着色为红色，并将其所有邻居都变成蓝色并继续。 停止当你走出顶点，或者你被迫做出一个边缘，它的两个端点是相同的颜色。
NP
NP是一个复杂等级，表示所有决策问题的集合，其中答案是“是”的实例具有可以在多项式时间中validation的certificate。
这意味着，如果有人给我们一个问题的实例和一个证书（有时称为证人）的答案是肯定的，我们可以检查它在多项式时间是正确的。
例
整数因子化在NP中。 这是给定整数n和m的问题，是否存在1 < f < m的整数f ，使得f除以n （ f是n一个小因子）？
这是一个决定性的问题，因为答案是肯定的或不是。 如果有人给我们一个问题的实例（所以他们把我们的整数n和m ）和一个整数f 1 < f < m ，并声称f是一个因子n （证书），我们可以检查答案多项式时间通过执行除法n / f 。
NP完全
NP-Complete是一个复杂类，它表示NP中所有问题X的集合，可以在多项式时间内将任何其他NP问题Y减less到X
直观地说，这意味着如果我们知道如何快速求解X ，我们可以快速求解Y 正确地说，如果存在一个多项式时间algorithmf ，将Y实例y转换成多项式时间的Y的实例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是一个布尔variables或者来自有限预定义列表(x_1, x_2, ... x_n)variables的否定。
可以看出， 每个NP问题都可以简化为3-SAT 。 certificate这是技术性的，需要使用NP的技术定义（ 基于非确定性图灵机 ）。 这就是所谓的库克定理 。
NP完全问题的重要性在于，如果可以find一个确定性的多项式时间algorithm来解决其中的一个问题，那么每个NP问题都可以在多项式时间内解决（一个问题就是将它们全部统一起来）。
NP难
直觉上来说，这些问题至less和NP完全问题一样困难 。 请注意，NP-hard问题不一定要在NP中 ，而且也不必是决策问题 。
这里的精确定义是一个问题X是NP难的，如果存在一个NP完全问题Y ，使得Y在多项式时间内可以简化为X
但是由于任何NP完全问题在多项式时间内都可以简化为任意其他的NP完全问题，所以NP-完全问题在多项式时间内可以简化为任意NP-hard问题。 那么，如果在多项式时间内有一个NP难问题的解，那么在多项式时间内就有一个NP问题的解。
例
暂停问题是一个NP难题。 给定程序P和inputI ，这是问题，它会停止吗？ 这是一个决定性的问题，但不是NP。 很显然，任何NP完全问题都可以归结为这个问题。 又如，任何NP完全问题都是NP难题。
我最喜欢的NP完全问题是扫雷问题 。
P = NP
这是计算机科学中最着名的问题，也是math科学中最重要的突出问题之一。 事实上， 克莱研究所正在提供100万美元来解决这个问题（史蒂芬·库克在克莱网站上的写作非常好）。
很显然，P是NP的一个子集。 NP问题是否具有确定性的多项式时间解决scheme是一个悬而未决的问题。 很大程度上相信他们没有。 最近一篇关于P = NP问题的最新（和重要性）的文章是： P与NP问题的地位 。
关于这个问题的最好的书是加里和约翰逊的“ 计算机与难题” 。
我一直在环顾四周，看到很多很长的解释。 下面是一个小图表，可能有助于总结：
注意从上到下的难度有多大：任何NP都可以简化为NP-Complete ，任何NP-Complete都可以简化为NP-Hard ，全部在P（多项式）时间。
如果你能在P时间内解决更困难的一类问题，那么这将意味着你find了如何解决P时间内所有更简单的问题（例如，certificateP = NP，如果你计算出如何解决任何NP完全问题P时间）。
____________________________________________________________ | 问题types| 在P时间可validation| 可以在P时间解决| 越来越难 ___________________________________________________________ | | | P | 是| 是| | | NP | 是| 是或否* | | | NP-Complete | 是| 未知| | | NP-Hard | 是或否** | 未知*** | | ____________________________________________________________
注意Yes或No条目：
- *也是P的NP问题在P时间是可以解决的。
- **一个NP-Hard问题也是NP-Complete在P时间是可validation的。
- *** NP完全问题（所有这些都构成NP-hard的一个子集）可能是。 NP的其余部分并非如此。
我也发现这个图很有用，可以看到所有这些types如何相互对应（更加关注图的左半部分）。
对于所问的问题，这是非常非正式的答案。
3233可以写成两个大于1的数字的乘积吗？ 有没有办法在柯尼斯堡的七座桥梁周围走一条路，而不用两次桥呢？ 这些都是具有共同特点的问题的例子。 如何有效地确定答案可能并不明显，但如果答案是肯定的，那么有一个简短而快速的检查证据。 在第一种情况下，51的非平凡分解; 第二，走桥的路线（适应约束）。
决策问题是一组只有一个参数不同的答案的答案。 说出问题COMPOSITE = {“是n合成”： n是一个整数}或者EULERPATH = {“图G有欧拉path吗？”： G是有限图}。
现在，一些决策问题可以使自己有效，即使不是明显的algorithm。 欧拉发现了一个有效的algorithm，比如250多年前的“七座柯尼斯堡桥”。
另一方面，对于许多决策问题，如何得到答案并不明显，但是如果您知道一些额外的信息，那么很明显该如何去certificate您的答案是正确的。 COMPOSITE就是这样的：试算是显而易见的algorithm，速度很慢：要把一个10位数的数字分解一下，就得尝试10万个可能的除数。 但是，举例来说，如果有人告诉你，61是3233的除数，那么简单的长整数是一个有效的方法，可以看出它们是正确的。
复杂等级NP是一个决策问题的类别，其中“是”的答案有状态不足，快速检查certificate。 像COMPOSITE一样。 重要的一点是，这个定义并没有说明问题的严重性。 如果你有一个正确的，有效的方法来解决决策问题，只要写下解决scheme中的步骤就足够了。
algorithm研究仍在继续，并且一直在创build新的聪明的algorithm。 一个你可能不知道如何高效解决的问题明天可能会有一个有效的（如果不是很明显的）解决scheme。 事实上，研究人员直到2002年才find一个有效的解决scheme， 随着所有这些进步，人们真的不得不想知道：这是否有一个简短的certificate只是一个幻想？ 也许每一个有助于高效certificate的决策问题都有一个有效的解决scheme？ 没有人知道 。
也许对这个领域最大的贡献来自于发现了一类特殊的NP问题。 通过计算电路模型，斯蒂芬·库克（Stephen Cook）发现了一个NP变种的决策问题，可以certificate这个问题比任何其他的NP问题都要难。 布尔可满足性问题的有效解决scheme可以用来为NP中的任何其他问题创build有效的解决scheme。 不久之后，理查德·卡普（Richard Karp）表明，其他一些决策问题也可以达到同样的目的。 这些问题，从某种意义上说，NP中“最难”的问题就是NP完全问题。
当然，NP只是一类决策问题。 很多问题并不是以这种方式自然表述的：“findN的因素”，“find访问每个顶点的图G中的最短path”，“给出一组variables赋值，使得下面的布尔expression式为真”。 虽然人们可能会非正式地谈论一些这样的问题是“在NP中”，从技术上来说这没有什么意义 – 他们不是决策问题。 其中一些问题甚至可能具有与NP完全问题相同的权力：对这些（非决策）问题的有效解决scheme将直接导致对NP问题的有效解决。 像这样的问题被称为NP-hard 。
除了其他很好的答案之外，下面是人们用来表示NP，NP-Complete和NP-Hard之间区别的典型模式 ：
解释P诉NP等最简单的方法就是将“单词问题”与“多项select题”进行比较。
当你试图解决“单词问题”，你必须从头开始寻找解决scheme。 当你试图解决“多项select问题”时，你可以select：或者像解决“单词问题”一样解决问题，或者尝试插入给你的每一个答案，然后select合适的答案。
通常情况下，“多选题”比相应的“单词问题”容易得多：replace候选答案并检查它们是否合适可能需要比从头开始寻找正确答案要less得多的努力。
现在，如果我们同意多项式时间“容易”的努力，那么类P将由“简单的单词问题”组成，类NP将由“简单的多项select问题”组成。
P诉NP的本质是一个问题：“有没有简单的多选问题，不容易出现问题”？ 也就是说，是否有问题容易validation给定的答案的有效性，但从头开始find答案是困难的？
现在我们直观地理解NP是什么，我们必须挑战我们的直觉。 事实certificate，从某种意义上讲，存在着“多项select问题”是最难的：如果能够find解决scheme中的一个“最困难的”问题，那么人们就能够find解决所有问题的办法NP问题！ 当库克在40年前发现这件事情时，这是一个惊喜。 这些“其中最难的”问题被称为NP难。 如果你发现一个“单词问题解决scheme”，你会自动find一个“单词问题的解决scheme”，每一个“简单的select题”！
最后，NP完全问题是同时NP和NP难题。 按照我们的比喻，他们同时是“多select问题容易”，“最难的是问题”。
P（多项式时间）：正如名字所暗示的那样，这是多项式时间可以解决的问题。
NP（非确定性多项式时间）：这些是可以在多项式时间中validation的决策问题。 这意味着，如果我声称有一个特定问题的多项式时间解决scheme，你问我来certificate它。 那么，我会给你一个certificate，你可以很容易地在多项式时间validation。 这类问题被称为NP问题。 请注意，这里我们不是在讨论是否存在这个问题的多项式时间解决scheme。 但是我们正在讨论在多项式时间内validation给定问题的解决scheme。
NP-Hard：至less和NP中最难的问题一样困难。 如果我们能够在多项式时间内解决这些问题，就可以解决任何可能存在的NP问题。 请注意，这些问题不一定是NP问题。 这意味着，我们可能/不可能在多项式时间内validation这些问题的解决scheme。
NP-Complete：这是NP和NP-Hard的问题。 这意味着，如果我们能解决这些问题，就可以解决任何其他NP问题，并且可以在多项式时间内validation这些问题的解决scheme。
我想我们可以更简洁地回答它。 我回答了一个相关的问题 ，并从那里复制我的答案
但首先，一个NP难问题是一个我们无法certificate存在多项式时间解的问题。 一些“问题-P”的NP-硬度通常通过将已经证实的NP-难问题转换成多项式时间的“问题-P”来certificate。
要回答剩下的问题，首先需要了解哪些NP难题也是NP完备的。 如果一个NP难题属于NP集，那么它是NP完全的。 属于设定NP，需要一个问题
（i）决定问题，
（二）问题的解决scheme的数量应该是有限的，每个解决scheme应该是多项式长度，和
（iii）给出一个多项式长度的解，我们应该能够说问题的答案是否是现在很容易看出，可能有很多不属于NP的NP难题难以解决。 作为一个直观的例子，我们需要find一个实际的时间表的旅行推销员的优化版本比旅行推销员的决定版本更难，我们只需要确定是否存在长度小于等于k的时间表。
NP完全问题是既是NP-Hard又是复杂类NP的问题。 因此，要certificate任何给定的问题都是NP完全的，你需要certificate这个问题既在NP中也在NP中。
NP复杂等级中的问题可以在多项式时间内非确定性地解决，并且NP中的问题的可能解（即，证书）可以在多项式时间内被validation为正确性。
k-clique问题的非确定性解决scheme的一个例子就是：
1）从图中随机selectk个节点
2）validation这些k个节点组成一个派系。
上面的策略是input图的大小的多项式，因此k -polique问题在NP中。
注意，在多项式时间内确定可解的所有问题也都在NP中。
显示一个问题是NP难的通常涉及到使用多项式时间映射从一些其他NP难题到您的问题的减less： http : //en.wikipedia.org/wiki/Reduction_(complexity）
这个问题真的很好答案，所以没有必要写我自己的解释。 所以我会尽力提供有关不同类别的计算复杂性的优秀资源。
对于那些认为计算复杂度仅仅是P和NP的人来说， 这里是关于不同计算复杂性问题的最详尽的资源 。 除了OP所提出的问题之外，它还列出了大约500个不同types的计算问题，并且有很好的描述以及描述这个类的基础研究论文。
据我了解，一个NP难问题并不比一个NP完全问题更“困难”。 实际上，按照定义，每个np完整的问题是：
- 在NP
- NP难
– 介绍。 到Cormen，Leiserson，Rivest和Stein的algorithm（3ed），第1069页
