首页 > 杏彩资讯 > 杏彩,最新证明面对证疑:PNP问题为什么这么难?

杏彩,最新证明面对证疑:PNP问题为什么这么难?

  近年来,不乏有人声称证了然P等于或者不等于NP,但都被发觉证明过程有误。现实上,到目前为止,还没有人可以大概回覆这个问题。2002年,有70位数学家和计较机科学家被邀请参取一次投票,投P能否等于NP。此中的61位认为P不等于NP,而剩下的人里有好几个都暗示投“等于”只是为了采纳相反的立场。

  现实上,量子计较机、图同构问题等人们热衷的最新进展无不指向P对NP问题。那么,P取NP问题事实是什么?它的处理将意味着什么?它难正在哪里?量子力学为它带来了什么?又有什么理论、将正在何时有可能处理它?本文试图对这些问题供给简单的引见和切磋。

  图灵期间的计较机科学关心的次如果问题的可计较性(computability),也即一个问题能否能够被计较机描述并处理。之后,跟着可计较性问题的澄清,计较机科学家逐步将留意力转移到了另一个问题,即问题的复杂性(complexity):施行一个给定的算法需要多长时间?不外,计较机科学家的谜底不是几分钟或者几毫秒,而是所需时间取问题规模的函数关系。

  麻省理工学院旧事(MIT News)曾颁发过一篇注释P/NP的文章。这篇文章指出,想象有一张未经排序的数字列表,然后写一个寻找最大值的算法。起首明显,该算法必必要查询列表中的所无数字。可是,若是它只是正在每一步查询一个数字,然后只更新并记实当下的最大数,那么对于每个数字,它只需要查询一次。于是,该算法的施行时间取它处置的问题规模,即计较机科学家们所指的N,间接成反比。当然,大大都算法是更为复杂的,因而比寻找最大值算法的效率要低。可是有很多常见算法的施行时间取N^2,或者N log(N)成反比。

  一个只包含常数、N、N^2以及N的其他次方的数学表达式称为一个多项式(polynomial),这就是“P = NP”中的“P”所代表的单词。一般来说,P代表求解时间取N的多项式成反比的问题的调集。雷同地,PSPACE代表所用空间取N的多项式成反比的问题的调集。

  明显,一个施行时间取N^3成反比的算法的要比取N成反比的算法慢(对于脚够大的N),但这种差别取多项式和指数的差别比起来要细微得多。麻省理工学院旧事的这篇文章指出,若是一个施行时间取N成反比的算法用1秒能够处理包含100个输入元素的问题,那么取N^3成反比的算法大要需要3个小时。可是,一个施行时间取2^N成反比的算法需要300艾(1艾等于10的18次方)年的时间来处理同样的问题。杏彩平台所以2^N取N的多项式的差别要比N^3和N之间的差别多的多。

  NP(Nondeterministic Polynomial time,非确定型多项式时间)指的是其解能够正在多项式时间内被验证的问题调集。容易想象的是,很多NP问题看起来需要指数时间来处理。例如,对于大整数质因子分化这个大概是NP中最出名的问题,验证一个解几乎只需要做一次乘法,但要实去解的话似乎需要系统地测验考试大量的可能解。

  所以“P能否等于NP”的意义是说“若是一个问题的解能够正在多项式时间内被验证,那么能否能够正在多项式时间内找到这个解”。这个问题的部门魅力正在于,大量典型的看起来需要指数时间去处理的NP问题被称为“NP完全问题”(NP-complete,NPC),它们能够正在多项式时间内彼此转化。这意味着若是此中一个问题是多项式时间可解的,那么所有其他问题也都是。第一个NPC问题是库克-列文(Stephen Cook, Leonid Levin)给出的布尔可满脚性问题(Boolean Satisfiability problem,SAT)。于是,任何NP问题都能够正在多项式时间内转化为SAT问题。取此等价地,若是SAT正在P中,那么P=NP。这即是出名的库克-列订婚理(Cook–Levin theorem)。

  正在现实糊口中,NP完全问题是相当遍及的,出格是正在大的安排使射中。麻省理工学院旧事曾列举了一个出名的NP完全问题是所谓的旅行商问题(Traveling Salesman Problem,TSP)。该问题正在当今很发财的物流业中能够表述为:一个物流配送公司欲将N个客户的订货沿最短路线全数送到,那么它该当若何确定最短路线?对于这一问题,P=NP意味着如许的物流分派能够很快地进行,但反之则意味着当物流规模逐步扩大时,我们将无法正在无效时间内找到最短路线。

  综上,我们将P、NP、NPC以及PSPACE等复杂度类及它们之间彼此的关系总结如下图。我们还晓得,SAT取TSP正在NPC中,而图同构和大整数分化等问题既没有被证明正在P中,也没能被证明正在NPC中,大部门理论计较机科学家认为它们的难度介于P取NPC之间(NP-intermediate,NPI)。

  几乎没有一个数学家、物理学家或者计较机科学家相信P实的等于NP——那样的话,所有的暗码将很容易被破解,良多搅扰人们的数学问题将有法子被处理,人工智能将冲破连连……一个想到谜底和验证谜底所需时间相当的世界,会是我们所保存的世界吗?若是是的话,为什么世界上最伶俐的数学家会对着一些数学问题思索良久,而当他们想出谜底时,又是那么快地就能验证谜底能否准确呢?既然大大都人感觉P不等于NP,那么它的证明事实有什么用?研究它又有什么意义?

  麻省理工学院(MIT)数学系从任以及计较机科学、人工智能尝试室计较理论小组(Theory of Computation Group,TOC)成员Michael Sipser认为,P/NP问题有帮于我们愈加深切地舆解计较复杂性。“一个次要的使用是正在暗码学范畴,此中暗码平安性经常是由计较使命的复杂性保障的,”Sipser说,“互联网平安买卖常用的RSA加密方案就是研究特定命论计较复杂性问题时的一个副产物”。此外,“P/NP问题曾经被数学界的人们普遍认为是根基、主要而斑斓的数学问题。我认为它是数学和计较机科学之间的桥梁

  对于同样的问题,TOC的另一位成员、MIT计较机科学和人工智能尝试室副传授Scott Aaronson(现为德克萨斯大学奥斯汀分校计较机科学传授)也供给了他的回覆:“是的,几乎所有的人都相信P是不等于NP的。可是,研究这个问题的过程要比成果主要。这个过程中,为了证明它,我们将需要大量的对计较的簇新理解。我们想要证明的是什么?是对于处理所有这些优化问题、搜刮问题、找到定理的证明、找到航空公司的最佳路线设想、破解暗码——所有这些分歧的工具,无论你何等伶俐,都不克不及找到无效的算法。所以,为了证明如许的命题,一个先决前提就是要领会所有可能的无效算法构成的空间。这可是一个令人难以相信的艰难使命。我们期望的是,正在证明这件工作的过程中,我们会领会到大量的远超我们想象的关于无效算法的理论,并且很是很是有可能发觉新的、当下无法预知的正在某些处所有奇异使用的算法。理论计较机科学的汗青经常是如许的,你用来证明一些工具不成能的论据恰好能够反过来申明此外工具可能,反之亦然。最简单的例子是加密,当你证明一些问题难以被无效处理时,你也会获得一个有用的编码方式

  值得一提的是,正在研究P/NP问题时,良多复杂性类的引入有着普遍而深切的理论意义和现实意义,有界错误概率多项式时间类(bounded-error probabilistic polynomial time,BPP)即是此中之一。此时不得不提的即是概率算法。一方面,20世纪80年代以来良多科学家认为概率的引入有帮于处理P/NP问题。另一方面,若是非要和下文中的量子力学扯上关系,概率算法长短说不成的——量子算法天然即是概率算法!

  典型的概率算法包含“抛硬币”的指令,而且抛硬币的成果可能影响算法后面的施行和输出。BPP是如许的一类鉴定问题:若是谜底是必定的,那么存正在?个多项式时间随机算法以?于2/3的概率接管,若是谜底能否认的则?于1/3。换句话说:给定任何输?,该算法错误的概率最多为1/3。1/3这个数字的意义仅仅正在于它是某个?于1/2的正的常数。任何如许的常数都是?样好的。为什么呢?嗯,假设我们获得?个犯错概率为1/3的BPP算法。若是我们实想要的话,我们能够很容易地将这个算法的犯错概率点窜为最多(?如说2^{-100})。怎样做呢?我们仅需要频频运?该算法?百次,然后输出占大都的谜底!所以,这就是BPP:良多人认为,BPP是典范物理学节制的宇宙入彀算机能够切实处理的所有问题构成的类。

  BPP取P、NP等的关系若何呢?明显,P包含于BPP,由于P即是不需抛硬币、输出成果确定的BPP。而现正在良多科学家认为,P可能等于BPP,这是又一个开放性问题。风趣的是,我们以至还不晓得BPP取NP的关系,而只晓得BPP包含于PSPACE。因此,下面的关系图中,虚线又增加了:

  看起来,BPP的插手未必能够处理P/NP问题,反倒带来了更多尚未有谜底的问题。而现实上,更多的复杂度类由于研究的需要被引入了进来。正在Scott Aaronson开的复杂度类动物园(Complexity Zoo)中,人们不竭地插手新的复杂度类,到现正在曾经有了498只复杂性类!人们不晓得这个研究过程何时是个起点。

  综上所述,若是P=NP成立,那么世界将换一个容貌;而若是可以大概证明二者不相等,我们也会取得脚够多的新冲破。这恰是其主要性所正在。而它很坚苦的缘由恰好正在于,我们还没能较为清晰地看到一条通往它的道路。

  “你如果光看报、读杂志等,你可能会感觉一个量子计较机能够通过‘并行地测验考试每一个可能的解’,然后‘正在心净跳一下的时间里处理NP完全问题’。嗯,大要那是外行人们对于量子计较机最焦点的错误印象Scott Aaronson正在接管麻省理工学院旧事采访时说。

  “Peter Shor(另一位TOC成员)发觉大整数分化的多项式量子算法时,量子计较界确实炸了正在麻省理工学院旧事的报道中,Sipser引见说。“Peter的冲破激发了计较机和物理两个范畴的一大波研究。现实上,Shor的发觉一度点燃了人们操纵微不雅标准下反曲觉的量子力学来正在多项式时间内处理NP完全问题的但愿。但现正在看来这似乎不太可能:大整数分化问题现实上是几个不晓得能否为NP完全的NP坚苦(NP-hard)问题同样地,人们不克不及证明不存正在多项式的大整数分化算法,所以虽然人们相信量子计较对于大整数分化如许的问题会带来计较能力的提拔,但这点同样尚未获得证明——更别提对于一般问题的指数级此外冲破了。

  对此,Scott Aaronson引见了Grover算法做为例子。Grover算法对于输入规模为N的无序数据库给出的2^{N/2}时间复杂度的量子搜刮算法。但早正在Grover的算法之前,Bennett等人曾经证明2^{N/2}是最优解了!换句线^N那么大的大海中捞一根针的量子算法都需要至多2^{N/2}步。响应地,典范计较机需要2^N步。所以致多能够说,对于“一般的”或者“无布局的”搜刮问题,量子计较机对于典范计较机来说只能给出某种加快——现实上是平方加快——但不会是像Shor算法那样的指数加快。

  为什么这个加快会是平方的,而非立方或者其他什么的?Scott Aaronson测验考试着给出了谜底,且尽量不牵扯到Grover算法或者Bennett等人最优化证明的具体细节。他认为,从底子上讲,我们获得平方加快的缘由是,量子力学是基于2-范数而非1-范数的。典范来讲,若是有N个解,此中只要一个是准确的,那么查询一次后我们距离获得准确谜底便有了1/N的概率,查询两次后便有了2/N的概率,查询三次3/N,依此类推。因而,我们需要N次查询来获得脚够大(即接近1)的概率猜出准确谜底。可是若是用量子力学,我们是对一组几率幅态矢进行线性变换,它是概率的平方根。所以我们如许考虑这个问题:查询一次后我们有1/\sqrt{N}的几率幅获得准确谜底,查询两次后是2/\sqrt{N}几率幅,查询三次后是3/\sqrt{N}几率幅,依此类推。所以颠末T次查询后,我们获得准确谜底的几率幅为T/\sqrt{N},然后概率即是T/\sqrt{N}^2= T^2/N。因而我们需要大约T \sqrt{N}次查询来获得接近于一的概率。

  量子计较机概念的引入给我们带来了新的复杂度类,此中最典型的一个即是BQP,即有界错误量子多项式时间类(bounded-error quantum polynomial time)。取BPP雷同地,BQP指能够正在多项式时间内用量子计较机以小于1/3的错误概率处理的问题的调集。良多人认为,BQP是量子物理学节制的宇宙入彀算机能够切实处理的所有问题构成的类。

  正在通往P/NP问题的路上,有良多的测验考试,例如量子力学、电路下界、交互式证明手艺等,都先是让人们看到了但愿,然后跟着研究的深切,又让人们感觉这些可能还不敷。那么,还有什么“有但愿的”处理方案吗?Scott Aaronson引见了芝加哥大学计较机系传授Ketan Mulmuley的几何复杂性理论纲要(Geometric Complexity Theory program, GCT program)。GCT试图将P/NP问题取代数几何、暗示理论等良多看起来比力远的数学概念联系起来。

  “我感觉GCT就像计较机科学范畴的弦论,”Scott Aaronson说,“一方面,它实现了如斯惊人的数学联系,以致于一旦你看到它们,你就会感觉这个纲要必然会正在准确的道路上。而另一方面,若是你用曾经处理了几多它最后想处理的问题,而不是这一纲要本身来评价它的话,那么可能它连最后的设法都还没有实现也就是说,大概恰是由于还没有脚够深切的领会,所以GCT还保留着处理P/NP的但愿。“以至GCT纲要最疯狂的支撑者也预测说得有几十年的跋涉,并且其正在数学上的复杂性也吓唬到了其他每小我

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.