为什么P／NP问题这么难？

《为什么P／NP问题这么难？》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、为什么P/NP问题这么难？P和NP是否相等通常被认为是理论计算机科学中最重要的难题，也是克雷数学研究所高额悬赏的七个千禧年难题之一。5天前，德国波恩大学的计算机科学家NobertBlum在arXiv上传了一份38页长的论文，声称证明了P/二NP(P不等于NP),引发学界的关注与讨论(https：//arxiv.org/abs/1708.03486)。ZJOeODnv二OO.S。二>9ocASolutionofthePversusNPProblemNorbertBlumliistitutfiirInfbrniatik,UniwrsitiitBonnFYiedrich-E

2、bcrt-Allec144,D-53113Bonn,Grnnanycnuiil:blumiic^.uni-bonn.de•August14,2017AbHtraclBergandUlfbcrgJandAmanoaridMivruobi;2haveusedCNF-DNF-approKimatorstoproveexponentiallowerboundsforthemonotow*twtzrkcomplexityofUwcliquefunctionfuxlofAnckzvlfutx>tion・Vieshowtlmtihfajqjroxim^torsam!«•usedt

3、oprowthejwtnwkmvrbowidfcxrtlirixnon-moix>toncnetworkcoenpicxily,ThbP/NP.NobertBlum宣称证明P/=NP的论文很快，加州大学伯克利分校的电子工程与计算机科学教授LucaTrevisan就在社交平台上发表意见称，安德烈耶夫方程(Andreev，sfunction)，也即论文证明中的关键，在文中被认为具有超多项式电路复杂度(superpolynomialcircuitcomplexity),而实际上可以被高斯消去法(Gaussianelimination)解决，所以仅有多项式复杂度，这使得文中的

4、证明不能成立。该证明是否正确还有待人们的进一步仔细检查。应4ShacharLovettAnybodyreaditandhassomeinformedthoughts?[1708.03486]ASolutionofthePversusNPProblemarxiv.org1ShareLikeComment介Share©14LucaTrevisanAndreev'sfunction,whichisclaimedtohavesuperpolynomialcircuitcomplexity(abstract,thensection7),isjustunivariatepolyn

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

6、，P代表一组相对容易的问题，而NP代表一组看起来非常难的问题。因此，P=NP将意味着明显困难的问题其实有比较容易的解决方案——当然，其屮的细节还要麻烦一些。实际上，量子计算机、图同构问题等人们热衷的最新进展无不指向P对NP问题。那么，P与NP问题究竟是什么？它的解决将意味着什么？它难在哪里？量子力学为它带来了什么？又有什么理论、将在何时有可能解决它？本文试图对这些问题提供简单的介绍和探讨。1当我们说P/NP问题时，说的是什么？图灵时期的计算机科学关注的主要是问题的W计算性(computability),也即一个问题是否可以被计算机描述并解决。之后，随着可计算性问题的澄

7、清，计算机科学家逐渐将注意力转移到了另一个问题，即问题的复杂性(complexity):执行一个给定的算法需要多长时间？不过，计算机科学家的答案不是几分钟或者几毫秒，而是所需时间与问题规模的函数关系。《麻省理工学院新闻》(⑷TNews)曾发表过一篇解释P/NP的文章。这篇文章指出，想象有一张未经排序的数字列表，然后写一个寻找最大值的算法。首先显然，该算法必须要查询列表中的所有数字。但是，如果它只是在每一步查询一个数字，然后只更新并记录当下的最大数,那么对于每个数字，它只需要查询一次。于是，该算法的执行时间与它处理的问题规模，即计算机科学家们所指的N,