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

老实说，维基百科可能是寻找答案的最佳场所。

如果NP = P，那么我们就可以比我们之前认为的更快地解决非常困难的问题。如果我们在P(多项式)时间内只解决了一个np -完全问题，那么它可以应用于np -完全范畴内的所有其他问题。

NP问题:-

NP问题是一类可以在非确定多项式时间内解决的问题。 非确定性算法分为两个阶段。 非确定性猜测阶段&&非确定性验证阶段。

Np问题的类型

NP完全 NP困难

NP完全问题:-

如果问题A具有以下两个性质，则称为NP完全问题

它属于NP类。 NP中的任何其他问题都可以在多项式时间内转化为P。

一些例子:

背包问题 子集和问题 顶点覆盖问题

NP代表非确定性多项式时间。

这意味着使用非确定性图灵机(就像常规图灵机，但也包括非确定性“选择”函数)可以在多项式时间内解决问题。基本上，解必须在多边形时间内可测试。如果是这样的话，一个已知的NP问题可以用修改输入的给定问题来解决(一个NP问题可以简化为给定问题)，那么这个问题就是NP完全的。

从np完全问题中得到的主要东西是，它不能以任何已知的方式在多项式时间内解决。NP-Hard/NP-Complete是一种表明某些类型的问题在现实时间内无法解决的方法。

编辑:正如其他人所注意到的，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问题可以在多项式时间内约简，其解 仍然可以在多项式时间内验证。也就是说，任何NP问题都可以 转化为np完全问题。 非正式地说，NP完全问题是一个NP问题，至少是“难” 和NP中的其他问题一样。