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

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

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

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

编辑:正如其他人所注意到的，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完全问题的例子那么我建议你看一下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美元，更不用说全世界计算机科学家和数学家的尊重和钦佩了。

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