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

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

如果你想找一个np完全问题的例子那么我建议你看一下3-SAT。

基本前提是你有一个合取范式的表达式，这是一种说法，你有一系列由or连接的表达式，它们都必须为真:

(a or b) and (b or !c) and (d or !e or f) ...

3- sat问题是找到一个满足表达式的解，其中每个or表达式恰好有3个布尔值可以匹配:

(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

这个问题的解可能是(A =T, b=T, c=F, d=F)。然而，目前还没有发现能在一般情况下在多项式时间内解决这个问题的算法。这意味着解决这个问题的最佳方法基本上是进行强力的猜测和检查，并尝试不同的组合，直到找到一个有效的组合。

3-SAT问题的特殊之处在于任何np完全问题都可以简化为3-SAT问题。这意味着如果你能找到一个多项式时间算法来解决这个问题，那么你就能得到1,000,000美元，更不用说全世界计算机科学家和数学家的尊重和钦佩了。

上面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问题，至少是“难” 和NP中的其他问题一样。

我们需要把算法和问题分开。我们编写算法来解决问题，它们以某种方式扩展。虽然这是一种简化，但如果缩放足够好，我们就用“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。

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