什么是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是可以用确定性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。
如果我弄错了，请告诉我。
如果你想找一个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中的其他问题一样。
NP-Complete指的是非常具体的东西，你必须小心，否则你会弄错定义。首先，NP问题是一个是/否问题
对于答案为"是"的问题的每个实例都有多项式时间证明，即答案为"是"，或者(等价地) 存在一种多项式时间算法(可能使用随机变量)，如果问题实例的答案是“是”，那么它有非零概率回答“是”，如果答案是“否”，则它会在100%的时间内回答“否”。换句话说，该算法的假阴性率必须小于100%，并且没有假阳性。
问题X是np完全的，如果
X在NP中，并且 对于NP中的任何问题Y，都有一个从Y到X的“约简”:一个多项式时间算法，将Y的任何实例转换为X的实例，当且仅当X实例的答案是“是”时，Y实例的答案是“是”。
如果X是NP完全的，并且存在一个确定性的多项式时间算法，可以正确地解决X的所有实例(0%假阳性，0%假阴性)，那么NP中的任何问题都可以在确定性多项式时间中解决(通过归约到X)。
So far, nobody has come up with such a deterministic polynomial-time algorithm, but nobody has proven one doesn't exist (there's a million bucks for anyone who can do either: the is the P = NP problem). That doesn't mean that you can't solve a particular instance of an NP-Complete (or NP-Hard) problem. It just means you can't have something that will work reliably on all instances of a problem the same way you could reliably sort a list of integers. You might very well be able to come up with an algorithm that will work very well on all practical instances of a NP-Hard problem.
