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

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

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

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

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

对于一些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。

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

基本上这个世界的问题可以分为

1)无法解决的问题 2)棘手问题 3) np问题 4) P-Problem

1)第一个是没有解决问题的办法。 2)其次是需要指数时间(即O (2 ^ n)以上)。 3)第三个是NP。 4)第四个问题很简单。

P:多项式时间问题的解。

NP:指多项式时间尚未找到一个解决方案。我们不确定有没有多项式时间的解决方案，但一旦你提供了一个解决方案，这个解决方案可以在多项式时间验证。

NP完全:是指在多项式时间中我们还没有找到一个解，但它可以在多项式时间中得到验证。NP中的NPC问题是比较困难的问题，所以如果我们能证明NPC问题有P个解，那么NP问题就能在P个解中找到。

NP困难:指多项式时间尚未找到解决方案，但它肯定无法在多项式时间内得到验证。NP难的问题超过NPC难的问题。

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

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

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

编辑:正如其他人所注意到的，np完全问题通常有近似解。在这种情况下，近似解通常给出一个近似界，用特殊的符号告诉我们这个近似有多接近。