浅谈NP问题

np问题通俗解释
NP问题是指“非确定性多项式时间”问题，也称为不可解问题。

它是计算机科学中的一个重要问题类别。

通俗来说，NP问题是指那些可以在多项式时间内验证是否解
答正确的问题，但尚未找到可以在多项式时间内解决的算法。

也就是说，虽然我们可以在多项式时间内检查一个给定解是否正确，但我们目前还没有找到一种高效的方法来找到一个解。

在计算理论中，NP问题是与P问题相对的一个概念。

P问题
是指可以在多项式时间内解决的问题。

一个经典的例子是旅行商问题。

在旅行商问题中，我们需要找到一条路径，使得旅行商可以经过多个城市，每个城市只到达一次，并且回到起点，同时总路径长度最短。

虽然我们可以在多项式时间内计算出给定路径的总长度，但当前还没有找到一种可以在多项式时间内找到最短路径的方法。

目前来说，还没有找到一种通用的解决NP问题的方法。

因此，研究人员一直在努力寻找解决这些问题的有效算法，或者找到一种方法来证明这些问题不存在多项式时间解决的算法。

NP的原理及定义和解释NP是非确定性多项式（Non-deterministic Polynomial）的简称，是计算机科学中的一个复杂性类。

NP问题是指可以在多项式时间内验证解的正确性的问题。

NP问题的解可以通过非确定性多项式算法在多项式时间内验证，但没有有效的多项式算法可以在多项式时间内求解。

因此，NP问题的求解是非常困难的，往往需要使用暴力或近似算法等方法。

定义：NP问题的定义可以分为两个方面：1. 证书存在性：对于一个给定的问题，如果存在一个证书（certificate），可以在多项式时间内验证其正确性，则该问题属于NP 问题。

2.多项式时间验证：对于给定的问题和一个潜在的解，可以在多项式时间内验证这个解是否是正确的。

NP问题的解法可以由以下两种形式描述：1.非确定性算法：对于一个给定的问题，非确定性算法可以通过猜测和尝试的方式，在多项式时间内找到问题的解。

这个算法可以通过多次猜测和尝试来验证潜在的解是否是正确的，但并没有给出一个确定性的步骤来找到解。

2.多项式时间验证算法：对于一个给定的问题和一个潜在的解，可以通过一个多项式时间的验证算法，验证这个解是否是正确的。

原理：NP问题的原理基于两个关键概念：证书存在性和多项式时间验证。

证书存在性是指对于一个给定的问题，存在一个证书（或称为证明）可以在多项式时间内验证其正确性。

证书可以是一组状态、数字、字符串等，通过这个证书可以验证一个给定的解是否正确。

这个证书可以被看作是一个“快速验证器”，它能够在多项式时间内验证问题的解的正确性。

多项式时间验证是指对于给定的问题和一个潜在的解，可以在多项式时间内验证这个解是否是正确的。

多项式时间验证算法可以通过一系列的计算和判断，来验证一个给定的解是否满足问题的条件。

这个验证算法的运行时间是一个多项式，在实际应用中可以被认为是“快速”的。

基于以上两个概念，可以得到一个重要的结论：如果一个问题是NP 问题，那么可以把它的解转换成一个证书，并使用多项式时间验证算法，来验证这个证书的正确性。

P NP NPC三者问题阐述1）”P对NP问题”是什么意思？首先说明一下问题的复杂性和算法的复杂性的区别，下面只考虑时间复杂性。

算法的复杂性是指解决问题的一个具体的算法的执行时间,这是算法的性质；问题的复杂性是指这个问题本身的复杂程度，是问题的性质.比如对于排序问题,如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息,则排序问题的复杂性是O(nlgn)，但是排序算法有很多，冒泡法是O（n^2），快速排序平均情况下是O(nlgn)等等,排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。

问题的复杂性不可能通过枚举各种可能算法来得到，一般都是预先估计一个值，然后从理论上证明。

为了研究问题的复杂性，我们必须将问题抽象，为了简化问题,我们只考虑一类简单的问题，判定性问题，即提出一个问题,只需要回答yes或者no的问题。

任何一般的最优化问题都可以转化为一系列判定性问题，比如求图中从A到B的最短路径，可以转化成：从A 到B是否有长度为1的路径？从A到B是否有长度为2的路径?…从A到B是否有长度为k的路径？如果问到了k的时候回答了yes，则停止发问，我们可以说从A到B的最短路径就是k。

如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。

P类问题就是所有复杂度为多项式时间的问题的集合.然而有些问题很难找到多项式时间的算法(或许根本不存在)，比如找出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。

