P-NP-NPC三者问题阐述

《P-NP-NPC三者问题阐述》由会员分享，可在线阅读，更多相关《P-NP-NPC三者问题阐述（4页珍藏版）》请在装配图网上搜索。

1、P NP NPC三者问题阐述1）”P对NP问题”是什么意思？首先说明一下问题的复杂性和算法的复杂性的区别，下面只考虑时间复杂性。算法的复 杂性是指解决问题的一个具体的算法的执行时间，这是算法的性质；问题的复杂性是指这个 问题本身的复杂程度，是问题的性质.比如对于排序问题，如果我们只能通过元素间的相互比 较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是O（nlgn）， 但是排序算法有很多，冒泡法是O（M2），快速排序平均情况下是O（nlgn）等等，排序问题的 复杂性是指在所有的解决该问题的算法中最好算法的复杂性。问题的复杂性不可能通过枚举 各种可能算法来得到，一般都是预先

2、估计一个值，然后从理论上证明。为了研究问题的复杂性，我们必须将问题抽象，为了简化问题，我们只考虑一类简单的 问题，判定性问题，即提出一个问题只需要回答yes或者no的问题。任何一般的最优化问 题都可以转化为一系列判定性问题，比如求图中从A到B的最短路径，可以转化成：从A 到B是否有长度为1的路径？从A到B是否有长度为2的路径?.从A到B是否有长度为 k的路径？如果问到了 k的时候回答了 yes，则停止发问，我们可以说从A到B的最短路径 就是k。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们 说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为

3、多 项式时间的问题的集合.然而有些问题很难找到多项式时间的算法（或许根本不存在），比如找 出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以 在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路， 我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）。 这种可以在多项式时间内验证一个解是否正确的问题称为NP问题.显然，所有的P类问题都 是属于NP问题的，但是现在的问题是,P是否等于NP?这个问题至今还未解决。注意，NP 问题不一定都是难解的问题，比如简单的数组排序问题是P类问题，但是P属于NP，所以 也是NP问

4、题,你能说他很难解么？刚才说了，现在还不知道是否有P=NP或者PNP，但 是后来人们发现还有一系列的特殊NP问题，这类问题的特殊性质使得很多人相信PNP， 只不过现在还无法证明。这类特殊的NP问题就是NP完全问题（NPC问题，C代表complete）。 NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有 的NP问题都可以在多项式时间内求解，即P=NP成立!！这是因为，每一个NPC问题可以在 多项式时间内转化成任何一个NP问题。比如前面说的哈米尔顿回路问题就是一个NPC问 题.NPC问题的历史并不久，cook在1971年找到了第一个NPC问题，此后人们又陆续发现

5、 很多NPC问题，现在可能已经有3000多个了。所以，我们一般认为NPC问题是难解的问 题，因为他不太可能存在一个多项式时间的算法（如果存在则所有mP问题都存在多项式 时间算法，这太不可思议了，但是也不是不可能）.类似哈米尔顿回路/路径问题，旅行商问题， 集团问题，最小边覆盖问题（注意和路径覆盖的区别），等等很多问题都是NPC问题，所以都是 难解的问题。2）浅谈np问题NP完全问题在科学研究和实际应用中广泛存在，仅仅指出它们的难解性是不够的，更重 要的是正面寻求解决方法，其中的关键是算法的设计与分析。图灵机宽泛地讲，图灵机可以说是一个复杂的代数结构，它又是一个通用的计算机模型，能做 计算机可以

6、做的所有事情.当然，图灵机也有不能解决的问题，但这些问题事实已经超出了计算机的能力范围了，我们现在基本上是这样认为的.费马大定理17世纪的一位法国数学家，提出了一个数学难题，使得后来的数学家一筹莫展，这个人 就是费马。这道题是这样的:当n2时，xn+yn=zn没有正整数解，在数学上被称为“费马大定理”。 为了获得它的一个肯定的或者否定的证明，历史上几次悬赏征求答案，一代又一代最优秀的 数学家都曾研究过，但是300多年过去了，至今既未获得最终证明，也未被推翻。即使用现 代的电子计算机也只能证明：当n小于等于4100万时，费马大定理是正确的.由于当时费马 声称他已解决了这个问题，但是他没有公布结果

