舟山新闻网,为您提供最佳全面的最新舟山新闻信息!
当前位置:主页 > 科技 > 正文

最新证明面临质疑丰台火车站最新消息:P/NP问题为什么这么难?(2)

时间:2017-08-16 12:52 来源:http://www.bmeetg.com/ 作者:舟山新闻网 阅读:

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

 复杂度类关系示意图。实线框表示已被证明的真包含关系,虚线框表示尚未被证明的真包含关系(下同)

 复杂度类关系示意图。实线框表示已被证明的真包含关系,虚线框表示尚未被证明的真包含关系(下同)

  2P/NP问题有什么用,又难在哪里?

  几乎没有一个数学家、物理学家或者计算机科学家相信P真的等于NP——那样的话,所有的密码将很容易被破解,很多困扰人们的数学问题将有办法被解决,人工智能将突破连连……一个想到答案和验证答案所需时间相当的世界,会是我们所生存的世界吗?如果是的话,为什么世界上最聪明的数学家会对着一些数学问题思索良久,而当他们想出答案时,又是那么快地就能验证答案是否正确呢?既然大多数人觉得P不等于NP,那么它的证明究竟有什么用?研究它又有什么意义?

  麻省理工学院(MIT)数学系主任以及计算机科学、人工智能实验室计算理论小组(Theory of Computation Group,TOC)成员Michael Sipser认为,P/NP问题有助于我们更加深入地理解计算复杂性。“一个主要的应用是在密码学领域,其中密码安全性经常是由计算任务的复杂性保障的,”Sipser说,“互联网安全交易常用的RSA加密方案就是研究特定数论计算复杂性问题时的一个副产品”。此外,“P/NP问题已经被数学界的人们广泛认为是基本、重要而美丽的数学问题。我认为它是数学和计算机科学之间的桥梁。”

 Michael Sipser

 Michael Sipser

  对于同样的问题,TOC的另一位成员、MIT计算机科学和人工智能实验室副教授Scott Aaronson(现为德克萨斯大学奥斯汀分校计算机科学教授)也提供了他的回答:“是的,几乎所有的人都相信P是不等于NP的。但是,研究这个问题的过程要比结果重要。这个过程中,为了证明它,我们将需要大量的对计算的崭新理解。我们想要证明的是什么?是对于解决所有这些优化问题、搜索问题、找到定理的证明、找到航空公司的最佳路线设计、破解密码——所有这些不同的东西,无论你多么聪明,都不能找到有效的算法。所以,为了证明这样的命题,一个先决条件就是要了解所有可能的有效算法组成的空间。这可是一个令人难以置信的艰巨任务。我们期望的是,在证明这件事情的过程中,我们会了解到大量的远超我们想象的关于有效算法的理论,而且非常非常有可能发现新的、当下无法预知的在某些地方有神奇应用的算法。理论计算机科学的历史经常是这样的,你用来证明一些东西不可能的论据恰恰可以反过来说明别的东西可能,反之亦然。最简单的例子是加密,当你证明一些问题难以被有效解决时,你也会得到一个有用的编码方法。”

Scott Aaronson

Scott Aaronson

  值得一提的是,在研究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加入后的复杂度类关系示意图

BPP加入后的复杂度类关系示意图

  看起来,BPP的加入未必可以解决P/NP问题,反倒带来了更多尚未有答案的问题。而事实上,更多的复杂度类因为研究的需要被引入了进来。在Scott Aaronson开的复杂度类动物园(Complexity Zoo)中,人们不断地加入新的复杂度类,到现在已经有了498只复杂性类!人们不知道这个研究过程何时是个终点。

  综上所述,如果P=NP成立,那么世界将换一个模样;而如果能够证明二者不相等,我们也会取得足够多的新突破。这正是其重要性所在。而它很困难的原因恰恰在于,我们还没能较为清楚地看到一条通往它的道路。

  3量子力学带来了什么?

  “你要是光看报、读杂志等,你可能会觉得一个量子计算机可以通过‘并行地尝试每一个可能的解’,然后‘在心脏跳一下的时间里解决NP完全问题’。嗯,大概那是门外汉们对于量子计算机最核心的错误印象。”Scott Aaronson在接受《麻省理工学院新闻》采访时说。

(责任编辑:舟山民生在线)

顶一下
(0)
0%
踩一下
(0)
0%