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

如果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 = P，那么我们就可以比我们之前认为的更快地解决非常困难的问题。如果我们在P(多项式)时间内只解决了一个np -完全问题，那么它可以应用于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美元，更不用说全世界计算机科学家和数学家的尊重和钦佩了。

I have heard an explanation, that is:" NP-Completeness is probably one of the more enigmatic ideas in the study of algorithms. "NP" stands for "nondeterministic polynomial time," and is the name for what is called a complexity class to which problems can belong. The important thing about the NP complexity class is that problems within that class can be verified by a polynomial time algorithm. As an example, consider the problem of counting stuff. Suppose there are a bunch of apples on a table. The problem is "How many apples are there?" You are provided with a possible answer, 8. You can verify this answer in polynomial time by using the algorithm of, duh, counting the apples. Counting the apples happens in O(n) (that's Big-oh notation) time, because it takes one step to count each apple. For n apples, you need n steps. This problem is in the NP complexity class.

如果一个问题可以证明它既NP-Hard，又在多项式时间内可验证，那么它就被归类为NP-complete。在不深入讨论NP-Hard的情况下，只要说明某些问题的多项式时间解还没有找到就足够了。也就是说，它需要n!(n !)步来解它们。然而，如果给你一个np完全问题的解，你可以在多项式时间内验证它。

np完全问题的一个经典例子是旅行商问题。”

作者:ApoxyButt 来自:http://www.everything2.com/title/NP-complete

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