P對NP問題

P對NP問題是克雷數學研究所高額懸賞的七個千禧年難題之一，同時也是計算機科學領域的最大難題，關係到計算機完成一項任務的速度到底有多快。

基本介紹

• 中文名：P對NP問題
• 外文名：P versus NP problem
• 類別：數學問題
• 領域：計算機科學
• 作用：評測計算機完成任務速度

簡介

P對NP問題是Steve Cook於1971年首次提出。“P/NP問題”，這裡的P指多項式時間（Polynomial），一個複雜問題如果能在多項式時間內解決，那么它便被稱為P問題，這意味著計算機可以在有限時間內完成計算；NP指非確定性多項式時間（nondeterministic polynomial），一個複雜問題不能確定在多項式時間內解決，假如NP問題能找到算法使其在多項式時間內解決，也就是證得了P=NP。比NP問題更難的則是NP完全和NP-hard，如圍棋便是一個NP-hard問題。2010年8月7日，來自惠普實驗室的科學家Vinay Deolalikar聲稱已經解決了“P/NP問題” ，並公開了證明檔案。

排序問題

如果我們只能通過元素間的相互比較來確定元素間的相互位置，而沒有其他的附加可用信息，則排序問題的複雜性是O(nlgn)，但是排序算法有很多，冒泡法是O(n^2)，快速排序平均情況下是O(nlgn)等等，排序問題的複雜性是指在所有的解決該問題的算法中最好算法的複雜性。問題的複雜性不可能通過枚舉各種可能算法來得到，一般都是預先估計一個值，然後從理論上證明。

定義

為了研究問題的複雜性，我們必須將問題抽象，為了簡化問題，我們只考慮一類簡單的問題，判定性問題，即提出一個問題，只需要回答yes或者 no的問題。任何一般的最最佳化問題都可以轉化為一系列判定性問題，比如求圖中從A到B的最短路徑，可以轉化成：從A到B是否有長度為1的路徑？從A到B是否有長度為2的路徑？。。。從A到B是否有長度為k的路徑？如果問到了k的時候回答了yes，則停止發問，我們可以說從A到B的最短路徑就是k。如果一個判定性問題的複雜度是該問題的一個實例的規模n的多項式函式，則我們說這種可以在多項式時間內解決的判定性問題屬於P類問題。P類問題就是所有複雜度為多項式時間的問題的集合。然而有些問題很難找到多項式時間的算法（或許根本不存在），比如找出無向圖中的哈米爾頓迴路問題，但是我們發現如果給了我們該問題的一個答案，我們可以在多項式時間內判斷這個答案是否正確。比如說對於哈米爾頓迴路問題，給一個任意的迴路，我們很容易判斷他是否是哈米爾頓迴路（只要看是不是所有的頂點都在迴路中就可以了）。這種可以在多項式時間內驗證一個解是否正確的問題稱為NP問題。顯然，所有的P類問題都是屬於NP問題的，但是現在的問題是，P是否等於NP?這個問題至今還未解決。這就是P對NP問題。

“P類”、“NP類”、“更複雜的類”，是確定型Turing機DTM中的不同複雜性分類。這些分類是由不同問題的性質決定的，還是我們目前沒有找到好的DTM解決方法形成的？這就是“P對NP”問題上。它的基本意思是：

（1）P=NP：我們最終能夠找到一些計算方法，使得NDTM能夠快速解決的問題，在DTM上也能夠快速解決。快速的意思是“使用不超過輸入字元串的多項式時間”。

（2）P≠NP：NP只能用NDTM快速解決，而不能用DTM快速解決。

假如P≠NP，關於NP類內部的結構，可以再分成3個區域：P、NPC和NPI。

NPC和是NP里“最難的”問題，因為任何NP中的問題可以在多項式時間內變換成為任何特定NPC（NP-完全問題，NP-completeness）的一個特例。這就是說，如果找到一個NPC問題的快速解決方法，則所有的NP問題都可以快速解決了。NPI是NP中既不是P又不是NPC的問題類，如果P≠NP。

例如，密碼學中的“素數分解”（大數分解和素性檢測），就是一個NPC問題。假如P=NP，密碼學的工作者必須改造的工作，實在是太多了！如果P=NP，則現有的大量密文都是容易解密的。

NPC問題

