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

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

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

  编译 | 张林峰(普林斯顿大学应用数学专业博士研究生)

  责编 | 陈晓雪

  P和NP是否相等通常被认为是理论计算机科学中最重要的难题,也是克雷数学研究所高额悬赏的七个千禧年难题之一。

  5天前,德国波恩大学的计算机科学家Nobert Blum在arXiv上传了一份38页长的论文,声称证明了P/=NP(P不等于NP),引发学界的关注与讨论 (https://arxiv.org/abs/1708.03486)

 Nobert Blum宣称证明P/=NP的论文

 Nobert Blum宣称证明P/=NP的论文

  很快,加州大学伯克利分校的电子工程与计算机科学教授Luca Trevisan就在社交平台上发表意见称,安德烈耶夫方程 (Andreev’s function),也即论文证明中的关键,在文中被认为具有超多项式电路复杂度 (superpolynomial circuit complexity),而实际上可以被高斯消去法 (Gaussian elimination) 解决,所以仅有多项式复杂度,这使得文中的证明不能成立。该证明是否正确还有待人们的进一步仔细检查。

 Luca Trevisan认为,Blum文中的证明不能成立

 Luca Trevisan认为,Blum文中的证明不能成立

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

  粗略地说,P代表一组相对容易的问题,而NP代表一组看起来非常难的问题。因此,P= NP将意味着明显困难的问题其实有比较容易的解决方案——当然,其中的细节还要麻烦一些。

  实际上,量子计算机、图同构问题等人们热衷的最新进展无不指向P对NP问题。那么,P与NP问题究竟是什么?它的解决将意味着什么?它难在哪里?量子力学为它带来了什么?又有什么理论、将在何时有可能解决它?本文试图对这些问题提供简单的介绍和探讨。

  1当我们说P/NP问题时,说的是什么?

  图灵时期的计算机科学关注的主要是问题的可计算性(computability),也即一个问题是否可以被计算机描述并解决。之后,随着可计算性问题的澄清,计算机科学家逐渐将注意力转移到了另一个问题,即问题的复杂性(complexity):执行一个给定的算法需要多长时间?不过,计算机科学家的答案不是几分钟或者几毫秒,而是所需时间与问题规模的函数关系。

  《麻省理工学院新闻》(MIT News)曾发表过一篇解释P/NP的文章。这篇文章指出,想象有一张未经排序的数字列表,然后写一个寻找最大值的算法。首先显然,该算法必须要查询列表中的所有数字。但是,如果它只是在每一步查询一个数字,然后只更新并记录当下的最大数,那么对于每个数字,它只需要查询一次。于是,该算法的执行时间与它处理的问题规模,即计算机科学家们所指的N,直接成正比。当然,大多数算法是更为复杂的,因此比寻找最大值算法的效率要低。但是有许多常见算法的执行时间与N^2,或者N log(N)成正比。

 无序数字列表求最大值的算法示意。MAX指最大值,N指数字个数,a[i]指当前查询的第i个数字

 无序数字列表求最大值的算法示意。MAX指最大值,N指数字个数,a[i]指当前查询的第i个数字

  一个只包含常数、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意味着这样的物流分配可以很快地进行,但反之则意味着当物流规模逐渐扩大时,我们将无法在有效时间内找到最短路线。

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

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