NP, NP- complete和NP- hard的区别是什么?
我知道网上有很多资源。我想读一下你的解释，原因是它们可能与外界的解释不同，或者有一些我不知道的东西。
当前回答
这是对问题的非正式回答。
3233可以写成另外两个大于1的数的乘积吗?有没有办法绕过Königsberg的七座桥而不经过任何一座桥两次?这些问题都有一个共同的特点。如何有效地确定答案可能并不明显，但如果答案是“是”，那么就有一个简短而快速的证明。在第一种情况下，61的非平凡因式分解(53是另一个质因数);第二种是通过桥梁的路线(符合约束条件)。
决策问题是一组答案为“是”或“否”的问题，这些问题只在一个参数上有所不同。假设问题COMPOSITE={"Is n Is COMPOSITE ": n是一个整数}或EULERPATH={"图G有欧拉路径吗?": G是有限图}。
现在，有些决策问题即使没有明显的算法，也可以用在高效的算法上。250多年前，欧拉发现了一种有效的算法来解决“Königsberg的七座桥”这样的问题。
另一方面，对于许多决策问题，如何得到答案并不明显，但如果你知道一些额外的信息，如何证明你得到了正确的答案就很明显了。COMPOSITE是这样的:试除法是显而易见的算法，它很慢:要分解一个10位数的数，你必须尝试10万个可能的除数。但是，例如，有人告诉你61是3233的除法，简单的长除法是一种有效的方法来证明他们是正确的。
复杂性类NP是一类决策问题，其中“是”的答案有简短的陈述，快速检查证明。像复合。重要的一点是，这个定义并没有说明问题有多难。如果你有一个正确有效的方法来解决一个决策问题，只要写下解决方案中的步骤就足够了。
算法的研究仍在继续，新的聪明的算法一直在被创造出来。一个你今天可能不知道如何有效解决的问题，明天可能会有一个有效的解决方案(如果不是明显的)。事实上，直到2002年，研究人员才找到了一个有效的COMPOSITE解决方案!有了这些进步，人们真的想知道:这一点关于简短的证明只是一种幻觉吗?也许每个适合有效证明的决策问题都有有效的解决方案?没有人知道。
也许这个领域最大的贡献来自于发现一类特殊的NP问题。通过摆弄电路模型进行计算，斯蒂芬·库克发现了一个NP类型的决策问题，可以证明，这个问题比任何其他NP问题都难，甚至更难。布尔可满足性问题的有效解决方案可以用于创建NP中任何其他问题的有效解决方案。不久之后，理查德·卡普(Richard Karp)证明了其他一些决策问题也可以达到同样的目的。这些问题在某种意义上是NP中“最难”的问题，被称为NP完全问题。
当然，NP只是一类决策问题。许多问题不是自然地以这种方式表述的:“找到N的因子”，“找到图G中访问每个顶点的最短路径”，“给出一组变量赋值，使以下布尔表达式为真”。尽管人们可能非正式地将一些这样的问题称为“NP问题”，但从技术上讲，这并没有多大意义——它们不是决策问题。其中一些问题甚至可能具有与NP完全问题相同的力量:对这些(非决策)问题的有效解决方案将直接导致对任何NP问题的有效解决方案。像这样的问题被称为np困难。
其他回答
我四处寻找，看到了许多冗长的解释。 这里有一个小图表，总结起来可能有用:
请注意难度是如何从上到下递增的:任何NP都可以简化为NP完全，任何NP完全都可以简化为NP困难，所有这些都需要P(多项式)时间。
如果你能在P时间内解决一个更难的问题，那就意味着你找到了如何在P时间内解决所有更简单的问题的方法(例如，证明P = NP，如果你知道如何在P时间内解决任何NP-完全问题)。
____________________________________________________________ | 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
“是”或“否”条目说明:
同样是P的NP问题可以在P时间内解决。 ** np -难问题，也是np -完全问题，在P时间内可验证。 *** np -完全问题(所有这些都构成了NP-hard的子集)可能是。其余的NP困难则不是。
我还发现这个图非常有用，可以看到所有这些类型是如何相互对应的(请更加注意图的左半部分)。
这是对问题的非正式回答。
3233可以写成另外两个大于1的数的乘积吗?有没有办法绕过Königsberg的七座桥而不经过任何一座桥两次?这些问题都有一个共同的特点。如何有效地确定答案可能并不明显，但如果答案是“是”，那么就有一个简短而快速的证明。在第一种情况下，61的非平凡因式分解(53是另一个质因数);第二种是通过桥梁的路线(符合约束条件)。
决策问题是一组答案为“是”或“否”的问题，这些问题只在一个参数上有所不同。假设问题COMPOSITE={"Is n Is COMPOSITE ": n是一个整数}或EULERPATH={"图G有欧拉路径吗?": G是有限图}。
现在，有些决策问题即使没有明显的算法，也可以用在高效的算法上。250多年前，欧拉发现了一种有效的算法来解决“Königsberg的七座桥”这样的问题。
另一方面，对于许多决策问题，如何得到答案并不明显，但如果你知道一些额外的信息，如何证明你得到了正确的答案就很明显了。COMPOSITE是这样的:试除法是显而易见的算法，它很慢:要分解一个10位数的数，你必须尝试10万个可能的除数。但是，例如，有人告诉你61是3233的除法，简单的长除法是一种有效的方法来证明他们是正确的。
复杂性类NP是一类决策问题，其中“是”的答案有简短的陈述，快速检查证明。像复合。重要的一点是，这个定义并没有说明问题有多难。如果你有一个正确有效的方法来解决一个决策问题，只要写下解决方案中的步骤就足够了。
算法的研究仍在继续，新的聪明的算法一直在被创造出来。一个你今天可能不知道如何有效解决的问题，明天可能会有一个有效的解决方案(如果不是明显的)。事实上，直到2002年，研究人员才找到了一个有效的COMPOSITE解决方案!有了这些进步，人们真的想知道:这一点关于简短的证明只是一种幻觉吗?也许每个适合有效证明的决策问题都有有效的解决方案?没有人知道。
也许这个领域最大的贡献来自于发现一类特殊的NP问题。通过摆弄电路模型进行计算，斯蒂芬·库克发现了一个NP类型的决策问题，可以证明，这个问题比任何其他NP问题都难，甚至更难。布尔可满足性问题的有效解决方案可以用于创建NP中任何其他问题的有效解决方案。不久之后，理查德·卡普(Richard Karp)证明了其他一些决策问题也可以达到同样的目的。这些问题在某种意义上是NP中“最难”的问题，被称为NP完全问题。
当然，NP只是一类决策问题。许多问题不是自然地以这种方式表述的:“找到N的因子”，“找到图G中访问每个顶点的最短路径”，“给出一组变量赋值，使以下布尔表达式为真”。尽管人们可能非正式地将一些这样的问题称为“NP问题”，但从技术上讲，这并没有多大意义——它们不是决策问题。其中一些问题甚至可能具有与NP完全问题相同的力量:对这些(非决策)问题的有效解决方案将直接导致对任何NP问题的有效解决方案。像这样的问题被称为np困难。
除了其他很好的答案，下面是人们用来显示NP、NP- complete和NP- hard之间区别的典型模式:
解释P和NP的最简单的方法是比较“文字问题”和“多项选择题”。
当你试图解决一个“应用题”时，你必须从头开始寻找解决方案。 当你试图解决一个“多项选择题”时，你有一个选择:要么像解决“应用题”一样解决它，要么试着把给你的每个答案都代入，然后选择一个合适的候选答案。
通常情况下，“多项选择题”比相应的“应用题”容易得多:替换候选答案并检查它们是否合适，可能比从头开始寻找正确答案要省力得多。
现在，如果我们同意花费多项式时间的努力是“简单”的，那么P类将由“简单的应用题”组成，NP类将由“简单的多项选择题”组成。
P和NP的本质是一个问题:“有没有简单的选择题不像应用题那么简单?”也就是说，是否存在这样的问题:验证给定答案的有效性很容易，但从头开始寻找答案却很困难?
现在我们已经直观地理解了NP是什么，我们必须挑战我们的直觉。事实证明，在某种意义上，“多项选择题”是最难的:如果一个人能找到其中一个“最难的”问题的解决方案，那么他就能找到所有NP问题的解决方案!40年前，当库克发现这一点时，完全出乎意料。这些“最难的”问题被称为np难问题。如果你找到其中一个的“应用题解答”，你就会自动找到每一个“简单多项选择题”的“应用题解答”!
最后，NP完全问题是那些同时是NP和NP难的问题。按照我们的类比，它们既“像选择题一样简单”，又“像应用题一样最难”。
根据我的理解，np-hard问题并不比np-complete问题“更难”。事实上，根据定义，每个np完全问题都是:
在NP np-hard
——介绍。Cormen, Leiserson, Rivest, and Stein所著的算法(3ed)，第1069页
条件1。和2。翻译成英语:
语言L在NP中，和 每一种NP语言都是多项式时间可约化为语言L。