注意，NP問題不一定都是難解的問題，比如簡單的數組排序問題是P類問題，但是P屬於NP，所以也是 NP問題，你能說他很難解么？剛才說了，現在還不知道是否有P=NP或者P<>NP，但是後來人們發現還有一系列的特殊NP問題，這類問題的特殊性質使得很多人相信P<>NP，只不過現在還無法證明。這類特殊的NP問題就是NP完全問題（NPC問題，C代表complete）。 NPC問題存在著一個令人驚訝的性質，即如果一個NPC問題存在多項式時間的算法，則所有的NP問題都可以在多項式時間內求解，即P=NP成立！！這是因為，每一個NPC問題可以在多項式時間內轉化成任何一個NP問題。比如前面說的哈米爾頓迴路問題就是一個NPC問題。NPC問題的歷史並不久，cook在 1971年找到了第一個NPC問題，此後人們又陸續發現很多NPC問題，現在可能已經有3000多個了。所以，我們一般認為NPC問題是難解的問題，因為他不太可能存在一個多項式時間的算法（如果存在則所有的NP問題都存在多項式時間算法，這太不可思議了，但是也不是不可能）。類似哈米爾頓迴路/路徑問題，貨郎擔問題，集團問題，最小邊覆蓋問題（注意和路徑覆蓋的區別），等等很多問題都是NPC問題，所以都是難解的問題。

要解決P = NP問題，NP完全的概念非常有用。不嚴格的講，NP完全問題是NP類中“最難”的問題，也就是說它們是最可能不屬於P類的。這是因為任何NP中的問題可以在多項式時間內變換成為任何特定NP完全問題的一個特例。例如，旅行推銷員問題的判定問題版本是NP完全的。所以NP中的任何問題的任何特例可以在多項式時間內機械地轉換成旅行商問題的一個特例。 所以若旅行商問題被證明為在P內，則P = NP！旅行商問題是很多這樣的NP完全的問題之一。若任何一個NP完全的問題在P內，則可以推出P = NP。不幸的是，很多重要的問題被證明為NP完全，但沒有一個有已知快速的算法。

與密碼學關係

關於“P對NP”問題對密碼學的影響，請看著名計算機科學家Stephen Cook（第一個NPC的提出者，1971年提出）2003年在“The importance of the P versus NP question”中的原始論述。Cook的基本看法是：

如果證明了P=NP，那么依據計算複雜性的密碼術就是沒有用途的。Internet（包含財政情報）的安全性是建立在這些假設上：大素數的分解、DES (the Data Encryption Standard)的解密，不能用數字計算機快速地解決。相反，量子密碼術不受P=NP的影響，可能解決Internet的安全性問題。

如果證明了P≠NP，那么大素數的分解還是不是NPC的？證明RSA、DES等密碼術的安全性比證明P1NP還困難。

不僅依據離散量運算的密碼學受到“P對NP”問題的影響，而且依據連續量運算的密碼學也受到實數環上的“P對NP”問題的影響。但人腦具有“潛意識”等非數學智慧型，如具有形象思維、動作思維、靈感直覺等，安全的密碼學總是存在的。正常人右腦的非數學智慧型明顯高於左腦的數學智慧型（Roger W. Sperry獲得1981年諾貝爾獎The Nobel Prize in Physiology or Medicine的工作），因此未來更安全密碼學的發展是沒有止境的！

P≠NP論證

如果P=NP，那么每個答案很容易得到驗證的問題也同樣可以輕鬆求解。這將對計算機安全構成巨大威脅，目前加密系統的破解就相當於要將一個整數分解為幾個因數的乘積，正是其求解過程的繁瑣，才能杜絕黑客的入侵。

而現在，美國惠普實驗室的數學家維奈·迪奧拉里卡圍繞一個眾所周知的NP問題進行論證，給出了P≠NP的答案。這就是布爾可滿足性問題(Boolean Satisfiability Problem)，即詢問一組邏輯陳述是否能同時成立或者互相矛盾。迪奧拉里卡聲稱，他已經證明，任何程式都無法迅速解答這個問題，因此，它不是一個P問題。

如果迪奧拉里卡的答案成立，說明P問題和NP問題是不同的兩類問題，這也意味著計算機處理問題的能力有限，很多任務的複雜性從根本上來說也許是無法簡化的。

對於有些NP問題，包括因數分解，P≠NP的結果並沒有明確表示它們是不能被快速解答的；但對於其子集NP完全問題，卻注定了其無法很快得到解決。其中一個著名的例子就是旅行商問題(Travelling Salesman Problem)，即尋找從一個城市到另一個城市的最短路線，答案非常容易驗證，不過，如果P≠NP，就沒有電腦程式可以迅速給出這個答案。

迪奧拉里卡的論文草稿已經得到了複雜性理論家的認可，但隨後公布的論文終稿還將接受嚴格的審查。