NP完全问题是那些既是NP困难又在复杂性类NP中的问题。因此，要证明任何给定的问题都是NP完全的，你需要证明这个问题既在NP中，也是NP困难的。

属于NP复杂性类的问题可以在多项式时间内非确定性地解决，并且可以在多项式时间内验证NP问题的可能解决方案（即证书）的正确性。

k-clique问题的非确定性解决方案的一个例子如下：

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

2）验证这些k个节点形成一个团。

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

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

显示一个问题是NP-hard通常涉及使用多项式时间映射从其他NP-hard问题减少到您的问题：http://en.wikipedia.org/wiki/Reduction_（复杂性）

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

• 决策问题：答案为是的或不的问题。

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

P

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

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

示例

给定一个连通图G，它的顶点可以用两种颜色着色，这样就没有边是单色的了吗？

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

NP

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

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

示例

整数分解在NP中。这是给定整数n和m的问题，是否有一个整数f和1 < f < m，使得f除以n（f是n的一个小因子）？

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

NP完全

NP完全是一个复杂性类，它表示NP中所有问题X的集合，对于这些问题，可以在多项式时间内将任何其他NP问题Y减少到X。

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

示例

3-SAT。这是一个问题，其中我们给出了一个3分句析取（ORs）的连词（ANDs），形式为