比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了)。

这种可以在多项式时间内验证一个解是否正确的问题称为NP问题.显然,所有的P类问题都是属于NP问题的，但是现在的问题是,P是否等于NP?这个问题至今还未解决。

NP问题的字面解释非确定型多项式完全问题一、背景介绍1. NP问题的概念NP问题是计算机科学和数学领域中一个重要的概念，即“非确定性多项式时间”（Non-deterministic Polynomial time），它代表了一类能在多项式时间内被验证的问题。

这类问题的解决方案虽然不能在多项式时间内被找到，但一旦有了一个解，却能够在多项式时间内被验证。

简而言之，如果一个问题可以在多项式时间内被验证，则它是一个NP问题。

2. 多项式完全问题的概念多项式完全问题是一类特殊的NP问题，它具有以下两个性质：它是一个NP问题；任何一个NP问题都可以在多项式时间内规约到它。

也就是说，如果有一个多项式时间算法能够解决任何一个多项式完全问题，那么就能够解决所有的NP问题。

3. 非确定型多项式完全问题非确定型多项式完全问题是NP问题中最困难的一类问题，它要求在多项式时间内验证一个解的存在，并且这个验证需要非确定性算法。

换言之，虽然这类问题的解可以在多项式时间内被验证，但却无法在多项式时间内被求解。

非确定型多项式完全问题是计算理论中一个极具挑战性的问题。

二、定义和性质1. 非确定型多项式完全问题的定义非确定型多项式完全问题是指一个问题，如果它是一个NP问题，并且任何一个NP问题都可以在多项式时间内归约到它，那么它就是一个非确定型多项式完全问题。

每一个非确定型多项式完全问题都是NP 问题，但不是所有的NP问题都是非确定型多项式完全问题。

2. 非确定型多项式完全问题的性质非确定型多项式完全问题具有以下一些重要性质：（1）困难性：非确定型多项式完全问题是计算上的一类最困难问题，它们无法在多项式时间内被求解。

（2）通用性：任何一个NP问题都可以在多项式时间内归约到非确定型多项式完全问题，因此解决了一个非确定型多项式完全问题就意味着可以解决所有的NP问题。

（3）实际意义：非确定型多项式完全问题在实际生活中具有广泛的应用，例如在计划问题、调度问题、网络设计等方面都有重要的地位。

P问题、NP问题、NPC问题、NP难问题的概念2010-04-15 21:35 | (分类:默认分类)转自/view/3e968900a6c30c2259019e8f.html你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。

你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。

他们没有搞清楚NP问题和NPC问题的概念。

NP问题并不是那种“只有搜才行”的问题，NPC问题才是。

好，行了，基本上这个误解已经被澄清了。

下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。

接下来你可以看到，把NP问题当成是NPC问题是一个多大的错误。

还是先用几句话简单说明一下时间复杂度。

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。

也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。

不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。

还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。

不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。

同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。

因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。

什么是P问题、NP问题和NPC问题这或许是众多OIer最大的误区之一。

你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。

你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。

他们没有搞清楚NP问题和NPC问题的概念。

NP问题并不是那种“只有搜才行”的问题，NPC问题才是。

好，行了，基本上这个误解已经被澄清了。

下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC 问题，你如果不是很感兴趣就可以不看了。

接下来你可以看到，把NP问题当成是NPC问题是一个多大的错误。

还是先用几句话简单说明一下时间复杂度。

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。

也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。

不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。

还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。

不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。

同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。

因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。

谈⼀谈如何理解NP问题⼀概念引⼊1.1时间复杂度在计算机处理⼀个问题时，往往需要⼀定的时间，假设把这个问题复杂化（将这个问题进⾏扩展），那么把计算机处理这类问题的时间变化速率，称为解决这种问题所⽤算法的时间复杂度。

例如，⼀个枚举⼀定范围内的数字的问题，计算机所⽤时间会随着范围的变化⽽线性变化，由于是简单的枚举，所以时间复杂度可以记为O(n)，n可以代表这个范围⼤⼩。

在计算机处理问题时，由于算法设计不同，对应的时间复杂度也不⼀定相同。

1.2多项式级时间和⾮多项式级时间在众多的时间复杂度中，根据其表达式的特点，可以⼤致将它们划分为两个范畴，⼀个是多项式级⼀个是⾮多项式级。

它们各⾃表⽰什么意思呢？还记得⾼中数学中学习的函数吗，在学习不同函数时，最常做的⼀件事是观察它们的图像变化，可以发现，x作为底数的图像和x作为指数的图像在后期的变化简直有天壤之别。

