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)
其他回答
找到一些有趣的定义:
对于这个特别的问题有很好的答案，所以没有必要写我自己的解释。所以我会试着提供关于不同类型计算复杂度的优秀资源。
对于那些认为计算复杂度只是关于P和NP的人来说，这里有关于不同计算复杂度问题的最详尽的资源。除了OP提出的问题，它还列出了大约500种不同类型的计算问题，并给出了很好的描述，还列出了描述这类问题的基础研究论文。
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-hard问题并不比np-complete问题“更难”。事实上，根据定义，每个np完全问题都是:
在NP np-hard
——介绍。Cormen, Leiserson, Rivest, and Stein所著的算法(3ed)，第1069页
条件1。和2。翻译成英语:
语言L在NP中，和 每一种NP语言都是多项式时间可约化为语言L。
P(多项式时间):顾名思义，这些问题可以在多项式时间内解决。
NP (Non-deterministic-polynomial Time):可以在多项式时间内验证的决策问题。这意味着，如果我说有一个多项式时间解对于一个特定的问题，你要我证明它。然后，我会给出一个证明你可以在多项式时间内证明。这类问题被称为NP问题。注意，这里我们讨论的不是这个问题是否存在多项式时间解。但我们讨论的是在多项式时间内验证给定问题的解。
NP- hard:这些问题至少和NP中最难的问题一样难。如果我们能在多项式时间内解决这些问题，我们就能解决任何可能存在的NP问题。请注意，这些问题不一定是NP问题。这意味着，我们可能在多项式时间内验证这些问题的解。
NP完全:这些问题既是NP问题又是NP困难问题。这意味着，如果我们能解决这些问题，我们就能解决任何其他NP问题，这些问题的解可以在多项式时间内得到验证。
