p与np问题漫谈.doc

P/NP问题漫谈P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”（Clay Mathematics Institute, 简称CMI）在千禧年大奖难题中收录。P对NP问题是Steve Cook于1971年首次提出。“P/NP问题”，这里的P指多项式时间（Polynomial），一个复杂问题如果能在多项式时间内解决，那么它便被称为P问题，这意味着计算机可以在有限时间内完成计算；NP指非确定性多项式时间（nondeterministic polynomial），一个复杂问题不能确定在多项式时间内解决，假如NP问题能找到算法使其在多项式时间内解决，也就是证得了P=NP。比NP问题更难的则是NPC和NP-hard，如围棋便是一个NP-hard问题。P/NP的代表问题是dsp问题(traveling salesman problem)。有一个售货员要开汽车到 n个指定的城市去推销货物，他必須经过全部的 n 个城。现在他有一个有此 n 城的地图及各城之间的公路距离，试问他应如何取最短的行程从家中出发再到家中？字母代表城市，数字代表两城间距离人们为何要提出NP问题？ 因为，大多数遇到的自然的难解问题，最后都发现它们是NP问题。如果我们能证明NP跟P的关系，则解决了无数问题的算法复杂度问题。NP里面有无数个不同的问题，我们是否要一个一个地判定它们是否属于P呢？P vs NP问题的美妙和简洁之处便在于在NP中，有一个子类，NP完全(NP Complete，简记为NPC)问题，指的是那些NP中最难的那些问题：所有其它的NP问题都可以归约到这些NP完全问题。也就是说，只要这些NP完全问题的某一个得到解决，无论是证明其存在多项式算法，还是不存在，都意味着P vs NP问题的解决。而几乎所有NP里面无法确定是否属于P的问题最后都被证明为NP完全。正因为如此，多数理论计算机学家都猜测PNP。目前已知的NP完全问题数以千计，上面引用中的例子都是完全问题，更多NP完全问题见NP完全问题的不完全列表。 一个很自然的想法是如果NPP，则NP-P里面的问题都是完全问题。至少有两个自然的问题，一个是大数分解（给出一个数的质因数分解式），另一个是图同构问题（给出两个图，它们是否同构），它们既没有被证明是P的，也没有被证明是NP-完全。但是更惊人的是还有这个定理：如果NPP，那么NP-P中存在非NP完全问题。当然，这种问题具体是什么样子，是无法用直观的语言表示出来，它纯粹是一个数学上的构造性证明。P与NP的定义: P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出; NP是一个判定问题类,这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解; P事实上很直观,我们通常在编程中求解的问题大多都是P类问题.比如说排序,找最短路径等.NP这 个类事实上也很有趣,它并不要求给出一个算法来求解问题本身,而只是要求给出一个确定性算法在多项式时间内验证它的解.P与PN是否相等？ 对于P与NP是否相等，在2002年对于100研究者的调查，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。NPC问题的集合在这个讨论中有重大作用，它们可以大致的被描述为那些在NP中最不像在P中的。简单来说，P=NP问题问道：如果是不是问题的正面答案可以很快验证，其答案是否也可以很快计算？这里有一个给你找点这个问题的感觉的例子。给定一个大数Y，我们可以问Y是否是复合数。例如，我们可能问53308290611是否有非平凡的因子。回答是肯定的，虽然手工找出一个因子很麻烦。从另一个方面讲，如果有人声称答案是对，因为224737可以整除53308290611，则我们可以很快用一个除法来验证。验证一个数是除数比首先找出除数来简单得多。用于验证一个正面答案所需的信息也称为证明。所以我们的结论是，给定 正确的证明，问题的正面答案可以很快地（也就是，在多项式时间内）验证，而这就是这个问题属于NP的原因。虽然这个特定的问题，最近被证明为也在P类中，这一点也不明显，而且有很多类似的问题相信不属于类P。像上面这样，把问题限制到“是不是”问题并没有改变原问题（即没有降低难度）；即使我们允许更复杂的答案，最后的问题（是否FP=FNP）是等价的。多数计算机科学家相信PNP。该信念的一个关键原因是经过数十年对这些问题的研究，没有人能够发现一个NP完全问题的多项式时间算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法了（Karp的21个NP完全问题，在最早发现的一批中，有所有著名的已经存在的问题）。进一步地，P = NP这样的结果会导致很多惊人的结果，那些结果现在被相信是不成立的，例如NP = 反NP和P = PH。也有这样论证的：问题较难求解（NP）但容易验证（P），这和我们日常经验是相符的。花絮普林斯顿大学计算机系楼将二进制代码表述的“P=NP?”问题刻进顶楼西面的砖头上。如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”。 康奈尔大学的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：“反证法。设P = NP。令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证，我们认定这样的科学家的存在性为真。但是，因为P = NP，该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明