NP问题:-

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

Np问题的类型

NP完全 NP困难

NP完全问题:-

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

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

一些例子:

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

基本上这个世界的问题可以分为

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完全问题的例子那么我建议你看一下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完全是一类问题。

P类由那些可以在多项式时间内解决的问题组成。例如，对于某个常数k，它们可以用O(nk)来求解，其中n是输入的大小。简单地说，您可以编写一个在合理时间内运行的程序。

NP类由那些在多项式时间内可验证的问题组成。也就是说，如果我们已知一个可能的解，那么我们可以在多项式时间内检验这个解是否正确。

一些例子是布尔可满足性(或SAT)问题，或哈密顿循环问题。在NP类中有很多已知的问题。

NP完全意味着问题至少和NP中的任何问题一样难。

它对计算机科学很重要，因为它已经证明了NP中的任何问题都可以转化为NP完备中的另一个问题。这意味着任何一个NP完全问题的解都是所有NP问题的解。

安全性中的许多算法依赖于NP困难问题没有已知解的事实。如果能找到解决方案，它肯定会对计算产生重大影响。

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

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