什么是P、NP和NPC复杂性问题精要.pdf

  什么是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) 的复杂度。     容易看出 ，前面的几类复杂度被分为两种级别 ，其中后者的复杂度无论如何都远远大于前 者 ：一种是O(1),O(log(n)),O(n^a)等 ，我们把它叫做多项式级的复杂度 ，因为它的规模n出现在 底数的位置 ；另一种是O(a^n)和O(n!)型复杂度 ，它是非多项式级的 ，其复杂度计算机往往不能 承受。当我们在解决一个问题时 ，我们选择的算法通常都需要是多项式级的复杂度 ，非多项式 级的复杂度需要的时间太多 ，往往会超时 ，除非是数据规模非常小。     自然地 ，人们会想到一个问题 ：会不会所有的问题都可以找到复杂度为多项式级的算法呢 ？ 很遗憾 ，答案是否定的。有些问题甚至根本不可能找到一个正确的算法来 ，这称之为“不可解 问题”(Undecidable Decision Problem)。The Halting Problem就是一个著名的不可解问题 ，在 我的Blog上有过专门的介绍和证明。再比如 ，输出从1到n这n个数的全排列。不管你用什么方 法 ，你的复杂度都是阶乘级 ，因为你总得用阶乘级的时间打印出结果来。有人说 ，这样的“问 题”不是一个“正规”的问题 ，正规的问题是让程序解决一个问题 ，输出一个“YES”或“NO” （这被 称为判定性问题 ），或者一个什么什么的最优值 （这被称为最优化问题 ）。那么 ，根据这个定 义 ，我也能举出一个不大可能会有多项式级算法的问题来 ：Hamilton回路。问题是这样的 ：给 你一个图 ，问你能否找到一条经过每个顶点一次且恰好一次 （不遗漏也不重复 ）最后又走回来 的路 （满足这个条件的路径叫做Hamilton回路 ）。这个问题现在还没有找到多项式级的算法。 事实上 ，这个问题就是我们后面要说的NPC问题。     下面引入P类问题的概念 ：如果一个问题可以找到一个能在多项式的时间里解决它的算法 ， 那么这个问题就属于P问题。P是英文单词多项式的第一个字母。哪些问题是P类问题呢 ？通常 NOI和NOIP不会出不属于P类问题的题目。我们常见到的一些信息奥赛的题目都是P问题。道 理很简单 ，一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。     接下来引入NP问题的概念。这个就有点难