这也正是需要将时间复杂度划分的原因（多项式级的时间复杂度在后期变化远⼩于⾮多项式级），将n作为底数的时间复杂度归为多项式级，n作为指数的归为⾮多项式级。

例如O(n)、O(log(n))、O(n^a)等就是多项式级的时间复杂度，像O(n!)和O(a^n)就是⾮多项式级的复杂度。

对于计算机来说需要处理的问题往往是很庞⼤的，如果采⽤⾮多项式级复杂度的算法，那么将浪费很⼤的资源。

1.3 P问题在解释了多项式级和⾮多项式级时间复杂度之后，P问题的概念就简单了。

对于众多的问题，通常把能够使⽤多项式级时间复杂度算法解决的问题称为P问题。

⼆什么叫NP问题2.1 约化⼀般，问题A可以约化为问题的B的解释是可以⽤解决问题B的⽅法解决问题A。

简单的说，也就是问题A是问题B的另⼀种形式，且问题A的复杂程度要⼩于等于问题B。

就像解⽅程组的问题，假如你会解⼆元⼀次⽅程组，那么你⼀定会解⼀元⼀次⽅程，在这个例⼦中，⼀元⼀次⽅程就是问题A，⼆元⼀次⽅程组就是问题B，问题A可以看作是问题B中另⼀个⾃变量系数为零的特殊“⼆元⼀次⽅程组”。

np 难问题的定义和分类
NP难问题在计算机科学中是一个重要的概念，涉及到多项式时间复杂性和确定性算法的问题。

具体来说，NP难问题指的是那些没有多项式时间复杂度的确定性算法来解决，但在多项式时间内能够验证解是否正确的问题。

NP问题是指非确定性多项式时间问题，即无法在多项式时间内找到确定性的解法，但可以在多项式时间内验证某个解是否正确的问题。

NP难问题通常被分为两类：NP完全问题和NP难问题。

NP完全问题是NP问题中最为困难的一类，指的是既是NP问题又是NP难问题的集合。

它们的特点是，即使利用了所有已知的算法和技巧，也无法在多项式时间内找到确定性的解法。

相比之下，NP难问题虽然没有多项式时间的确定性算法，但它们的难易程度可能不如NP完全问题。

在NP难问题的分类中，还有一些其他的问题类型，例如NP类问题、NP完全类问题和NP半完全问题等。

这些问题的分类主要是基于它们在NP问题中的关系和性质。

总之，NP难问题是计算机科学中的一个重要概念，涉及到多项式时间复杂性和确定性算法的问题。

它们通常被分为NP完全问题和NP难问题两类，其中NP完全问题是最为困难的一类。

解决这些问题的难度很高，但研究它们的性质和结构有助于更好地理解计算复杂性和算法设计等领域的知识。

NP问题规约NP问题规约是计算复杂性理论中的一个重要概念。

在计算复杂性理论中，P类问题是可以在多项式时间内解决的问题，而NP类问题是可以在多项式时间内验证一个解的问题。

NP问题规约指的是一个问题可以被多项式时间内归约到另一个问题，即一个问题的解可以在多项式时间内被用来解决另一个问题。

1. NP问题和P问题：P问题（可在多项式时间内解决的问题）：这些问题的解法可以在多项式时间内验证。

例如，多项式时间内验证一个给定的数是否是素数就是一个P问题。

NP问题（可在多项式时间内验证的问题）：这些问题的解可以在多项式时间内验证，但我们尚未找到一个能在多项式时间内解决它们的算法。

例如，旅行商问题是一个NP问题，因为如果给定一条路径，我们可以在多项式时间内验证它是否是最短路径。

2. NP问题规约：NP问题规约是指，如果问题A可以在多项式时间内归约到问题B，那么问题A就被规约到问题B。

这通常表示为 $A \leq_p B$。

这意味着，如果我们有一个能够在多项式时间内解决问题B的算法，我们也可以在多项式时间内解决问题A。

3. NP-完全问题：如果一个问题是NP问题，而且所有其他NP问题都可以在多项式时间内规约到它，那么这个问题被称为NP-完全问题。

证明一个问题是NP-完全的经典方法是通过展示它是一个NP问题，然后证明它是NP-困难的。

一个著名的NP-完全问题是布尔可满足性问题（SAT）。

4. 应用和重要性：问题等价性证明：NP问题规约在证明问题等价性中起着关键作用。

通过将一个问题规约到另一个已知的问题，我们可以证明它们是等价的。

