算法设计与分析什么是P问题、NP问题和NPC问题.ppt

1、什么是P问题、NP问题和NPC问题？时间复杂度并不意味着一个程序解决问题需要多长时间，而是当问题的规模扩大时，程序所需的时间长度增长得有多快。也就是说，对于一台高速处理数据的计算机来说，处理特定数据的效率不能衡量一个程序的质量，而应该看这个程序的运行时间是否相同，或者在数据的大小变得大了几百倍之后，它是否也慢了几百倍，或者慢了几万倍。不管数据有多大，程序的处理时间总是很长。我们说这个程序非常好，它的时间复杂度为0(1)，这也被称为常数级复杂度；时间复杂性、数据规模有多大以及需要多长时间。这个程序的时间复杂度是O(n)，比如找到N个数的最大值；例如，气泡排序、插入排序等。O(n2)的复杂性在于数

2、据扩展了两倍，而时间变慢了四倍。也有一些穷举算法，所需时间以几何顺序增加，这是O(an)的指数复杂度，甚至是O(n！)阶乘复杂性。没有O(2*n2)的复杂性，因为前“2”是一个系数，它根本不会影响整个程序的时间增长。时间复杂度。同样，O (n3 n2)的复杂性也是O (n3)的复杂性。因此，我们会说一个0.01*n3程序的效率低于0.100 * N2程序的效率。当N较小时，前者优于后者，但后者随数据规模增长缓慢，O(n3)的复杂度将远远超过O(n2)。我们还说，0(n100)的复杂度小于0(1.01n)。很容易看出，前者的复杂性分为两个层次，其中后者的复杂性在任何情况下都远远大于前者：一是O(

3、1)、O(log(n)、O(na)等。我们称它为多项式级复杂性，因为它的尺度n出现在底部；另一个是O(an)和O(n！)类型的复杂性，它是非多项式的，并且它的复杂性对于计算机来说通常是无法忍受的。当我们解决一个问题时，我们选择的算法通常需要多项式复杂度，而非多项式复杂度需要太多时间并且经常超时，除非数据规模非常小。自然，人们会想到一个问题：所有的问题都能找到多项式复杂度的算法吗？答案是否定的。有些问题甚至不可能找到正确的算法，这就是所谓的“不可判定的决策问题”。例子：汉密尔顿电路。问题是这样的：给你一个图，问你是否能找到一条路径，它通过每个顶点一次，精确一次(没有遗漏或重复)，然后再回来(满足

4、这个条件的路径叫做哈密尔顿电路)。这个问题没有多项式级算法。事实上，这个问题就是我们以后要讨论的NPC问题。p问题定义，如果一个问题可以找到一个算法，可以在多项式时间内解决它，那么这个问题属于p问题。p是英语单词多项式的第一个字母。这里要强调的是，NP问题不是一个非P类问题。NP问题是一个可以在多项式时间内验证解的问题。NP问题的另一个定义是可以在多项式时间内猜到一个解。例如，我的RP很好，当我需要在程序中枚举时，我可以一个接一个地猜。现在有人提出了寻找最短路径的问题，询问从起点到终点是否有长度小于100个单位的路线。它根据数据画了一幅画，但无法计算，所以它问我：你认为最起码的方法是什么？NP

5、问题，我说，我的RP(个性，运气)很好，我绝对可以给你一个短的出路。然后我随意画了几条线，说：“就是这里。”。这个人根据我指出的文章把重量加起来。嘿，上帝，路径长度是98，小于100。所以答案出来了，有一条小于100的路径。人们会问他这个问题是怎么产生的，他可以说出来，因为我找到了一个小于100的解。在这个问题上，很难找到解决办法，但很容易验证解决办法。验证一个解决方案只需要O(n)个时间复杂度，这意味着我可以花费O(n)个时间来计算路径的长度。所以，只要我的RP是好的，我的猜测是准确的，我就能在多项式时间内解决这个问题。我想方案总是最好的，不满足问题意思的方案不会骗我选择它。这是NP问题。N

6、P问题，当然，有一个问题不是NP问题，也就是说，你猜测和理解但它是无用的，因为你不能在多项式时间内验证它。一个经典的例子，它指出没有办法在多项式时间内验证一个解。显然，上面提到的哈密尔顿电路是一个NP问题，因为很容易验证一条路径是否只经过每个顶点。但是我想把这个问题变成这样：你在图表中有汉密尔顿电路吗？所以这个问题不能用多项式时间来验证，因为除非你尝试所有的方法，否则你不能断定它没有哈密顿回路。之所以要定义NP问题，是因为只有NP问题才能找到多项式的算法。我们不能指望多项式级算法来解决一个甚至不能验证解多项式的问题。显然，所有的P问题都是NP问题。也就是说，如果你能解决一个问题多项式，你必须验

7、证一个问题多项式的解。因为所有的正解都出来了，你只需要比较任何给定的解。关键是人们想知道是否所有的NP问题都是P型问题。所有关于NP问题的研究都集中在一个问题上，即是否存在P=NP？到目前为止，这个问题仍然“令人头疼”。然而，总的趋势和总的方向是存在的。一般认为P=NP不是真的，也就是说，大多数人认为一个多项式复杂度的算法至少有一个NP问题。人们对NP完全问题如此深信不疑是有原因的，即在研究NP问题的过程中，他们发现了一个非常特殊的NP问题，称为NP完全问题，也称为NPC问题。c是英语单词“complete”的第一个字母。是NPC让人们相信了民进党。为了说明NPC问题，我们首先引入一个概念约简

8、，在一些材料中称为“约简”。问题A可以归结为问题B的意义，即问题A可以用问题B的解来解决，或者问题A可以“化”为问题B。“问题A可以归结为问题B”有一个重要的直观意义：B的时间复杂度高于或等于A。也就是说，问题A不比问题B难.这很容易理解。由于问题甲可以由问题乙解决，如果问题乙的时间复杂度低于问题甲，则问题甲的算法可以改进为问题乙的算法，并且两者的时间复杂度相同。约简有一个重要的性质：约简是可传递的。如果问题甲可以化简为问题乙，问题乙可以化简为问题丙，那么问题甲就可以化简为问题丙。化简的标准概念是：如果我们能找到这样一个变化规律，那么任何一个程序甲的输入都可以根据这个规律转化为程序乙的输入，这

9、样两个程序的输出就相同了。 然后我们说问题A可以化为问题b。所谓“可约性”，是指“多项式时间可约性”，即变换输入的方法可以在多项式时间内完成。 简化过程只有在多项式时间内完成才有意义。NPC问题的定义，NPC问题的定义很简单。同时满足以下两个条件的问题是NPC问题。首先，这肯定是一个NP问题；然后，所有的NP问题都可以归结为它。证明NPC是个问题也很简单。首先证明它至少是一个NP问题，然后证明已知的NPC问题之一可以归结为它(通过归结的传递性，NPC问题的第二个定义可以得到满足；至于第一个NPC问题是如何产生的，将在以后介绍)，所以可以说这是一个NPC问题。既然所有的NP问题都可以归结为NPC

10、问题，那么只要任何一个NPC问题找到一个多项式算法，所有的NP问题都可以用这个算法来解决，而且NP等于p。因此，前一篇文章说，“是NPC使人们相信了PNP。”我们可以直观地理解，目前对于NPC问题还没有有效的多项式算法，只能以指数甚至阶乘的复杂度进行搜索。NP-Hard问题是这样一个问题，它满足NPC问题的第二个但不一定是第一个定义，即NP-Hard问题比NPC问题更广泛。相关概念概述： P，NP，NPC，NP-hard，问题P:可以在多项式时间内解决。NP:不能在多项式时间内求解或不确定是否能在多项式时间内求解，但可以在多项式时间内验证。NP完全问题，所有的NP问题都可以在多项式时间内归结为它的NP问题，即这个NPC问题已经解决，所有的NP问题都已经解决。Nphard:是一个NP难问题，所有的NP问题都可以在多项式时间内归结为它的问题(不一定是NP问题)。NPC问题，NPC问题存在。确实有一个非常具体的问题属于NPC。逻辑电路问题是NPC问题的“鼻祖”。是第一个NPC问题。其他NPC问题都是从这个问题中引申出来的。逻辑电路问题是指这样一个问题，给定一个逻辑电路，问是否有一个输入使输出为真。逻辑电路问题属于NPC问题。这一点得到了严格证明。它显然属于NP问题，可以直接证明所有的NP问题都可以归结为它。证明过程相当复杂，这大致意