NP，NP有什么区别？
NP ， NP-Complete和NP-Hard之间有什么区别？
我意识到网络上的许多资源。 我想阅读你的解释，原因是他们可能与那里有什么不同，或者它在外面，我不知道。
我假设你正在寻找直观的定义，因为技术定义需要相当长的一段时间才能理解。 首先，让我们记住一个初步的必要概念来理解这些定义。
现在，让我们定义这些复杂类。
P
P是一个复杂等级，表示可以在多项式时间内解决的所有决策问题的集合。 也就是说，给定一个问题的实例，答案是或否可以在多项式时间内确定。
例
给定一个连通图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 准确地说， Y还原为X ，如果存在一个多项式时间算法f变换实例y的Y到实例x = f(y)的X在多项式时间，与该回答该属性y是肯定的，当且仅如果对f(y)的回答是肯定的。
例
3-SAT 。 这是一个问题，在这个问题中，我们给出了3子句分离（OR），表单语句
(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中，而且也不一定是决策问题。
这里的精确定义是，如果存在NP完全问题Y ，那么问题X是NP难的，使得Y在多项式时间内可以简化为X
但是由于任何NP完全问题都可以简化为多项式时间内的任何其他NP完全问题，所以所有NP完全问题都可以简化为多项式时间内的任意NP难问题。 那么，如果在多项式时间内有一个NP难问题的解，那么在多项式时间内就有一个NP问题的解。
例
暂停问题是一个NP难题。 这是给定程序P和输入I ，它会停止吗？ 这是一个决策问题，但它不在NP中。 很明显，任何NP完全问题都可以归结为这个问题。 又如，任何NP完全问题都是NP难题。
我最喜欢的NP完全问题是扫雷问题。
P = NP
这是计算机科学中最着名的问题，也是数学科学中最重要的突出问题之一。 事实上，克莱研究所正在提供100万美元的解决方案来解决这个问题（斯蒂芬库克在克莱网站上的评论相当不错）。
很明显，P是NP的一个子集。 尚未解决的问题是NP问题是否具有确定性多项式时间解。 很大程度上相信他们没有。 这是一篇最近出版的关于P = NP问题的最新（以及重要性）的文章：P与NP问题的现状。
关于这个主题的最好的书是Garey和Johnson提出的Computers and Intractability。
我一直在环顾四周，看到很多很长的解释。 这是一个小图表，可能对总结有用：
注意从上到下的难度有多大：任何NP都可以简化为NP-Complete，任何NP-Complete都可以简化为NP-Hard，所有P（多项式）时间。
如果你可以在P时间内解决更困难的一类问题，那么这意味着你找到了解决P时间内所有更简单的问题的方法（例如，证明P = NP，如果你计算出如何解决任何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条目：
我还发现这个图很有用，可以看到所有这些类型如何相互对应（更关注图的左半部分）。
这是对所问问题的非常非正式的回答。
3233可以写成两个大于1的数字的乘积吗？ 是否有任何方法可以在柯尼斯堡的七座桥梁周围走过一条路，而不需要两次桥？ 这些是具有共同特点的问题的例子。 如何有效地确定答案可能并不明显，但如果答案是'是'，那么就有一个简短而快速的检查证据。 在第一种情况下，51的非平凡因子分解; 第二，走桥的路线（适合约束）。
决策问题是一组只有一个参数不同的答案的答案。 说出问题COMPOSITE = {“是n合成”： n是一个整数}或者EULERPATH = {“图G有欧拉路径吗？”： G是有限图}。
现在，一些决策问题可以使它们有效，即使不是明显的算法。 欧拉发现了一种有效的算法，用于解决250多年前的“七座柯尼斯堡桥”问题。
另一方面，对于许多决策问题，如何得出答案并不明显 - 但如果你知道一些额外的信息，很明显该如何去证明你的答案是正确的。 COMPOSITE就是这样的：试算是显而易见的算法，并且速度很慢：要分解一个10位数的数字，你必须尝试10万个可能的除数。 但是，例如，如果有人告诉你，61是3233的除数，那么简单的长分区是一种有效的方法，可以看出它们是正确的。
复杂等级NP是决策问题的类别，其中'是'的答案对状态不足，快速检查证据。 像COMPOSITE一样。 重要的一点是，这个定义并没有说明问题的严重性。 如果您有解决决策问题的正确有效方法，只需写下解决方案中的步骤即可证明。
继续进行算法研究，并且始终创建新的聪明算法。 一个你可能不知道如何高效解决的问题明天可能会有一个高效的（如果不是明显的）解决方案。 事实上，研究人员直到2002年才找到一种有效的复合材料解决方案！ 随着所有这些进步，人们真的不得不怀疑：这是否有点简单的证明只是一种幻觉？ 也许每一个有助于高效证明的决策问题都有一个有效的解决方案？ 没人知道。
也许对这个领域的最大贡献来自于发现一类特殊的NP问题。 通过使用电路模型进行计算，斯蒂芬库克发现了NP变种的一个决策问题，证明它可能比任何其他NP问题都困难或困难。 布尔可满足性问题的有效解决方案可用于为NP中的任何其他问题创建有效的解决方案。 不久之后，理查德卡普表明，其他一些决策问题可以达到同样的目的。 从某种意义上说，这些问题是NP中“最难”的问题，被称为NP完全问题。
当然，NP只是一类决策问题。 许多问题不是以这种方式自然地陈述：“找到N的因子”，“找到访问每个顶点的图G中的最短路径”，“给出一组变量赋值，使得下面的布尔表达式成为真”。 虽然人们可能非正式地谈论一些这样的问题是“在NP中”，从技术上讲这没什么意义 - 它们不是决策问题。 其中一些问题甚至可能具有与NP完全问题相同的权力：对这些（非决策）问题的有效解决方案将直接导致对任何NP问题的有效解决方案。 像这样的问题被称为NP-hard 。
链接地址: http://www.djcxy.com/p/1035.html