(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中和它们不一定是决策问题。

这里的确切定义是问题#0是NP难的，如果存在NP完全问题#1，使得#1在多项式时间内可约化为#0。

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

示例

停机问题是一个NP难问题。这是一个给定程序P和输入I的问题，它会停止吗？这是一个决策问题，但它不在NP中。很明显，任何NP完全问题都可以简化为这个问题。再举一个例子，任何NP完全问题都是NP难的。

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

P=NP

这是计算机科学中最著名的问题，也是数学科学中最重要的悬而未决的问题之一。事实上，0号提供一百万美元来解决这个问题（斯蒂芬·库克在克莱网站上的1号很好）。

很明显P是NP的一个子集。悬而未决的问题是NP问题是否有确定性多项式时间解。人们普遍认为它们没有。这是最近一篇关于P=NP问题最新（和重要性）的优秀文章：P与NP问题的状态。

关于这个主题的最好的书是Garey和Johnson的计算机和难以捉摸。

这是对所提问题的非正式回答。

3233可以写成另外两个大于1的数的乘积吗？有没有办法绕着所有柯尼斯堡七桥走一次而不走两次桥？这些是具有共同特征的问题的例子。如何有效地确定答案可能不明显，但如果答案是“是”，那么有一个简短快速的检查证明。在第一种情况下，61的非平凡因子分解（53是另一个主要因子）；在第二种情况下，走桥的路线（符合约束）。

决策问题是一组答案为是或否的问题的集合，这些问题只在一个参数中变化。假设问题COMPOSITE={“n复合吗”：n是整数}或EULERPATH={“图G有欧拉路径吗？”：G是有限图}。

现在，一些决策问题适合于高效的算法，如果不是显而易见的算法。欧拉在250多年前发现了一种有效的算法来解决像“柯尼斯堡七桥”这样的问题。

另一方面，对于许多决策问题，如何得到答案并不明显-但是如果你知道一些额外的信息，那么如何证明你得到了正确的答案是显而易见的。复合是这样的：试验除法是显而易见的算法，它很慢：要分解一个10位数字，你必须尝试大约100,000个可能的除数。但是，例如，如果有人告诉你61是3233的除数，简单的长除法是一种有效的方法来证明它们是正确的。

复杂性类NP是决策问题的类别，其中“是”的答案具有简短的状态，快速检查证明。就像复合。重要的一点是，这个定义没有说明问题有多难。如果你有一个正确、有效的方法来解决决策问题，仅仅写下解决方案中的步骤就足够了。

算法研究仍在继续，新的聪明算法一直在创造。一个你今天可能不知道如何有效解决的问题，明天可能会有一个有效（如果不明显）的解决方案。事实上，研究人员直到2002才找到了复合的有效解决方案！有了所有这些进步，人们真的不得不怀疑：有短证明只是一种错觉吗？也许第一个适合高效证明的决策问题有一个有效的解决方案？没人知道。

也许对这一领域最大的贡献是发现了一类特殊的NP问题。通过研究用于计算的电路模型，斯蒂芬·库克发现了NP品种的一个决策问题，可以证明它与其他每问题一样难或更难。第一个问题的有效解决方案可以用来创建NP中任何其他问题的有效解决方案。不久后，理查德·卡普证明了许多其他决策问题也可以达到同样的目的。从某种意义上说，这些问题是NP中“最难”的问题，被称为NP完全问题。

当然，NP只是决策问题中的一类，很多问题并不是这样自然表述的：“求N的因子”、“求G中访问每个顶点的最短路径”、“给出一组变量赋值，使以下布尔表达式成立”。尽管人们可能会非正式地谈论一些此类问题“在NP中”，但技术上这并没有多大意义——它们不是决策问题。其中一些问题甚至可能具有与NP完全问题相同的能力：对这些（非决策）问题的有效解决将直接导致任何NP问题的有效解决。这样的问题称为NP-hard。

我想我们可以更简洁地回答它。我回答了一个相关问题，并从那里复制我的答案

但首先，一个NP难问题是一个我们不能证明存在多项式时间解的问题。一些“问题P”的NP硬度通常通过在多项式时间内将一个已经证明的NP难问题转换为“问题P”来证明。

要回答剩下的问题，你首先需要了解哪些NP难问题也是NP完全的。如果一个NP难问题属于集合NP，那么它是NP完全的。要属于集合NP，一个问题需要

（i）决策问题
（ii）问题的解的数量应该是有限的，每个解应该是多项式长度，并且
（iii）给定一个多项式长度解，我们应该能够说出问题的答案是否为yes/no

现在，很容易看出可能有许多不属于集合NP并且更难解决的NP难问题。作为一个直观的例子，我们需要找到实际时间表的旅行推销员的优化版本比旅行推销员的决策版本更难，我们只需要确定长度<=k的时间表是否存在。

在不涉及技术细节的情况下解释P v. NP等问题的最简单方法是将“单词问题”与“多项选择问题”进行比较。

当你试图解决一个“单词问题”时，你必须从头开始找到解决方案。当你试图解决“多项选择题”时，你有一个选择：要么像解决“单词问题”一样解决它，要么尝试插入给你的每个答案，并选择适合的候选答案。

经常发生的情况是，“多项选择题”比相应的“单词问题”容易得多：替换候选答案并检查它们是否合适可能需要比从头开始寻找正确答案少得多的努力。

现在，如果我们同意多项式时间“容易”的努力，那么类P将由“简单单词问题”组成，而类NP将由“简单选择题”组成。

P v. NP的本质是这样一个问题：“有没有比单词题更容易的简单的选择题？”也就是说，是否有一些问题可以很容易地验证给定答案的有效性，但从头开始找到答案却很困难？

现在我们已经直观地理解了NP是什么，我们必须挑战我们的直觉。事实证明，在某种意义上，存在一些“多项选择题”中最难的问题：如果一个人能找到其中一个问题的解决方案，那么他将能够找到所有NP问题的解决方案！40年前库克发现这一点时，这完全是一个惊喜。这些“其中最难的”问题被称为NP-hard。如果你找到其中一个“单词题的解决方案”，那么你将自动为每个“简单的多项选择题”找到一个“单词题的解决方案”！

最后，NP完全问题是那些同时是NP和NP难的问题。按照我们的类比，它们同时是“像选择题一样容易”和“最难的是单词问题”。

P（多项式时间）：顾名思义，这些问题可以在多项式时间内解决。

NP（非确定性多项式时间）：这些是可以在多项式时间内验证的决策问题。这意味着，如果我声称某个特定问题有多项式时间解，你要求我证明它。然后，我会给你一个证明，你可以很容易地在多项式时间内验证。这类问题称为NP问题。注意，这里我们不是在讨论这个问题是否有多项式时间解。但我们谈论的是在多项式时间内验证给定问题的解。

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

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

我环顾四周，看到了许多长长的解释。这里有一个小图表，可能对总结有用：

注意难度是如何从上到下增加的：任何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

关于Yes或No条目的注释：

• *也是P的NP问题在P时间内是可解的。
• **一个同样是NP完全的NP困难问题在P时间内是可验证的。
• ***NP完全问题（所有这些问题都形成了NP难的子集）可能是。NP难的其余部分不是。

我还发现这个图在查看所有这些类型如何相互对应方面非常有用（更多地注意图表的左半部分）。

对于这个特定的问题有很好的答案，所以没有必要写我自己的解释。所以我将尝试用关于不同类别的计算复杂性的优秀资源做出贡献。

对于那些认为计算复杂性只是关于P和NP的人来说，这里是最详尽的资源是关于不同的计算复杂性问题。除了OP问的问题，它列出了大约500个不同类别的计算问题，并有很好的描述，以及描述该类的基础研究论文列表。

据我所知，np-hard问题并不比np完备问题“难”。事实上，根据定义，每个np完全问题都是：

1. 在np
2. np-hard

——算法介绍（第3版），Cormen，Leiserson，Rivest和Stein，第1069页

条件1.和2.翻译成英语：

1. 语言L在NP中，并且
2. 每个NP语言都是多项式时间可约化为语言L。

除了其他很好的答案，以下是人们用来显示NP，NP-完全和NP-hard之间区别的典型模式：

找到一些有趣的定义：