我四处寻找，看到了许多冗长的解释。 这里有一个小图表，总结起来可能有用:

请注意难度是如何从上到下递增的:任何NP都可以简化为NP完全，任何NP完全都可以简化为NP困难，所有这些都需要P(多项式)时间。

如果你能在P时间内解决一个更难的问题，那就意味着你找到了如何在P时间内解决所有更简单的问题的方法(例如，证明P = NP，如果你知道如何在P时间内解决任何NP-完全问题)。

____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V

“是”或“否”条目说明:

同样是P的NP问题可以在P时间内解决。 ** np -难问题，也是np -完全问题，在P时间内可验证。 *** np -完全问题(所有这些都构成了NP-hard的子集)可能是。其余的NP困难则不是。

我还发现这个图非常有用，可以看到所有这些类型是如何相互对应的(请更加注意图的左半部分)。

我假设您正在寻找直观的定义，因为技术定义需要相当长的时间来理解。首先，让我们记住一个基本概念来理解这些定义。

决策问题:回答是或不是的问题。

---

现在，让我们定义这些复杂性类。

P

P是一个复杂度类，表示所有决策问题的集合，可以在多项式时间内解决。

也就是说，给定一个问题的实例，答案是或否可以在多项式时间内决定。

例子

给定一个连通图G，它的顶点可以用两种颜色来着色，从而没有边是单色的吗?

算法:从一个任意顶点开始，将其涂成红色，将其所有邻居涂成蓝色，然后继续。当你用尽顶点时停止，或者你被迫让一条边的两端都是相同的颜色。

---

NP

NP是一个复杂度类，它表示所有决策问题的集合，其中答案是“是”的实例具有可以在多项式时间内验证的证明。

这意味着如果有人给我们一个问题的实例和一个证明(有时称为证人)，答案是肯定的，我们可以在多项式时间内检查它是否正确。

例子

整数因式分解是NP。这是一个给定整数n和m的问题，是否存在一个1 < f < m的整数f，使得f能整除n (f是n的一个小因子)?

这是一个决策问题，因为答案是是或不是。如果有人给我们一个问题的实例(他们给了我们整数n和m)和一个1 < f < m的整数f，并声称f是n的因数(证书)，我们可以通过执行n / f的除法在多项式时间内检查答案。

---

非完全多项式

NP- complete是一个复杂度类，它表示NP中所有问题X的集合，其中可以在多项式时间内将任何其他NP问题Y减少到X。

直观地说，这意味着如果我们知道如何快速解决X，我们就可以快速解决Y。准确地说，Y可约为X，如果有一个多项式时间算法f在多项式时间内将Y的实例Y转换为X = f(Y)的实例X，其性质是Y的答案是yes，当且仅当f(Y)的答案是yes。

例子

3-SAT。在这个问题中，我们得到了一个3子句析取(or)的连词(and)，这种形式的语句

(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)

其中，每个x_vij是一个布尔变量或有限预定义列表(x_1, x_2，…)中的一个变量的负数。x_n)。

可以看出，每一个NP问题都可以简化为3-SAT。这个证明是技术性的，需要使用NP的技术定义(基于非确定性图灵机)。这就是众所周知的库克定理。

NP完全问题之所以重要，是因为如果可以找到一个确定的多项式时间算法来解决其中一个问题，那么每个NP问题都可以在多项式时间内解决(一个问题可以统治所有问题)。

---

NP-hard

直观地说，这些问题至少和np完全问题一样难。注意，NP难问题不一定是NP问题，也不一定是决策问题。

这里的精确定义是，如果存在一个np完全问题Y，那么问题X是np难的，这样Y可以在多项式时间内约化为X。

但由于任何np完全问题都可以在多项式时间内化简为任何其他np完全问题，所以所有np完全问题都可以在多项式时间内化简为任何np难问题。那么，如果在多项式时间内存在一个NP难问题的解，那么在多项式时间内就存在所有NP问题的解。

例子

停止问题是np难问题。这个问题是给定一个程序P和输入I，它会停止吗?这是一个决策问题，但不属于NP范畴。很明显，任何np完全问题都可以简化为这个问题。另一个例子是，任何np完全问题都是np难的。

我最喜欢的np完全问题是扫雷问题。

---

P = NP

这是计算机科学中最著名的问题，也是数学科学中最重要的杰出问题之一。事实上，克莱研究所为解决这个问题提供了100万美元(斯蒂芬·库克在克莱网站上的文章相当不错)。

很明显P是NP的子集。悬而未决的问题是NP问题是否有确定的多项式时间解。人们普遍认为，事实并非如此。这里有一篇关于P = NP问题的最新(和重要性)的杰出文章:P vs NP问题的现状。

这方面最好的书是加里和约翰逊合著的《计算机与顽固性》。

除了其他很好的答案，下面是人们用来显示NP、NP- complete和NP- hard之间区别的典型模式:

根据我的理解，np-hard问题并不比np-complete问题“更难”。事实上，根据定义，每个np完全问题都是:

在NP np-hard

——介绍。Cormen, Leiserson, Rivest, and Stein所著的算法(3ed)，第1069页

条件1。和2。翻译成英语:

语言L在NP中，和 每一种NP语言都是多项式时间可约化为语言L。

NP完全问题是那些既NP- hard又属于NP复杂度类的问题。因此，为了证明任何给定的问题是NP完全的，你需要证明这个问题既是NP问题，又是NP难问题。

NP复杂度类的问题可以在多项式时间内非确定性地解决，NP复杂度类问题的可能解(即证书)可以在多项式时间内验证其正确性。

k团问题的非确定性解的一个例子是这样的:

1)从图中随机选择k个节点

2)验证这k个节点组成了一个团。

上述策略在输入图的大小上是多项式，因此k团问题属于NP。

注意，所有在多项式时间内确定可解决的问题也都属于NP。

说明一个问题是np困难的通常包括使用多项式时间映射从其他np困难问题减少到你的问题:http://en.wikipedia.org/wiki/Reduction_(complexity)

P(多项式时间):顾名思义，这些问题可以在多项式时间内解决。

NP (Non-deterministic-polynomial Time):可以在多项式时间内验证的决策问题。这意味着，如果我说有一个多项式时间解对于一个特定的问题，你要我证明它。然后，我会给出一个证明你可以在多项式时间内证明。这类问题被称为NP问题。注意，这里我们讨论的不是这个问题是否存在多项式时间解。但我们讨论的是在多项式时间内验证给定问题的解。

NP- hard:这些问题至少和NP中最难的问题一样难。如果我们能在多项式时间内解决这些问题，我们就能解决任何可能存在的NP问题。请注意，这些问题不一定是NP问题。这意味着，我们可能在多项式时间内验证这些问题的解。

NP完全:这些问题既是NP问题又是NP困难问题。这意味着，如果我们能解决这些问题，我们就能解决任何其他NP问题，这些问题的解可以在多项式时间内得到验证。