NP, NP- complete和NP- hard的区别是什么?
我知道网上有很多资源。我想读一下你的解释，原因是它们可能与外界的解释不同，或者有一些我不知道的东西。
当前回答
我想我们可以更简洁地回答。我回答了一个相关的问题，并从那里复制了我的答案
但首先，np难问题是指我们无法证明存在多项式时间解的问题。某些“问题- p”的np -硬度通常是通过在多项式时间内将已经证明的np -难问题转换为“问题- p”来证明的。
要回答剩下的问题，首先需要了解哪些np困难问题也是np完全问题。如果一个NP难问题属于集合NP，则它是NP完全问题。要属于集合NP，一个问题需要 (i)决策问题， (ii)问题的解的数量应该是有限的，每个解应该是多项式长度，并且 (iii)给定一个多项式长度的解，我们应该能够说出问题的答案是或否 现在，很容易看出，可能有许多NP困难问题不属于集合NP，更难解决。作为一个直观的例子，旅行推销员的优化版本(我们需要找到一个实际的时间表)比旅行推销员的决策版本(我们只需要确定长度<= k的时间表是否存在)更难。
其他回答
除了其他很好的答案，下面是人们用来显示NP、NP- complete和NP- hard之间区别的典型模式:
NP完全问题是那些既NP- hard又属于NP复杂度类的问题。因此，为了证明任何给定的问题是NP完全的，你需要证明这个问题既是NP问题，又是NP难问题。
NP复杂度类的问题可以在多项式时间内非确定性地解决，NP复杂度类问题的可能解(即证书)可以在多项式时间内验证其正确性。
k团问题的非确定性解的一个例子是这样的:
1)从图中随机选择k个节点
2)验证这k个节点组成了一个团。
上述策略在输入图的大小上是多项式，因此k团问题属于NP。
注意，所有在多项式时间内确定可解决的问题也都属于NP。
说明一个问题是np困难的通常包括使用多项式时间映射从其他np困难问题减少到你的问题:http://en.wikipedia.org/wiki/Reduction_(complexity)
我四处寻找，看到了许多冗长的解释。 这里有一个小图表，总结起来可能有用:
请注意难度是如何从上到下递增的:任何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困难则不是。
我还发现这个图非常有用，可以看到所有这些类型是如何相互对应的(请更加注意图的左半部分)。
P(多项式时间):顾名思义，这些问题可以在多项式时间内解决。
NP (Non-deterministic-polynomial Time):可以在多项式时间内验证的决策问题。这意味着，如果我说有一个多项式时间解对于一个特定的问题，你要我证明它。然后，我会给出一个证明你可以在多项式时间内证明。这类问题被称为NP问题。注意，这里我们讨论的不是这个问题是否存在多项式时间解。但我们讨论的是在多项式时间内验证给定问题的解。
NP- hard:这些问题至少和NP中最难的问题一样难。如果我们能在多项式时间内解决这些问题，我们就能解决任何可能存在的NP问题。请注意，这些问题不一定是NP问题。这意味着，我们可能在多项式时间内验证这些问题的解。
NP完全:这些问题既是NP问题又是NP困难问题。这意味着，如果我们能解决这些问题，我们就能解决任何其他NP问题，这些问题的解可以在多项式时间内得到验证。
找到一些有趣的定义:
