[资料共享]P=NP?七大千禧年大奖难题之一！

P/https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=10581694&是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”（Clay https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=101395455& Institute, 简称CMI）在https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=57418480&中收录。 P/NP问题中包含了复杂度类P与NP的关系。1971年https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=168104843&(Stephen A. Cook) 和 Leonid Levin 相对独立的提出了下面的问题，即是否两个复杂度类P和NP是恒等的（P=NP?）。

1    P/NP问题

P和NP

复杂度类P包含所有那些可以由一个https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=142957674&在https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=445974&表达的时间内解决的问题；类NP由所有其肯定解可以在给定正确信息的https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=70101569&内验证的决定问题组成，或者等效的说，那些解可以在非https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=72967821&上在多项式时间内找出的问题的集合。很可能，计算理论最大的未解决问题就是关于这两类的关系的:P和NP相等吗?在2002年对于100研究者的调查，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能所接受的公理独立，所以不可能证明或证否。[1] 所以https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=174959995&也是Clay研究所的七个百万美元大奖问题之一。https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=73641139&问题(或者叫NPC)的集合在这个讨论中有重大作用，它们可以大致的被描述为那些在NP中最不像在P中的。(确切定义细节请参看NP-完全)理论计算机科学家现在相信P, NP,和NPC类之间的关系如图中所示，其中P和NPC类不交。假设P ≠ NP的复杂度类的图解.如P = NP则三个类相同.本质上，P = NP问题问道：如果是/不是问题的正面答案可以很快验证，其答案是否也可以很快计算？这里有一个给你找点这个问题的感觉的例子。给定一个大数Y,我们可以问Y是否是复合数。例如，我们可能问53308290611是否有非平凡的因子。回答是肯定的，虽然手工找出一个因子很麻烦。从另一个方面讲，如果有人声称答案是"对，因为224737可以整除53308290611",则我们可以很快用一个除法来验证。验证一个数是除数比首先找出除数来简单得多。用于验证一个正面答案所需的信息也称为证书。所以我们的结论是，给定 正确的证书，问题的正面答案可以很快的(也就是，在多项式时间内)验证，而这就是这个问题属于NP的原因。虽然这个特定的问题，证明为也在P类中(参看下面的关于"质数在P中"的参考),这一点也不明显，而且有很多类似的问题相信不属于类P。限制到是/不是问题并没有改变问题；即使我们允许更复杂的答案，https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=138701055&(是否FP = FNP)是等价的。

NP完全

要解决P = NP问题，https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=73641139&的概念非常有用。不严格的讲，NP完全问题是NP类中“最难”的问题，也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。例如，https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=101310558&的判定问题版本是NP完全的。所以NP中的任何问题的任何特例可以在多项式时间内机械地转换成旅行商问题的一个特例。所以若旅行商问题被证明为在P内，则P = NP！旅行商问题是很多这样的NP完全的问题之一。若任何一个NP完全的问题在P内，则可以推出P = NP。不幸的是，很多重要的问题被证明为NP完全，但没有一个有已知快速的算法。

P容易处理吗

上面所有的讨论假设了P表示“容易”而“不在P中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设，它在实践中却不总是真的，原因包括如下几点：它忽略了常数因子。一个需要101000n时间的问题是属于P的（它是线性时间的），但是事实上完全无法处理。一个需要10-100002n时间的问题不是在P中的（它是https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=73829492&的），但是对于n 取值直到几千时还是很容易处理的。它忽略了指数的大小。一个https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=105680&n1000属于P，但是很难对付。已经证明在P中存在需要任意大的指数的问题（参看时间等级定理）。一个时间复杂度2n/1000的问题不属于P，但对与n直到几千还是容易应对的。它只考虑了最坏情况的复杂度。可能现实世界中的有些问题在多数时候可以在时间n中解决，但是很偶尔你会看到需要时间2n的特例。这个问题可能有一个多项式的平均时间，但最坏情况是指数式的，所以该问题不属于P。它只考虑确定性解。可能有一个问题你可以很快解决https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=142728934&接受出现一点误差的可能，但是确保https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=158477110&会难得多。这个问题不会属于P，虽然事实上它可以很快求解。这实际上是解决属于NP而还不知道是否属于P的问题的一个办法（参看RP， BPP）。新的诸如https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=323052&这样的计算模型，可能可以快速的解决一些尚未知道是否属于P的问题；但是，没有一个它们已知能够解决的问题是NP完全的。不过，必须注意到P和NP问题的定义是采用象https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=623258&这样的经典计算模型的属于表述的。所以，即使一个https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=323052&算法被发现能够有效的解决一个NP完全问题，我们只是有了一个快速解决困难问题的实际方法，而不是数学类P和NP相等的证明。

