NP-Complete指的是非常具体的东西，你必须小心，否则你会弄错定义。首先，NP问题是一个是/否问题

对于答案为"是"的问题的每个实例都有多项式时间证明，即答案为"是"，或者(等价地) 存在一种多项式时间算法(可能使用随机变量)，如果问题实例的答案是“是”，那么它有非零概率回答“是”，如果答案是“否”，则它会在100%的时间内回答“否”。换句话说，该算法的假阴性率必须小于100%，并且没有假阳性。

问题X是np完全的，如果

X在NP中，并且 对于NP中的任何问题Y，都有一个从Y到X的“约简”:一个多项式时间算法，将Y的任何实例转换为X的实例，当且仅当X实例的答案是“是”时，Y实例的答案是“是”。

如果X是NP完全的，并且存在一个确定性的多项式时间算法，可以正确地解决X的所有实例(0%假阳性，0%假阴性)，那么NP中的任何问题都可以在确定性多项式时间中解决(通过归约到X)。

So far, nobody has come up with such a deterministic polynomial-time algorithm, but nobody has proven one doesn't exist (there's a million bucks for anyone who can do either: the is the P = NP problem). That doesn't mean that you can't solve a particular instance of an NP-Complete (or NP-Hard) problem. It just means you can't have something that will work reliably on all instances of a problem the same way you could reliably sort a list of integers. You might very well be able to come up with an algorithm that will work very well on all practical instances of a NP-Hard problem.

这是一类问题，我们必须模拟每一种可能性，以确保我们有最优解。

对于一些np完全问题，有很多好的启发式方法，但它们充其量只是一个有根据的猜测。

据我所知

P是可以用确定性TM在多项式时间内解决的问题集。

NP是需要在多项式时间内解决非确定性TM的问题集。 这意味着我们可以用多项式时间并行检查每个实例的所有不同变量组合。如果问题是可解决的，那么至少有一个平行的TM实例会以“是”而停止。 这也意味着如果你能对变量/解做出正确的猜测，那么你只需要在多项式时间内检查它的有效性。

NP- hard是指问题比NP更难的集合。这意味着NP- hard问题比NP集中的任何问题都要难。即使使用图灵机的非确定性，这些问题也是指数级的。所以并行计算在解决这些问题时没有帮助。

NP- complete是NP和NP- hard的交集集。根据我的理解，

NP完全中的问题至少和NP集中最难的问题一样难。 所有np -完全问题的类都是等价的，即np -完全集中的一个问题可以简化为任何其他的np -完全问题。这意味着，如果任何一个np完全问题都有一个有效的解，那么所有的np完全问题都可以用相同的解来解决。

如果np -完全集中的任何问题在多项式时间内确定可解，则整个np -完全集在多项式时间内确定可解。此外，由于NP-完全问题至少与NP集中最难的问题一样难，NP集中的所有问题(等于或容易于NP-完全集中的问题)将被确定性多项式的运行时间所限制，将P集扩展到NP集中，从而得到P=NP。

如果我弄错了，请告诉我。

什么是NP?

NP是所有决策问题(答案是或否的问题)的集合，其中“是”答案可以通过确定性图灵机在多项式时间(O(nk)，其中n是问题大小，k是常数)验证。有时用多项式时间来定义快或快。

P是什么?

P是由确定性图灵机在多项式时间内解决的所有决策问题的集合。由于它们可以在多项式时间内求解，因此也可以在多项式时间内验证。因此P是NP的子集。

什么是np完全?

NP中的问题x也属于NP完全，当且仅当NP中的所有其他问题都可以快速地(即。在多项式时间内)转换成x。

换句话说:

x在NP中，并且 NP中的每个问题都可约为x

所以，NP完全问题的有趣之处在于，如果任何一个NP完全问题可以快速解决，那么所有NP问题都可以快速解决。

另见帖子“P=NP”是什么?为什么这是一个如此著名的问题?

什么是NP-Hard?

NP- hard是指至少和NP中最难的问题一样难的问题。注意，np完全问题也是np难的。然而，并非所有NP难问题都是NP问题(甚至是决策问题)，尽管有NP作为前缀。NP-hard中的NP并不意味着非确定性多项式时间。是的，这令人困惑，但它的用法根深蒂固，不太可能改变。

np完全问题是一组问题，其中每一个问题都是任意的 其他np问题可以在多项式时间内约简，其解 仍然可以在多项式时间内验证。也就是说，任何NP问题都可以 转化为np完全问题。 非正式地说，NP完全问题是一个NP问题，至少是“难” 和NP中的其他问题一样。

NP-Complete指的是非常具体的东西，你必须小心，否则你会弄错定义。首先，NP问题是一个是/否问题

对于答案为"是"的问题的每个实例都有多项式时间证明，即答案为"是"，或者(等价地) 存在一种多项式时间算法(可能使用随机变量)，如果问题实例的答案是“是”，那么它有非零概率回答“是”，如果答案是“否”，则它会在100%的时间内回答“否”。换句话说，该算法的假阴性率必须小于100%，并且没有假阳性。

问题X是np完全的，如果

X在NP中，并且 对于NP中的任何问题Y，都有一个从Y到X的“约简”:一个多项式时间算法，将Y的任何实例转换为X的实例，当且仅当X实例的答案是“是”时，Y实例的答案是“是”。

如果X是NP完全的，并且存在一个确定性的多项式时间算法，可以正确地解决X的所有实例(0%假阳性，0%假阴性)，那么NP中的任何问题都可以在确定性多项式时间中解决(通过归约到X)。

So far, nobody has come up with such a deterministic polynomial-time algorithm, but nobody has proven one doesn't exist (there's a million bucks for anyone who can do either: the is the P = NP problem). That doesn't mean that you can't solve a particular instance of an NP-Complete (or NP-Hard) problem. It just means you can't have something that will work reliably on all instances of a problem the same way you could reliably sort a list of integers. You might very well be able to come up with an algorithm that will work very well on all practical instances of a NP-Hard problem.