P与NP问题

理论计算机初步：P vs NP - 问概述 ©Zhang-Zi, August 23, 2006 P = NP? 这个问题，作为理论计算机科学的核心问题，其声名早已经超越了这个领域。它是Clay研究所 的七个百万美元大奖问题之一，在2006国际数学家大会上，它是某个1小时讲座的主题。 要说起P和NP是什么东西，得先从算法的多项式时间复杂度谈起，注意，这里面的两个P都是指 Polynomial。 一个问题的规模指的是输入的总位数，比如一个n个数的排序问题，输入规模就是n。注意，在 某些时候，输入规模是要值得注意的，比如判定一个数n是否是一个质数这个问题，它的输入规 模并不是n，而是log(n)，因为一个数n用大约log(n)位就能示出来了，这也是为何枚举因子 判定素数的算法并不是多项式时间算法的原因。 如果一个算法，它能在以输入规模为参变量的某个多项式的时间内给出，则称它为多项式 时间算法。注意：这里的多项式时间是指算法运行的步数。一个算法是否是多项式算法，与计 算模型的具体的物理实现没有关系，虽然大多数假想的计算模型不可能有任何物理的实现。 P指确定型图灵机上的具有多项式算法的问题集合，NP指非确定型图灵机上具有多项式算法的问 题集合，这里N是Non-Deterministic的意思（图灵机的概念见理论计算机初步：算法和计算模 型）。 脱离图灵机的概念，就在普通的计算机上看，P问题是指能够在多项式时间求解的判定问题（判 定问题指只需要回答是和不是的问题），而NP问题则是指那些其肯定解能够在给定正确信息下 在多项式时间内验证的判定问题。比如，要判定一个数是合数，如果给我一个约数，我们就很 快判定它就是合数。所以判定一个数是合数的问题属于NP。 下面是一些NP问题的例子： 零子集和问题 给n个整数，判断是否可以从中找到若干个数，其和为0。 旅行商问题 有n个城市，一个推销员要从其中某一个城市出发，不重复地走遍所有的城市，再回到他出发的 城市。问这个推销员的最短路程(是否小于指定的K)。 从上面的定义知道，NP包含P。P vs NP问题指P是否完全等于NP，即确定型图灵机和非确定图灵 机的性能是否一样。 人们为何要提出NP问题？因为，大多数遇到的自然的难解问题，最后都发现它们是NP问题。如 果我们能证明NP跟P的关系，则解决了无数问题的算法复杂度问题。 NP里面有无数个不同的问题，我们是否要一个一个地判定它们是否属于P呢？P vs NP问题的美 妙和简洁之处便在于在NP中，有一个子类，NP完全(NP Complete，简记为NPC)问题，指的是那 些NP中最难的那些问题：所有其它的NP问题都可以归约到这些NP完全问题。也就是说，只要这 些NP完全问题的某一个得到解决，无论是证明其存在多项式算法，还是不存在，都意味着P vs NP 问题的解决。 而几乎所有NP里面无法确定是否属于P的问题最后都被证明为NP完全。正因为如此，多数理论计 算机学家都猜测P≠NP。目前已知的NP完全问题数以千计，上面引用中的例子都是完全问题，更 多NP完全问题见NP完全问题的不完全列表。 一个很自然的想法是如果NP≠P，则NP-P里面的问题都是完全问题。至少有两个自然的问题，一 个是大数分解（给出一个数的质因数分解式），另一个是图同构问题（给出两个图，它们是否 同构），它们既没有被证明是P的，也没有被证明是NP-完全。但是更惊人的是还有这个定理： 如果NP≠P，那么NP-P中存在非NP完全问题。 当然，这种问题具体是什么样子，是无法用直观的语言表示出来，它纯粹是一个数学上的构造 性证明。 参阅： Complexity classes P and NP - Wikipedia, the free encyclopedia, P/NP问题- Wikipedia Turing machine - Wikipedia, the free encyclopedia, 图灵机- Wikipedia NP-hard - Wikipedia, the free encyclopedia, 理论计算机初步：P vs NP - 历史，现状和未来 ©Zhang-Zi, August 24, 2006 上篇文章已经提到，P vs NP是理论计算机科学的核心问题。从数学的角度来说，它和其他历史 上有名的数学问题一样，给与人们一个智力上重大的挑战。而更为重要的是，在无数与计算有 关的的学术领域中，NP-完全问题以各种不同形式层出不穷。因此，这并不是一个纯粹的与世独 立的智力游戏，而是对计算机科学有全面影响力的问题。 历史上的进展 从上个世界70年代初这个问题被Cook提出以来，人们发展了各种工具来试图解决它，下面引自 堵丁柱&葛可一的《计算复杂性导论》前言： 人们在七十年代开始对NP-完全问题的研究主要是横向发展，也就是以许多不同的计算模型来分 析难解问题的本质。这些新的计算模型包括了平行计算模型、概率计算模型、布尔线路、判断 树、平均复杂性、交互证明系统以及程式长度复杂性等等。对这些新的计算模型的研究一方面 使我们对难解问题有了更深一层的认识，一方面也产生了一些预想不到的应用。最显著的一个 例子就是计算密码学的革命性突破：基于NP问题的公钥密码体系。另一个有名的例子是线性规 划的多项式时间解的发现。 到了八十年代中，对NP-完全问题的研究有了纵向的突破，在许多表面看来并不相关的计算模型 之间发现了深刻的刻划关系。这些刻划关系不但解决了几个令人困扰多年的未解问题，同时也 刺激了其它相关领域的发展。其中之一是对线路复杂性的研究发现了一些问题在某种有限制的 线路模型中必有指数下界。这些结果使用了组合数学与概率等新的数学工具，并且解决了 一个有名的有关多项式分层的未解问题。另一个更重大的结果是以概率可验证明对NP类的刻划。 由此得出了许多组合优化问题近似解的NP-完全性，从而刺激了算法界对近似算法研究的新热 潮。这个结果来自于对交互证明系统这个概念的扩展，并且使用了线性代数与编码理论等数学 证明技巧。 但是，明显的，目前还没有一个看上去有希望的方向。相反的，1993年Razborov和Rudich证明 的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P vs NP问 题。这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定 理的可能证明有越来越多的陷阱要规避。 数学里最伟大的定理之一——费马大定理，用了数学家300多年时光。P vs NP问题，作为理论 计算机领域最困难的问题，40年时间似乎太短了。 不过我还是相信，这个问题被拖这么长时间，是因为没有足够伟大的数学家来做这个问题。 大牛们怎么看？ 对于NP是否等于P，大家看法不一。在2002年对于100个研究者的调查中，61人相信答案是否定 的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所 以不可能证明或证否。同时，在被询问到这个问题可能在何时被解决时，79个人给出了确切的 数字，统计结果如下： 1. P=NP will be resolved between 2002-2009: 5 2. P=NP will be resolved between 2010-2019: 12 3. P=NP will be resolved between 2020-2029: 13 4. P=NP will be resolved between 2030-2039: 10 5. P=NP will be resolved between 2040-2049: 5 6. P=NP will be resolved between 2050-2059: 12 7. P=NP will be resolved between 2060-2069: 4 8. P=NP will be resolved between 2070-2079: 0 9. P=NP will be resolved between 2080-2089: 1 10. P=NP will be resolved between 2090-2099: 0 11. P=NP will be resolved between 2100-2110: 7 12. P=NP will be resolved between 2100-2199: 0 13. P=NP will be resolved between 2200-3000: 5 14. P=NP will never be resolved : 5. 在这份调查中，还有国际上著名的计算机学家对这个问题的看法，比如： Avi Wigderson: (Institute of Advanced Study) I think this project is a bit premature. I think we know too little of what is relevant to even guess answers to your questions, certainly if "we" s replaced by "I" The only thing I can definitely say, is that it is one of the most important and interesting questions ever asked by humans, and more people and resources should participate in filling up the holes that would allow better guesses of answers to your questions. 姚期智: (Princeton) It's hard to say when the question will be resolved. I don't have even an educated guess. Probably the resolution is that P is not equal to NP. I think the mathematical techniques used will be beautiful. 可能的极为诡异的结果 从实际应用来说，人们都希望NP=P，因为这意味着很多问题都能有有效的算法，但有些极为诡 异的结果也是可能的，人们从这个结果中什么都得不到。 比如某一天人们最终使用某种数学上的技巧证明了NP问题的多项式时间算法的存在性，但并不 知道如何找到它——这在数学上是极为可能的，那最终会怎么样呢？ 这种情况不会发生，事实上，在NP=P的假设下，人们已经找到了NP完全问题的多项法解法，但 这并没有好太多，因为这个算法是这样的： // 接受NP完全语言的一个算法。 // // 这是一个多项式时间算法当且仅当P=NP。 // // “多项式时间”表示它在多项式时间内返回“是”，若 // 结果是“是”，否则永远运行。 // // 输入：S = 一个自然数的有限集 // 输出：是 如果某个S的子集加起来等于0。 // 否则，它永远运行没有输出。 // 注：上面这是一个NP完全问题 // // 程序数P 是你将一个整数P写为二进制，然后 // 将位串考虑为一个程序。 // 每个可能的程序都可以这样产生， // 虽然多数什么也不做因为有语法错误。 FOR N = 1…infinity FOR P = 1…N 以S为输入运行程序数P N步 IF 程序输出一个完整的数学证明 AND 证明的每一步合法 AND 结论是S确实有（或者没有）一个和为0的子集 THEN OUTPUT 是（或者不是）并停机 如果NP=P，上面这个算法便是一个NP完全问题的多项式时间算法。可是它一点价值都没有，更 不用说来解决实际问题了。 另一种可能性：独立问题？ 自从Godel的开创性结果以来，我们知道某些问题，比如连续统假设，是不可能从目前的条件（公 理系统）推导出来的。有人怀疑P vs NP问题也是这样。这样的话，如果不存在NP完全问题的有 效算法，我们不可能证明这一点。同样，如果存在一个有效的算法，我们也不可能找到它。 花絮 中国民科一向喜欢做大问题，不知为何很少向P vs NP问题下手，但他们的外国同行可不会客气， 这里就有一大帮，而且这些国外的前辈们专业多了，好多解答还提供pdf文档下载呢。 参考文献： P verse NP problem The history and status of P verse NP question 千禧年大奖难题（一） 堵丁柱, 葛可一, 计算复杂性导论 , 高等教育出版社, 2002