科学家的理论

多数计算机科学家相信P≠NP。该信念的一个关键原因是经过数十年对这些问题的研究，没有人能够发现一个NP完全问题的https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=70101569&算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法了（Karp的21个NP完全问题，在最早发现的一批中，有所有著名的已经存在的问题]]）。进一步地，P = NP这样的结果会导出很多惊人的结果，那些结果现在被相信是不成立的，例如NP = 余NP和P = PH。也有这样论证的：问题较难求解(NP)但容易验证(P)，这和我们日常经验是相符的。从另一方面讲，某些研究者认为我们过于相信P ≠ NP，而应该也去寻找P = NP的证明。例如，2002年中有这样的声明：倾向P≠NP的主要论据是在穷尽搜索的领域完全没有本质进展。也就是说，以我的观点，一个很弱的论据。算法的空间是很大的，而我们只是在开始探索的起点。[ . . . ]费马最後定理的解决也显示非常简单的[sic]问题可能只有用非常深刻的理论才能解决。— Moshe Vardi，https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=87243&过分依赖某种投机不是规划研究的一个好的导引。我们必须总是尝试每个问题的两个方向。偏见可能导致著名的数学家无法解决答案和他们的预计相反的著名问题，虽然他们发展了所有所需的方法。— Anil Nerode,https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=80727&

学术定义

更正式一些，一个决定问题是一个取一些字符串为输入并要求输出为https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=440790&的问题。若有一个算法（譬如图灵机，或一个LISP或Pascal的程序并有无限的内存）能够在最多n^k步内对一个串长度为n的输入给出正确答案，其中k是某个不依赖于输入串的常数，则我们称该问题可以在多项式时间内解决，并且将它置入类P。直观的讲，我们将P中的问题视为可以较快解决的问题。

假设有一个算法A(w,C)取两个参数，一个串w，也就是我们的决定问题的输入串，而另一个串C是“建议证明”，并且使得A在最多n^k步之内产生“是/否”答案（其中n是w的长度而k不依赖于w）。进一步假设

w是一个答案为“是”的例子，当且仅当，存在C使得A(w,C)返回“是”。

则我们称这个问题可以在非决定性多项式时间内解决，且将它放入NP类。我们把算法A作为一个所建议的证明的检验器，它运行足够快。（注意缩写NP代表“Non-deterministic（https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=71688453&）Polynomial（https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=445974&）”而不是代表“Non-Polynomial（非多项式）。

证明的难度

虽然百万美元的奖金和大量投入巨大却没有实质性结果的研究足以显示该问题是困难的，还有一些https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=73282694&的结果证明为什么该问题可能很难解决。

最常被引用的结果之一设计https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=58436825&。假想你有一个魔法机器可以解决单个问题，例如决定一个给定的数字是否为质数，但可以瞬间解决这个问题。我们的新问题是，若我们被允许任意利用这个机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，P = NP和P ≠ NP二者都可以证明。这个结论的后果是，任何可以修改来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在相对化）。

如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P = https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=10581694&。[3] 这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定理的可能证明有越来越多的陷阱要规避。

这实际上也是为什么NP完全问题有用的原因：若有一个多项式时间算法，或者没有一个这样的算法，对于NP完全问题存在，这将用一种相信不被上述结果排除在外的方法来解决P = NP问题。

多项时间算法

没人知道https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=70101569&算法对于NP完全问题是否存在。但是如果这样的算法存在，我们已经知道其中的一些了！例如，下面的算法正确的接受了一个https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=73641139&语言，但是没人知道通常它需要多久运行。它是一个多项式时间算法当且仅当P = NP。

// 接受NP完全语言的一个算法子集和。

//

// 这是一个多项式时间算法当且仅当P=NP。

//

// “多项式时间”表示它在多项式时间内返回“是”，若

// 结果是“是”，否则永远运行。

//

// 输入：S = 一个https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=213727&的https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=351849&

// 输出："是" 如果某个S的子集加起来等于0。

// 否则，它永远运行没有输出。

// 注意: "程序数P" 是你将一个整数P写为二进制，然后

// 将位串考虑为一个程序。

// 每个可能的程序都可以这样产生，

// 虽然多数什么也不做因为有语法错误。

//

FOR N = 1...infinity

FOR P = 1...N

以S为输入运行程序数P N步

IF 程序输出一个不同的整数的列表

AND 所有整数都在S中

AND 整数的和为0

THEN

OUTPUT "是" 并 停机

若P = NP，则这是一个接受一个NP完全语言的多项式时间算法。“接受”表示它在多项式时间内给出“是”的答案，但允许在答案是“否”的时候永远运行。

