《什么是p问题、np问题和npc问题》由会员分享，可在线阅读，更多相关《什么是p问题、np问题和npc问题（21页珍藏版）》请在金锄头文库上搜索。
1、什么是P问题、NP问题和NPC问题 先用几句话简单说明一下时间复杂度n时间复杂度并不是表示一个程序解决问题需要花多少 时间，而是当问题规模扩大后，程序需要的时间长度 增长得有多快。n也就是说，对于高速处理数据的计算机来说，处理某 一个特定数据的效率不能衡量一个程序的好坏，而应 该看当这个数据的规模变大到数百倍后，程序运行时 间是否还是一样，或者也跟着慢了数百倍，或者变慢 了数万倍。q不管数据有多大，程序处理花的时间始终是那么多的，我们 就说这个程序很好，具有O(1)的时间复杂度，也称常数级复 杂度；先用几句话简单说明一下时间复杂度q数据规模变得有多大，花的时间也跟着变得有多长 ，这个程序的时间
2、复杂度就是O(n)，比如找n个数 中的最大值；q而像冒泡排序、插入排序等，数据扩大2倍，时间 变慢4倍的，属于O(n2)的复杂度。q还有一些穷举类的算法，所需时间长度成几何阶数 上涨，这就是O(an)的指数级复杂度，甚至O(n!)的 阶乘级复杂度。q不会存在O(2*n2)的复杂度，因为前面的那个“2”是 系数，根本不会影响到整个程序的时间增长。先用几句话简单说明一下时间复杂度q同样地，O (n3+n2)的复杂度也就是O(n3)的复 杂度。q因此，我们会说，一个O(0.01*n3)的程序的效率 比O(100*n2)的效率低，尽管在n很小的时候，前 者优于后者，但后者时间随数据规模增长得慢，最 终
3、O(n3)的复杂度将远远超过O(n2)。我们也说， O(n100)的复杂度小于O(1.01n)的复杂度。先用几句话简单说明一下时间复杂度n容易看出，前面的几类复杂度被分为两种级别，其中 后者的复杂度无论如何都远远大于前者：q一种是O(1),O(log(n),O(na) 等，我们把它叫做多项式级的 复杂度，因为它的规模n出现在底数的位置；q另一种是O(an)和O(n!)型复杂度，它是非多项式级的，其 复杂度计算机往往不能承受。n当我们在解决一个问题时，我们选择的算法通常都需 要是多项式级的复杂度，非多项式级的复杂度需要的 时间太多，往往会超时，除非是数据规模非常小。不可解问题 n自然地，人们会想
4、到一个问题：会不会所有的问题都 可以找到复杂度为多项式级的算法呢？n答案是否定的。有些问题甚至根本不可能找到一个正 确的算法来，这称之为“不可解问题”(Undecidable Decision Problem)。n例如：q Hamilton回路。q问题是这样的：给你一个图，问你能否找到一条经过每个顶 点一次且恰好一次（不遗漏也不重复）最后又走回来的路（ 满足这个条件的路径叫做Hamilton回路）。q这个问题现在还没有找到多项式级的算法。事实上，这个问 题就是我们后面要说的NPC问题。 P类问题 n如果一个问题可以找到一个能在多项式的时间 里解决它的算法，那么这个问题就属于P问题 。nP是英文
5、单词多项式的第一个字母。 NP问题 n在这里强调，NP问题不是非P类问题。nNP问题是指可以在多项式的时间里验证一个 解的问题。NP问题的另一个定义是，可以在 多项式的时间里猜出一个解的问题。 q比方说，我RP很好，在程序中需要枚举时，我可 以一猜一个准。q现在某人拿到了一个求最短路径的问题，问从起点 到终点是否有一条小于100个单位长度的路线。它 根据数据画好了图，但怎么也算不出来，于是来问 我：你看怎么选条路走得最少？NP问题q我说，我RP很好，肯定能随便给你指条很短的路出来。然后 我就胡乱画了几条线，说就这条吧。那人按我指的这条把权 值加起来一看，嘿，神了，路径长度98，比100小。于是
6、答 案出来了，存在比100小的路径。q别人会问他这题怎么做出来的，他就可以说，因为我找到了 一个比100 小的解。q在这个题中，找一个解很困难，但验证一个解很容易。验证 一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的 时间把我猜的路径的长度加出来。q那么，只要我RP好，猜得准，我一定能在多项式的时间里解 决这个问题。我猜到的方案总是最优的，不满足题意的方案 也不会来骗我去选它。这就是NP问题。 NP问题n当然有不是NP问题的问题，即你猜到了解但 是没用，因为你不能在多项式的时间里去验证 它。n一个经典的例子，它指出了一个目前还没有办 法在多项式的时间里验证一个解的问题。q很显然，
7、前面所说的Hamilton回路是NP问题，因为 验证一条路是否恰好经过了每一个顶点非常容易。q但我要把问题换成这样：试问一个图中是否不存在 Hamilton回路。这样问题就没法在多项式的时间里 进行验证了，因为除非你试过所有的路，否则你不 敢断定它“没有Hamilton回路”。NP问题n之所以要定义NP问题，是因为通常只有NP问 题才可能找到多项式的算法。n我们不会指望一个连多项式地验证一个解都不 行的问题存在一个解决它的多项式级的算法。n很显然，所有的P类问题都是NP问题。也就是 说，能多项式地解决一个问题，必然能多项式 地验证一个问题的解既然正解都出来了， 验证任意给定的解也只需要比较一下
8、就可以了 。 NP问题n关键是，人们想知道，是否所有的NP问题都 是P类问题。 n所有对NP问题的研究都集中在一个问题上， 即究竟是否有P=NP？ n目前为止这个问题还“啃不动”。但是，一个总 的趋势、一个大方向是有的。人们普遍认为， P=NP不成立，也就是说，多数人相信，存在 至少一个不可能有多项式级复杂度的算法的 NP问题。 NPC问题n人们如此坚信PNP是有原因的，就是在研究 NP问题的过程中找出了一类非常特殊的NP问 题叫做NP-完全问题，也即所谓的 NPC问题。 C是英文单词“完全”的第一个字母。正是NPC 问题的存在，使人们相信PNP。n为了说明NPC问题，我们先引入一个概念 约化
9、(Reducibility，有的资料上叫“归约”) 约化n一个问题A可以约化为问题B的含义即是，可 以用问题B的解法解决问题A，或者说，问题A 可以“变成”问题B。 n “问题A可约化为问题B”有一个重要的直观意 义：B的时间复杂度高于或者等于A的时间复 杂度。也就是说，问题A不比问题B难。q这很容易理解。既然问题A能用问题B来解决，倘若 B的时间复杂度比A的时间复杂度还低了，那A的算 法就可以改进为B的算法，两者的时间复杂度还是 相同。 约化n约化具有一项重要的性质：约化具有传递性。如果问 题A可约化为问题B，问题B可约化为问题C，则问题 A一定可约化为问题C。 n约化的标准概念：如果能找到
10、这样一个变化法则，对 任意一个程序A的输入，都能按这个法则变换成程序 B的输入，使两程序的输出相同，那么我们说，问题 A可约化为问题B。n我们所说的“可约化”是指的可“多项式地”约化 (Polynomial-time Reducible)，即变换输入的方法 是能在多项式的时间里完成的。约化的过程只有用多 项式的时间完成才有意义。 NPC问题nNPC问题的定义非常简单。同时满足下面两个 条件的问题就是NPC问题。q首先，它得是一个NP问题；q然后，所有的NP问题都可以约化到它。n证明一个问题是 NPC问题也很简单。q先证明它至少是一个NP问题，q再证明其中一个已知的NPC问题能约化到它（由约 化
11、的传递性，则NPC问题定义的第二条也得以满足 ；q至于第一个NPC问题是怎么来的，下文将介绍）， 这样就可以说它是NPC问题了。 NPC问题n既然所有的NP问题都能约化成NPC问题，那 么只要任意一个NPC问题找到了一个多项式的 算法，那么所有的NP问题都能用这个算法解 决了，NP也就等于P 了。n因此前文才说，“正是NPC问题的存在，使人 们相信PNP”。我们可以就此直观地理解， NPC问题目前没有多项式的有效算法，只能用 指数级甚至阶乘级复杂度的搜索。NP-Hard问题 nNP-Hard问题是这样一种问题，它满足NPC问 题定义的第二条但不一定要满足第一条n即NP-Hard问题要比 NPC
12、问题的范围广。 NPC问题nNPC问题是存在的。确实有这么一个非常具体 的问题属于NPC问题。 n逻辑电路问题是NPC类问题的“鼻祖”。是第一 个NPC问题。其它的NPC问题都是由这个问题 约化而来的。n逻辑电路问题是指的这样一个问题：给定一个 逻辑电路，问是否存在一种输入使输出为True 。逻辑电路问题n逻辑电路问题属于NPC问题。这是有严格证明 的。它显然属于NP问题，并且可以直接证明 所有的NP问题都可以约化到它。n证明过程相当复杂，其大概意思是说任意一个 NP问题的输入和输出都可以转换成逻辑电路 的输入和输出（想想计算机内部也不过是一些 0和1的运算），因此对于一个NP问题来说， 问题转化为了求出满足结果为True的一个输入 （即一个可行解）。NPC 问题n有了第一个NPC 问题后，一大堆NPC问题就 出现了，因为再证明一个新的NPC问题只需要 将一个已知的NPC问题约化到它就行了。n后来，Hamilton 回路成了NPC问题，TSP问 题也成了NPC问题。