算法设计：了解NP问题规约有助于设计更有效的算法。

如果我们可以将一个新问题规约到一个已知的问题，我们可以利用已知问题的算法来解决新问题。

计算复杂性理论：NP问题规约是计算复杂性理论中一项基础工具，有助于理解问题的相对难度和可解性。

总体而言，NP问题规约是计算复杂性理论中的一个强大的概念，它有助于我们理解问题的相对难度，设计高效的算法，并证明问题之间的等价性。

你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。

你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。

他们没有搞清楚NP问题和NPC问题的概念。

NP问题并不是那种“只有搜才行”的问题，NPC 问题才是。

好，行了，基本上这个误解已经被澄清了。

下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。

接下来你可以看到，把NP问题当成是NPC问题是一个多大的错误。

还是先用几句话简单说明一下时间复杂度。

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。

也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。

不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。

还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。

不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。

同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。

因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。

我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。

下面引入P类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。

P是英文单词多项式的第一个字母。

哪些问题是P类问题呢？通常NOI和NOIP不会出不属于P类问题的题目。

我们常见到的一些信息奥赛的题目都是P 问题。

道理很简单，一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。

接下来引入NP问题的概念。

这个就有点难理解了，或者说容易理解错误。

在这里强调（回到我竭力想澄清的误区上），NP问题不是非P类问题。

NP问题是指可以在多项式的时间里验证一个解的问题。

NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。

比方说，我RP很好，在程序中需要枚举时，我可以一猜一个准。

现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于100个单位长度的路线。

它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少？我说，我RP很好，肯定能随便给你指条很短的路出来。

然后我就胡乱画了几条线，说就这条吧。

那人按我指的这条把权值加起来一看，嘿，神了，路径长度98，比100小。

于是答案出来了，存在比100小的路径。

别人会问他这题怎么做出来的，他就可以说，因为我找到了一个比100 小的解。

在这个题中，找一个解很困难，但验证一个解很容易。

验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把我猜的路径的长度加出来。

那么，只要我RP好，猜得准，我一定能在多项式的时间里解决这个问题。

我猜到的方案总是最优的，不满足题意的方案也不会来骗我去选它。

这就是NP问题。

当然有不是NP问题的问题，即你猜到了解但是没用，因为你不能在多项式的时间里去验证它。

下面我要举的例子是一个经典的例子，它指出了一个目前还没有办法在多项式的时间里验证一个解的问题。

很显然，前面所说的Hamilton回路是NP问题，因为验证一条路是否恰好经过了每一个顶点非常容易。

但我要把问题换成这样：试问一个图中是否不存在Hamilton回路。

什么是P问题、NP问题和NPC问题●先用几句话简单说明一下时间复杂度1.时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。

2.也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。

3.不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；4.数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；5.而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。

6.还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。

7.不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。

8.同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。

9.因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。

我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。

10.容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者：1)一种是O(1),O(log(n)),O(n^a) 等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置；2)另一种是O(a^n)和O(n!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。

11.当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。

漫谈算法（三）NP问题漫谈算法（三）NP问题Keywords: NP Problme; NP-hard Problem; NP-complete Problem; P Problem[为什么写这类文章] 漫谈算法（零）序[这系列文章里会用到的一下符号和公式] 漫谈算法（番外篇）符号标记以及基本数学公式首先解释一下什么是NP问题，什么是NP hard问题，什么是NP 完全问题。

看下面的图，他们之间的关系表示的比较清楚。

P Problem：这个应该最易理解，就是一个问题可以在Polynominal的时间的得到解决，当然，是对于任意input size。

NP Problem：对于一类问题，我们可能没有一个已知的快速的方法得到问题的答案，但是如果给我们一个candidate answer，我们能够在polynominal的时间内验证这个candidate answer到底是不是我们已知问题的答案，这类问题叫做NP problem。

所以很显然P Problem是NP problem的一个子集。

NP-hard Problem：对于这一类问题，用一句话概括他们的特征就是“at least as hard as the hardest problems in NP Problem”，就是NP-hard问题至少和NP问题一样难。

NP-complete Problem：对于这一类问题，他们满足两个性质，一个就是在polynomial时间内可以验证一个candidate answer是不是真正的解，另一个性质就是我们可以把任何一个NP问题在polynomial的时间内把他的input转化，使之成为一个NP-complete 问题。

所以对于NP-hard问题，我们可以把他们分成两个部分，一部分可以用polynomial的时间验证一个candidate answer是不是真正的answer，这一部分问题组成了NP-complete集合。