可能我们想要“解决”子集和问题，而不是仅仅“接受”子集和语言。这表示我们想要它总是停机并返回一个“是”或“否”的答案。是否存在任何可能在多项式时间内解决这个问题的算法？https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=70790017&。但是如果这样的算法存在，那么我们已经知道其中的一些了！只要将上面的算法中的IF语句替换成下面的语句：

IF 程序输出一个完整的https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=99806822&

AND 证明的每一步合法

AND 结论是S确实有（或者没有）一个和为0的子集

THEN

OUTPUT "是" （或者"不是"如果那被证明了）并停机

逻辑表述

P=https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=10581694&可以用逻辑命题的特定类的可表达性的术语来重新表述。所有P中的语言可以用https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=712143&加上最小https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=76056&操作（实际上，这允许了https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=8016634&的定义）来表达。类似地，NP是可以用存在性https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=207343&来表达—也就是，在关系、函数、和子集上排除了全域量词的二阶逻辑。https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=445974&等级，PH中的语言对应与所有的二阶逻辑。这样，“P是NP的https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=268082&吗”这样的问题可以表述为“是否存在性二阶逻辑能够表达带最小不动点操作的一阶逻辑的所不能表达的语言？”[/p][p]

花絮

https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=80713&计算机系楼将https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=15555451&表述的“P=NP?”问题刻进顶楼西面的砖头上。如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”。[4]https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=80727&的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：“https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=179968&。设P = NP。令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=70101569&内验证，我们认定这样的科学家的存在性为真。但是，因为P = NP，该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到矛盾。

2最新消息

https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=66258320&年：8 月 6 日，HP LAB的 Vinay Deolalikar 教授宣布证明了P!=NP，证明文章已经发送到该问题各相关领域专家手中，等待检验，在他的主页上，证明过程已经公布（https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=7621879&共103页）。8 月 8 日，Lipton 在博客上讨论了这篇论文，给出了略显乐观的评价：这是一个值得认真对待的证明。这篇文章引来大量严肃的学术性回复，大多来自业内人士，各方看法不一。8 月 9 日，Lipton 在参考各方反应的基础上同 Ken Regan 合写了一篇新的博客文章，指出了 Deolalikar 证明思路中的一些重大漏洞，对它的整体评价口吻较前日明显低调了许多。同日，因为 Lipton 博客文章后面大量有价值的评论值得梳理，Venkatasubramanian 建立了一个可以被公众编辑的 Google Docs 文档以整理这些讨论。翌日，在https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=147157&的帮助下，该文档被转换成一个 wiki 架构的页面。8 月 10 日，Lipton 写了新的博客文章，试图将各方讨论的结果以更清晰的方式呈现出来。这篇文章继续成为各方讨论的平台，更多学术上的批评开始浮出水面。更多科学家参与了博客评论以及 wiki 页面的编辑。同日，Deolalikar 在自己的网站上撤下了https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=8189084&的链接，稍后放上了新一稿。8 月 11 日，Lipton贴出了 Deolalikar 对一部分学术质疑的答复。Vinay Deolalikar 贴出了论文的第三稿。同一日，在学术讨论之外，各方对事态发展的速度和形式本身开始进行反思。Lipton 和陶哲轩等人认为一个借助https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=103817121&被良好组织起来的讨论可以产生很好的效果，无论对于 Deolalikar 改进他的证明还是对于推进人们关于 P/NP 问题本身的了解都有益处。而另一些科学家，以 Impagliazzo 为代表，认为网络讨论导致了人们反应过度，浪费了太多本可以从事其它研究的时间。这一论点引起了大量争论。8 月 12 日，Lipton贴出了一封来自 Neil Immerman 的信，指出了两个此前未被认真讨论的漏洞。8 月 13 日，Deolalikar 贴出了一篇关于自己的证明的解释性文档。8 月 14 日，在很多科学家的共同讨论中，人们逐渐厘清 Deolalikar 的论文的根本问题在于把两个没有在论文中被严格定义出来的直观概念混淆在一起，从而做出了不完善的论证。8 月 15 日，Lipton 贴出了他对于一周以来讨论的总结。人们关于论文的看法——即证明不能成立——已经趋于稳定（当然这不能排除大家都同时犯了错误的可能性），随后的发言越来越多地集中于更抽象的层面，并且至今仍在继续。

   证明P=NP对世界的影响

