上面NP完全问题的定义是正确的，但我想我可能会对它们的哲学重要性进行抒情，因为还没有人解决这个问题。

几乎你遇到的所有复杂问题都是NP完全的。这门课有一些非常基础的东西，从计算上看和容易解决的问题是不同的。它们有自己的味道，而且不难辨认。这基本上意味着任何适度复杂的算法都不可能精确地解决——调度、优化、包装、覆盖等。

But not all is lost if a problem you'll encounter is NP Complete. There is a vast and very technical field where people study approximation algorithms, which will give you guarantees for being close to the solution of an NP complete problem. Some of these are incredibly strong guarantees -- for example, for 3sat, you can get a 7/8 guarantee through a really obvious algorithm. Even better, in reality, there are some very strong heuristics, which excel at giving great answers (but no guarantees!) for these problems.

请注意，两个非常著名的问题——图同构和因式分解——不知道是P或NP。

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

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

上面NP完全问题的定义是正确的，但我想我可能会对它们的哲学重要性进行抒情，因为还没有人解决这个问题。

几乎你遇到的所有复杂问题都是NP完全的。这门课有一些非常基础的东西，从计算上看和容易解决的问题是不同的。它们有自己的味道，而且不难辨认。这基本上意味着任何适度复杂的算法都不可能精确地解决——调度、优化、包装、覆盖等。

But not all is lost if a problem you'll encounter is NP Complete. There is a vast and very technical field where people study approximation algorithms, which will give you guarantees for being close to the solution of an NP complete problem. Some of these are incredibly strong guarantees -- for example, for 3sat, you can get a 7/8 guarantee through a really obvious algorithm. Even better, in reality, there are some very strong heuristics, which excel at giving great answers (but no guarantees!) for these problems.

请注意，两个非常著名的问题——图同构和因式分解——不知道是P或NP。

NP问题:-

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

Np问题的类型

NP完全 NP困难

NP完全问题:-

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

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

一些例子:

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

我们需要把算法和问题分开。我们编写算法来解决问题，它们以某种方式扩展。虽然这是一种简化，但如果缩放足够好，我们就用“P”来标记算法，如果缩放不够好，就用“NP”来标记算法。

了解我们试图解决的问题，而不是我们用来解决它们的算法，是有帮助的。所以我们说，所有具有良好伸缩算法的问题都是"在P内"的。而那些有一个糟糕的缩放算法的是“NP”。

That means that lots of simple problems are "in NP" too, because we can write bad algorithms to solve easy problems. It would be good to know which problems in NP are the really tricky ones, but we don't just want to say "it's the ones we haven't found a good algorithm for". After all, I could come up with a problem (call it X) that I think needs a super-amazing algorithm. I tell the world that the best algorithm I could come up with to solve X scales badly, and so I think that X is a really tough problem. But tomorrow, maybe somebody cleverer than me invents an algorithm which solves X and is in P. So this isn't a very good definition of hard problems.

尽管如此，NP中仍有许多问题，没有人知道一个好的算法。因此，如果我能证明X是一个特定的问题:一个解决X的好算法也可以用某种迂回的方式，为NP中的所有其他问题提供一个好算法。现在人们可能更相信X是一个棘手的问题。在这种情况下，我们称X为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。

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