為什么P／NP問題這么難？

《為什么P／NP問題這么難？》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。

1、為什么P/NP問題這么難？P和NP是否相等通常被認為是理論計算機科學中最重要的難題，也是克雷數(shù)學研究所高額懸賞的七個千禧年難題之一。5天前，德國波恩大學的計算機科學家NobertBlum在arXiv上傳了一份38頁長的論文，聲稱證明了P/二NP(P不等于NP),引發(fā)學界的關注與討論(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就在社交平臺上發(fā)表意見稱，安德烈耶夫方程(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,但都被發(fā)現(xiàn)證明過程有誤。事實上，到冃前為止，還沒有人能夠回答這個問題。2002年，有70位數(shù)學家和計算機科學家被邀請參與一次投票，投P是否等于NP。其中的61位認為P不等于NP,而剩下的人里有好幾個都表示投“等于,,只是為了采取相反的立場。粗略地說

6、，P代表一組相對容易的問題，而NP代表一組看起來非常難的問題。因此，P=NP將意味著明顯困難的問題其實有比較容易的解決方案——當然，其屮的細節(jié)還要麻煩一些。實際上，量子計算機、圖同構問題等人們熱衷的最新進展無不指向P對NP問題。那么，P與NP問題究竟是什么？它的解決將意味著什么？它難在哪里？量子力學為它帶來了什么？又有什么理論、將在何時有可能解決它？本文試圖對這些問題提供簡單的介紹和探討。1當我們說P/NP問題時，說的是什么？圖靈時期的計算機科學關注的主要是問題的W計算性(computability),也即一個問題是否可以被計算機描述并解決。之后，隨著可計算性問題的澄

7、清，計算機科學家逐漸將注意力轉移到了另一個問題，即問題的復雜性(complexity):執(zhí)行一個給定的算法需要多長時間？不過，計算機科學家的答案不是幾分鐘或者幾毫秒，而是所需時間與問題規(guī)模的函數(shù)關系?！堵槭±砉W院新聞》(⑷TNews)曾發(fā)表過一篇解釋P/NP的文章。這篇文章指出，想象有一張未經排序的數(shù)字列表，然后寫一個尋找最大值的算法。首先顯然，該算法必須要查詢列表中的所有數(shù)字。但是，如果它只是在每一步查詢一個數(shù)字，然后只更新并記錄當下的最大數(shù),那么對于每個數(shù)字，它只需要查詢一次。于是，該算法的執(zhí)行時間與它處理的問題規(guī)模，即計算機科學家們所指的N,