P和NP问题详解

时间复杂度：时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，则这个程序的时间复杂度就是O(n)。多项式级的复杂度：如O(1)，O(log(n))，O(n^a)等——注意它的规模n出现在底数的位置！非多项式级的复杂度：如：O(a^n)和O(n!)等。P/NP问题：P问题即为所有可以由一个确定型图灵机在多项式表达的时间内解决的问题；NP问题由所有可以在多项式时间内验证解是否正确的决定问题组成，或者等效的说，那些解可以在非确定型图灵机上在多项式时间内找出的问题的集合。简单地说，P问题是指可以在多项式复杂度的时间内解决的问题，NP是可以在多项式复杂度的时间内验证解是否是正确的问题。P属于NP。NP=Non-deterministicPolynomial。Example：当你计算两个数字的和时，这类问题很快就经过一系列有限的基本步骤而解出来了，这就是一个P问题；另一类问题计算过程比较繁琐，但验证答案却很容易，比如把整数44427进行因数分解，求解过程可能会很费时，但如果告诉你答案是177×251，简单计算即可验证答案是对的，这类问题（分解因子）就被归为NP问题。NP问题有很多，例如著名的推销员旅行问题（TravelSalemanProblemorTSP）：假设一个推销员需要从香港出发，经过广州，北京，上海，…，等n个城市，最后返回香港。任意两个城市之间都有飞机直达，但票价不等。现在假设公司只给报销C元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于C？推销员旅行问题显然是NP的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于C的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排！但n很大时，这将是个天文数字。Reducibility（“约化”或“归约”）：一个问题A可以约化为问题B的含义即是，可以用解决问题B的解法来解决问题A，或者说，问题A可以“变成”问题B。如：一元一次方程可以“归约”为一元二次方程。问题A可“约化”为问题B直观意义：B的时间复杂度高于或者等于A的时间复杂度。也就是说，问题A不比问题B难。NPC（NP-Complete）：这个问题是一个NP问题；所有的NP问题都可以约化到它。简单意思是NP里最难的问题。NPH（NP-Hard）：所有的NP问题都可以约化到它。NPC属于NPH。旅行推销员问题是数图论中最著名的问题之一，其另一种变形问题即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds，Cook和Karp等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法。不过，迄今为止，这类问题中没有一个找到有效算法。一些问题：P=NP？：克雷数学研究所高额悬赏的七个千禧年难题之一，同时也是计算机科学领域的最大难题，关系到计算机完成一项任务的速度到底有多快。P=NP？简单地说，就是是否每一个容易验证正确性的问题都能很“快”地计算出来？比如说，要验证一个整数是否整除另一个整数是很“快”的，那么给出一个整数，是否能很“快”找出它的一个因子？每个NP问题，可以规约到NPC，不严格的讲，NPC是NP类中“最难”的问题，也就是说它们是最可能不属于P类的。所以，若任何一个NPC的问题在P内，则可以推出P=NP。不幸的是，很多重要的问题被证明为NPC问题，但没有一个有已知快速的算法，即不是P问题。计算机科学家现在相信P，NP，和NPC类之间的关系如图中所示，其中P和NPC类不交。主流的推测是P不等于NP，很多应用算法就是基于这样的假设，而许多加密算法的保密性也是建立在P!=NP的前提上的，比如说著名的RSA（公钥加密算法：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。）。