7、，于是留下数学难题中少有的千古之谜。 有数学家说过“一个好的问题胜过十个好解答”。因为解答一出，此问题已是到了终点，对不 断求创新的人们而言，已不构成挑战。而新的问题是源头活水，能开拓新的境界。多数人都 不愿沉醉在好的解答中不断地玩味，而希望找到新的问题，不断地思考、摸索。了解NP问题“P=NP？ ”这个问题，作为理论计算机科学的核心问题，其声名早已经超越了这个领 域。它是Clay研究所的七个百万美元大奖问题之一，在2006国际数学家大会上，它是某个1 小时讲座的主题.要说起P和NP是什么东西，得先从算法的多项式时间复杂度谈起，注意，这里面的两 个P都是指Polynomial（多项式）。一个问

8、题的规模指的是输入的总位数，比如一个n个数的排序问题，输入规模就是n。 在某些时候,输入规模是值得注意的，比如判定一个数n是否是一个质数这个问题，它的输 入规模并不是n，而是log（n），因为一个数n用大约log（n）位就能表示出来了，这也是为何 枚举因子判定素数的算法并不是多项式时间算法的原因。如果一个算法，能在以输入规模为参变量的某个多项式的时间内给出答案，则称它为多 项式时间算法.注意：这里的多项式时间是指算法运行的步数。一个算法是否是多项式算法， 与计算模型的具体的物理实现没有关系，虽然大多数假想的计算模型不可能有任何物理的实 现。P指确定型图灵机上的具有多项式算法的问题集合，NP指非

9、确定型图灵机上具有多项 式算法的问题集合，这里N是不确定的意思.脱离图灵机的概念，就在普通的计算机上看，P问题是指能够在多项式时间求解的判定 问题（判定问题指只需要回答是和不是的问题），而NP问题则是指那些其肯定解能够在给定 正确信息下在多项式时间内验证的判定问题。比如，要判定一个数是合数，如果给我一个约 数，我们就很快判定它就是合数。所以判定一个数是合数的问题属于NP。NP问题的代表问题之一是售货员旅行问题（traveling salesman problem）。有一个售货员 要 汽车到n个指定的城市去推销货物，他必须经过全部的n个城市.现在他有此n城的地图 及各城之间的公路距离，试问他应如

10、何取最短的行程从家中出发再回到家中。NP问题的历史人们在七十年代开始对NP完全问题的研究主要是横向发展，也就是以许多不同的计算 模型来分析难解问题的本质。这些新的计算模型包括了平行计算模型、概率计算模型、布尔 线路、判断树、平均复杂性、交互证明系统以及程式长度复杂性等等。对这些新的计算模型 的研究一方面使我们对难解问题有了更深一层的认识，一方面也产生了一些预想不到的应 用。最显著的一个例子就是计算密码学的革命性突破：基于NP问题的公钥密码体系。另一 个有名的例子是线性规划的多项式时间解的发现。到了八十年代中，对NP完全问题的研究有了纵向的突破，在许多表面看来并不相关的 计算模型之间发现了深刻的

11、刻划关系.这些刻划关系不但解决了几个令人困扰多年的未解问 题，同时也刺激了其它相关领域的发展。其中之一是对线路复杂性的研究发现了一些问题在 某种有限制的线路模型中必有指数下界。这些结果使用了组合数学与概率方法等新的数学工 具，并且解决了一个有名的有关多项式分层的未解问题。另一个更重大的结果是以概率可验 证明对NP类的刻划。这个结果来自于对交互证明系统这个概念的扩展，并且使用了线性代 数与编码理论等数学证明技巧。但是，明显的，目前还没有一个看上去有希望的方向。数学里最伟大的定理之一一费马大定理，用了数学家纷纷发表了 300多年时光。NP问题， 作为理论计算机领域最困难的问题，40年时间似乎太短了

12、.大师的看法对于NP是否等于P，大家看法不一。在2002年对于100个研究者的调查中，61人相 信答案是否定的，9个相信答案是肯定的,22个不确定，而8个相信该问题可能和现在所接 受的公理独立，所以不可能证明或证否。在这份调查报告中，国际上著名的计算机学家对这个问题的看法。Avi Wigderson:（美国普林斯顿高等研究院教授）我想这个项目还没有成熟,因为关于这个 项目的相关知识我们了解的太少了 .我唯一可以确定的事情就是，人类所有提出的问题中最 重要和最有趣的问题之一，是越来越多的人和资源应该参与其中，才能得到更好的猜想结果 姚期智（清华大学教授）很难说何时能够解决这个问题。我的猜想还没有

