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)。我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。
P、NP、NPC、NPH问题的区别和联系
P问题
如果⼀个问题能找到在多项式时间内解决它的算法，那么我们说该问题是P类问题。P是多项式（Polynomial）的第⼀个字母。⽐如排
序问题就是⼀个P问题，因为我们可以找到⼀个时间复杂度为O(n2)O(n2)的冒泡排序算法。
NP问题
⼀些问题我们很难在多项式时间内找到解决问题的算法， 但是如果别⼈给了我⼀个解，我可以很快地验证该解是不是问题的正确答案。
⽐如在汉密尔顿回路问题中，我想验证⼀条路径是否正确，则验证路径是否正确的时间复杂度为O(n)O(n)，为多项式级的时间复杂度。
也就是说直接找NP问题的⼀个解可能很慢，当验证NP问题的解却很快。
NPC问题
所有P问题都是NP问题，因为能在多项式时间内解决的问题也能够在多项式时间内验证解的正确性。
是否所有的NP问题都是P问题，这就是著名的“P对NP问题（P=NP?）”。在2000年美国的Clay数学研究所公布的七个千年数学难题
中，P对NP问题位居榜⾸，可见解决该问题的难度。由于直接证明P对NP问题过于复杂，⼈们引⼊了另⼀类问题--NPC问题（NP -complete，NP-完全问题）。
规约
假设有两个问题A和B，对问题A的输⼊a经过某种规则转换为对问题B的输⼊b，⽽A(a)和B(b)的结果相同，也就是说我们可以将求解A
问题转换为求解B问题，或者说可以⽤解决问题B的⽅法解决问题A，那我们称A可以归约（reducibility，或“约化”）到B。
超级NP问题
是否可以将若⼲相对不那么复杂NP问题不断归约，从⽽得到⼀个最难的“超级NP问题”，所有的NP问题都可以归约到这个“超级NP问
题”，只要解决了这个“超级NP问题”，那么也就意味着所有NP问题都可以被解决。事实上，存在这样的⼀类“超级NP问题”，这也就是我们所
说的NPC问题。
NPC问题的定义如下：如果⼀个问题Q，它满⾜以下两条性质：(1). Q是NP问题
什么是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)。我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。
P、NP、NP-hard、NPC问题
P问题：⼀个问题可以在多项式的时间得到解决。P为英⽂polynominal的⾸字母。多项式时间的时间复杂度例如O(n)、O(n^2)等等。
NP问题：NP问题可能没有⼀个已知的快速解决⽅案。但如果能够在多项式的时间内验证⼀个解是否正确，则称此问题为NP问题。例如根
据数据画好了⼀个图。求解能否找到权重和⼩于100的⽣成树。这个问题可以在多项式的时间内得到验证。假设你运⽓好，随⼿⼀画就得到
了⼩于100的⽣成树，验证的⽅法只需要将⽣成树的所有树边权重相加。时间复杂度为O(V)。V代表树的结点树，⽣成树的边数为|V|-1。
提到NPC问题之前需要了解的概念是规约。例如⼀个问题A可以约化为问题B的含义是，可以⽤问题B的解法来解决问题A。或者说A可以转
化为B。例如求⼀元⼀次⽅程可以规约到求⼀元⼆次⽅程。将⼀元⼆次⽅程的⼆次项系数变为0。这样两个问题就等价了。通过实例也可看出
问题B不⽐问题A简单，即问题B的时间复杂度⾼于或者等于A。规约是具有传递性的。A规约成B，B规约成C，则A能够规约成C。
通过不断地规约，我们能得到复杂度更⾼但是应⽤范围更⼴的算法来代替复杂度虽低但是应⽤范围⼩的⼀类问题的算法。根据传递性，最终
可以得到⼀个复杂度最⾼，并且可以解决所有NP问题的NP问题。这就是NPC问题，即NP完全问题。NPC不⽌⼀个，⽽是⼀系列问题。
证明⼀个问题是NPC问题的步骤：1.⾸先要证明此问题是⼀个NP问题。2.证明⼀个已知的NPC问题能够规约到此问题。已知的NPC问题，
给定⼀个逻辑电路，是否存在⼀种输⼊使得输出为True。所有的NP问题都可以规约到逻辑电路问题。直观地解释是计算机中所有的程序最
终都转化成01组成的机器语⾔执⾏。
另外⼀个⽐较神奇的问题是，因为NPC问题是NP问题不断规约⽽来的，所以如果能证明⼀个NPC问题可以在多项式时间内解决。那么所有
的NP问题都能在多项式时间内解决。即NP=P。遗憾的是此题⽬前⽆解。
