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

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完全是一类问题。

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

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

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

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

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

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

NP问题:-

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

Np问题的类型

NP完全 NP困难

NP完全问题:-

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

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

一些例子:

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

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 = P，那么我们就可以比我们之前认为的更快地解决非常困难的问题。如果我们在P(多项式)时间内只解决了一个np -完全问题，那么它可以应用于np -完全范畴内的所有其他问题。