P-NP-NPC三者问题阐述.doc

P NP NPC三者问题阐述1）P对NP问题是什么意思?首先说明一下问题的复杂性和算法的复杂性的区别，下面只考虑时间复杂性。算法的复杂性是指解决问题的一个具体的算法的执行时间，这是算法的性质；问题的复杂性是指这个问题本身的复杂程度，是问题的性质。比如对于排序问题，如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是O(nlgn)，但是排序算法有很多，冒泡法是O(n2)，快速排序平均情况下是O(nlgn)等等，排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。问题的复杂性不可能通过枚举各种可能算法来得到，一般都是预先估计一个值，然后从理论上证明。为了研究问题的复杂性，我们必须将问题抽象，为了简化问题，我们只考虑一类简单的问题，判定性问题，即提出一个问题，只需要回答yes或者no的问题。任何一般的最优化问题都可以转化为一系列判定性问题，比如求图中从A到B的最短路径，可以转化成：从A到B是否有长度为1的路径？从A到B是否有长度为2的路径？从A到B是否有长度为k的路径？如果问到了k的时候回答了yes，则停止发问，我们可以说从A到B的最短路径就是k。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。然而有些问题很难找到多项式时间的算法（或许根本不存在），比如找出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然，所有的P类问题都是属于NP问题的，但是现在的问题是，P是否等于NP?这个问题至今还未解决。注意，NP问题不一定都是难解的问题，比如简单的数组排序问题是P类问题，但是P属于NP，所以也是NP问题，你能说他很难解么？刚才说了，现在还不知道是否有P=NP或者PNP，但是后来人们发现还有一系列的特殊NP问题，这类问题的特殊性质使得很多人相信PNP，只不过现在还无法证明。这类特殊的NP问题就是NP完全问题（NPC问题，C代表complete）。NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立！这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如前面说的哈米尔顿回路问题就是一个NPC问题。NPC问题的历史并不久，cook在1971年找到了第一个NPC问题，此后人们又陆续发现很多NPC问题，现在可能已经有3000多个了。所以，我们一般认为NPC问题是难解的问题，因为他不太可能存在一个多项式时间的算法（如果存在则所有的NP问题都存在多项式时间算法，这太不可思议了，但是也不是不可能）。类似哈米尔顿回路/路径问题，旅行商问题，集团问题，最小边覆盖问题（注意和路径覆盖的区别），等等很多问题都是NPC问题，所以都是难解的问题。2）浅谈np问题NP完全问题在科学研究和实际应用中广泛存在，仅仅指出它们的难解性是不够的，更重要的是正面寻求解决方法，其中的关键是算法的设计与分析。 图灵机 宽泛地讲，图灵机可以说是一个复杂的代数结构，它又是一个通用的计算机模型，能做计算机可以做的所有事情。当然，图灵机也有不能解决的问题，但这些问题事实已经超出了计算机的能力范围了，我们现在基本上是这样认为的。 费马大定理 17世纪的一位法国数学家，提出了一个数学难题，使得后来的数学家一筹莫展，这个人就是费马。 这道题是这样的:当n2时，xn+yn=zn没有正整数解，在数学上被称为“费马大定理”。为了获得它的一个肯定的或者否定的证明，历史上几次悬赏征求答案，一代又一代最优秀的数学家都曾研究过，但是300多年过去了，至今既未获得最终证明，也未被推翻。即使用现代的电子计算机也只能证明:当n小于等于4100万时，费马大定理是正确的。由于当时费马声称他已解决了这个问题，但是他没有公布结果，于是留下数学难题中少有的千古之谜。 有数学家说过“一个好的问题胜过十个好解答”。因为解答一出，此问题已是到了终点，对不断求创新的人们而言，已不构成挑战。而新的问题是源头活水，能开拓新的境界。多数人都不愿沉醉在好的解答中不断地玩味，而希望找到新的问题，不断地思考、摸索。 了解NP问题 “P=NP？”这个问题，作为理论计算机科学的核心问题，其声名早已经超越了这个领域。它是Clay研究所的七个百万美元大奖问题之一，在2006国际数学家大会上，它是某个1小时讲座的主题。 要说起P和NP是什么东西，得先从算法的多项式时间复杂度谈起，注意，这里面的两个P都是指Polynomial（多项式）。 一个问题的规模指的是输入的总位数，比如一个n个数的排序问题，输入规模就是n。在某些时候，输入规模是值得注意的，比如判定一个数n是否是一个质数这个问题，它的输入规模并不是n，而是log(n)，因为一个数n用大约log(n)位就能表示出来了，这也是为何枚举因子判定素数的算法并不是多项式时间算法的原因。 如果一个算法，能在以输入规模为参变量的某个多项式的时间内给出答案，则称它为多项式时间算法。注意:这里的多项式时间是指算法运行的步数。一个算法是否是多项式算法，与计算模型的具体的物理实现没有关系，虽然大多数假想的计算模型不可能有任何物理的实现。 P指确定型图灵机上的具有多项式算法的问题集合，NP指非确定型图灵机上具有多项式算法的问题集合，这里N是不确定的意思。 脱离图灵机的概念，就在普通的计算机上看，P问题是指能够在多项式时间求解的判定问题（判定问题指只需要回答是和不是的问题），而NP问题则是指那些其肯定解能够在给定正确信息下在多项式时间内验证的判定问题。比如，要判定一个数是合数，如果给我一个约数，我们就很快判定它就是合数。所以判定一个数是合数的问题属于NP。 NP问题的代表问题之一是售货员旅行问题(traveling salesman problem)。有一个售货员要 汽车到n个指定的城市去推销货物，他必须经过全部的n个城市。现在他有此n城的地图及各城之间的公路距离，试问他应如何取最短的行程从家中出发再回到家中。 NP问题的历史 人们在七十年代开始对NP完全问题的研究主要是横向发展，也就是以许多不同的计算模型来分析难解问题的本质。这些新的计算模型包括了平行计算模型、概率计算模型、布尔线路、判断树、平均复杂性、交互证明系统以及程式长度复杂性等等。对这些新的计算模型的研究一方面使我们对难解问题有了更深一层的认识，一方面也产生了一些预想不到的应用。最显著的一个例子就是计算密码学的革命性突破：基于NP问题的公钥密码体系。另一个有名的例子是线性规划的多项式时间解的发现。 到了八十年代中，对NP完全问题的研究有了纵向的突破，在许多表面看来并不相关的计算模型之间发现了深刻的刻划关系。这些刻划关系不但解决了几个令人困扰多年的未解问题，同时也刺激了其它相关领域的发展。其中之一是对线路复杂性的研究发现了一些问题在某种有限制的线路模型中必有指数下界。这些结果使用了组合数学与概率方法等新的数学工具，并且解决了一个有名的有关多项式分层的未解问题。另一个更重大的结果是以概率可验证明对NP类的刻划。这个结果来自于对交互证明系统这个概念的扩展，并且使用了线性代数与编码理论等数学证明技巧。 但是，明显的，目前还没有一个看上去有希望的方向。 数学里最伟大的定理之一费马大定理，用了数学家纷纷发表了300多年时光。NP问题，作为理论计算机领域最困难的问题，40年时间似乎太短了。 大师的看法 对于NP是否等于P，大家看法不一。在2002年对于100个研究者的调查中，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。 在这份调查报告中，国际上著名的计算机学家对这个问题的看法。 Avi Wigderson:(美国普林斯顿高等研究院教授)我想这个项目还没有成熟，因为关于这个项目的相关知识我们了解的太少了。我唯一可以确定的事情就是，人类所有提出的问题中最重要和最有趣的问题之一，是越来越多的人和资源应该参与其中，才能得到更好的猜想结果。 姚期智:（清华大学教授）很难说何时能够解决这个问题。我的猜想还没有得到学术界的验证，结果很可能是P问题并不等于NP问题，我认为使用数学技术会非常完美的。 可能的结果 从实际应用来说，人们都希望NP=P，因为这意味着很多问题都能有有效的算法，但有些极为诡异的结果也是可能的，人们从这个结果中什么都得不到。 比如某一天人们最终使用某种数学上的技巧证明了NP问题的多项式时间算法的存在性，但并不知道如何找到它这在数学上是极为可能的，那最终会怎么样呢？ 这种情况不会发生，事实上，在NP=P的假设下，人们已经找到了NP完全问题的多项法解法，但这并没有好太多，如果NP=P，很多算法便是一个NP完全问题的多项式时间算法。可是它一点价值都没有，更不用说来解决实际问题了。 经典计算中存在着一大类NP 问题。这类问题在经典计算机上是不能计算的，但是量子计算可以把其中的一部分NP问题变成 P问题，即问题的复杂度随着比特位数的增长以多项式数量级上升。这类问题原则上是可以计算的。 一个具体的例子就是大因数分解，按经典计算复杂性理论，这个问题不存在有效算法。但是如果用量子计算机结合Shor量子算法，这个问题就变成了P问题。 现状 P和NP是理论计算机科学的核心问题。从数学的角度来说，它和其他历史上有名的数学问题一样，给与人们一个智力上重大的挑战。而更为重要的是，在无数与计算有关的的学术领域中，NP完全问题以各种不同形式层出不穷。因此，这并不是一个纯粹的与世独立的智力游戏，而是对计算机科学有全面影响力的问题。 计算机与社会科学、自然科学和思维科学等许多学科相互渗透和交叉，形成了许多新的边缘学科和新学科群，正在改变许多传统学科。分子与量子计算机的深入研究和技术难关的攻克，并最终投入运算，必将在政治、经济、军事、文化乃至人类生活的各个方面产生深刻的影响。 最近美国南加州大学Adleman博士应用基于DNA分子计算技术的生物实验方法有效地求解了“哈密顿路径问题”目前计算机无法解决的NP完备问题。生物分子计算机的研制是基于生物分子的信息处理技术，即生物材料的信息处理功能与生物分子的计算技术。 能以叠加方式存贮信息的量子计算可生成一些真正的随机数，这是传统计算机无能为力的。数学上已证明量子计算可大大加快因式分解的速度。这一证据也吸引人们将注意力集中在根据量子力学原理制造量子计算机上。 计算能力超越图灵机、突破现有的体系结构是计算业界的梦想，不断有报道在DNA计算模型上找到了某NP问题的多项式算法,这应该意味着基于DNA计算模型的P类和NP类的划分会和经典模型有所不同。但是我们仍然希望量子计算能够突破图灵模式，给计算机科学带来一个崭新的世界。 哈密顿路径问题 天文学家哈密顿(William Rowan Hamilton) 提出，在图中找出一条包含所有结点的闭路，并且，出来起点和重点重合外，这条闭路所含结点是互不相同的，可以在多项式时间类判断一个回路是否是哈密顿回路，但目前没有算法直接解出哈密顿回路。 量子计算 量子计算(quantum computation)是对于一