如果“NP=P”，这个结果对我们这个世界的影响是很大的。这意味着任何一个原来找不到“P类算法”的NP类问题都可以找到相应的“P类算法”了。比如刚才说的大整数的质因数分解问题，就成为了P类问题。这意味着刚才例子中2048位的二进制大整数可以用一台普通电脑在几秒钟甚至更短的时间完成其质因数分解，那么被广泛应用的RSA加密算法就彻底失效了。我们大量的银行数字证书、网站SSL加密都不再安全，人类必须要寻找新的、更强的加密算法。

同时，这也意味着很多原来通过计算很难解决的大量问题都可以通过算法优化而轻松得到解决了。如果NP=P，那么我们就可以更好地预测天气，更容易通过氨基酸序列来预测蛋白质结构，更好的确定计算机芯片上最有效的晶体管布局，更优的完成物流交通调度，......。

如果“NP不等于 P”，对我们这个世界的影响很小，或者说对实际生活几乎没有什么影响。可是，迄今为止还没有谁能给出这个证明。

这个问题的难度远远超过一般人的想象。目前，绝大多数的相关领域科学家（包括数学家、计算理论科学家、IT行业资深算法研究人员等）都认为“NP不等于 P”，所以，我们可以暂时先松口气，不用太担心“NP=P”给我们日常生活带来的影响。

实在看不懂的看这里~

“NP=P”到底是个什么问题？

要知道“NP=P”是个什么问题，先要知道什么是“P类问题”，什么是“NP类问题”，而这两个概念又和计算理论中的时间复杂度有关。不过不用担心，这几个概念都不是很复杂。

简单的说，解决一个问题的某种算法所需要的计算量（或计算步骤）随着这个问题的规模增长而增长的速度就被称为这个算法的时间复杂度。要注意的是，时间复杂度本质上指的是计算量增长的速度而不是这个算法运行的时间。例如：

（1）我们要计算前n个自然数的和，如果使用最直接而笨拙的方法，需要计算n-1次加法，那么可以认为这个算法的时间复杂度就是“n-1”，记作O(n-1)或者O(n)。之所以可以记作O(n)，是因为随着n的增大，1这个常数就忽略不计了。

（2）如果我们要把n个不同的自然数排序，那么就需要对这些自然数的大小进行比较。我们也采用最笨拙的算法，也就是将每两个自然数都做一次比较，那么需要比较n(n-1)/2次，时间复杂度可以记为 ，或者记为 。

（3）下面举一个更复杂些的例子。给出一个含有n个逻辑变量的逻辑表达式，请判断这个表达式是否是一个“重言”的逻辑表达式。“重言”的意思是说这个表达式无论所包含的n个逻辑变量怎么取值，其结果都是真，类似于我们语言中的“废话”（如“明天要么下雨要么不下雨”）。最简单的重言表达式如 ，其结果永远为真。我们如果也采用最笨拙的算法，穷举出n个逻辑变量的全部可能的组合，计算每种组合下逻辑表达式的值，如果都是真，就说明这个逻辑表达式是重言的。n个逻辑变量全部可能的组合有 种，每种组合要进行大约P(n)次逻辑运算（P(n)是n的某个多项式），因此其时间复杂度为 。

还有一些问题，无论其是否能够在多项式时间复杂度内求解，至少我们知道如果随便给出一个可能的解，我们可以在多项式时间复杂度内验证其是否为所求的解。这类问题我们称之为“NP类问题”。比如前面的例子（3），我们随便猜测一组逻辑变量的组合，就可以通过P(n)次逻辑运算判定其结果是否为假，如果是，那么我们就确定这个逻辑表达式不是重言表达式。因此，（3）中的问题虽然我们还没有找到一个多项式时间复杂度的算法，不知道它是否属于“P类问题”，但是我们很确定它一定属于“NP类问题”。

之所以要研究一个问题是否有多项式时间复杂度的算法，是因为多项式时间复杂度的计算量增长速度相对来说算是“慢”的，随着n的增大，其计算量远远小于 、 、 等时间复杂度问题。比如很有名的大整数质因数分解问题，给出一个2048位的二进制整数，要找到它的某个质因数，一般情况下穷尽全世界的计算能力也不能在100年内完成这个求解计算过程；但是如果我给出一个质数，却可以用普通的计算机在几秒钟时间以内确定这个质数是否是这个2048位二进制整数的一个因数。这就是不同时间复杂度在实际计算过程中的差别！

cjy20050924：噗、、、这是啥啊回到原帖

cjy20050924：噗、、、这是啥啊回到原帖

qigemingzizeina：O(∩_∩)O哈哈~回到原帖

qyd061030：能看懂多少？回到原帖

qigemingzizeina：完全懒得看了回到原帖

qyd061030：我也看不懂【世界数学家都没能解出的难题】回到原帖

cjy20050924：我的芊芊宝贝好久不见~回到原帖