13、得到学术界的验证， 结果很可能是P问题并不等于NP问题，我认为使用数学技术会非常完美的。可能的结果从实际应用来说，人们都希望NP=P因为这意味着很多问题都能有有效的算法，但有些极 为诡异的结果也是可能的，人们从这个结果中什么都得不到。比如某一天人们最终使用某种数学上的技巧证明了 NP问题的多项式时间算法的存在 性，但并不知道如何找到它这在数学上是极为可能的，那最终会怎么样呢？这种情况不会发生，事实上，在NP=P的假设下，人们已经找到了 NP完全问题的多项 法解法，但这并没有好太多，如果NP=P，很多算法便是一个NP完全问题的多项式时间算法。 可是它一点价值都没有，更不用说来解决实际问题了。经典

14、计算中存在着一大类NP问题.这类问题在经典计算机上是不能计算的，但是量子计 算可以把其中的一部分NP问题变成P问题，即问题的复杂度随着比特位数的增长以多项 式数量级上升。这类问题原则上是可以计算的。一个具体的例子就是大因数分解，按经典计算复杂性理论，这个问题不存在有效算法。 但是如果用量子计算机结合Shor量子算法，这个问题就变成了 P问题。现状P和NP是理论计算机科学的核心问题。从数学的角度来说，它和其他历史上有名的数学 问题一样，给与人们一个智力上重大的挑战。而更为重要的是，在无数与计算有关的的学术 领域中，NP完全问题以各种不同形式层出不穷。因此这并不是一个纯粹的与世独立的智力 游戏,而

15、是对计算机科学有全面影响力的问题.计算机与社会科学、自然科学和思维科学等许多学科相互渗透和交叉，形成了许多新的 边缘学科和新学科群，正在改变许多传统学科。分子与量子计算机的深入研究和技术难关的 攻克,并最终投入运算，必将在政治、经济、军事、文化乃至人类生活的各个方面产生深刻 的影响。最近美国南加州大学Adleman博士应用基于DNA分子计算技术的生物实验方法有效地 求解了“哈密顿路径问题”一一目前计算机无法解决的NP完备问题。生物分子计算机的研制 是基于生物分子的信息处理技术，即生物材料的信息处理功能与生物分子的计算技术。能以叠加方式存贮信息的量子计算可生成一些真正的随机数，这是传统计算机无能

16、为力 的。数学上已证明量子计算可大大加快因式分解的速度.这一证据也吸引人们将注意力集中 在根据量子力学原理制造量子计算机上。计算能力超越图灵机、突破现有的体系结构是计算业界的梦想，不断有报道在DNA计算 模型上找到了某NP问题的多项式算法，这应该意味着基于DNA计算模型的P类和NP类的 划分会和经典模型有所不同。但是我们仍然希望量子计算能够突破图灵模式，给计算机科学 带来一个崭新的世界.哈密顿路径问题天文学家哈密顿(William Rowan Hamilton)提出，在图中找出一条包含所有结点的闭 路，并且，出来起点和重点重合外，这条闭路所含结点是互不相同的，可以在多项式时间类判 断一个回路是

17、否是哈密顿回路，但目前没有算法直接解出哈密顿回路.量子计算量子计算(quantum computation)是对于一个或多个量子位元(qubit)或量子三元(qutrit) 以上进行操作，以达到具有量子特性的演算功能.算法的多项式时间复杂度算法的时间复杂度是指算法需要消耗的时间资源.而算法的多项式时间复杂度是指时间 开销能约束在n的k阶多项式数量范围内。Shor量子算法1994年Shor等人提出了一种大因数分解的量子多项式算法，引起了轰动Shor算法的 核心是：利用数论中的一些定理，将大数因子分解转化为求某个函数的周期；通过对储存器 中的纠缠态实施“量子傅立叶变换”，从而完成经典计算机无法完成的大数因子分解。