一個價值百萬美金的問題

2000年5月24日，在參考了一個世紀前希爾伯特提出的23個問題的做法之後，克雷數學研究所發布了七道千禧年大獎難題，總價值七百萬美金。解答任何一道問題的第一個人將被授予一百萬美金的獎勵。在這七個問題中，一道關於解決P和NP的複雜度問題成為了整個計算機領域的焦點，因為這個問題的結論會直接給計算機領域帶來截然不同的理論極限和發展前景。

在說明這個問題以及該問題在計算機領域的影響之前，我們先簡單的闡述一下關於時間複雜度的定義以及複雜度學說中的幾個大的問題集合。

首先需要說明的是，時間複雜度並不是表示一個程序解決問題需要花多少時間，而是當問題規模擴大後，程序需要的時間長度增長得有多快。比如說，如果一個程序在輸入數據的規模變大到數百倍後，程序運行時間是不變的，那我們說這個程序的時間複雜度是O(1)，或常數級複雜度。比如在隊列中插入或刪除。無論隊列多長，所需插入和刪除的時間並不會因其發生改變。

同樣，如果程序運行時間隨著數據規模增大而等量增大，那我們稱這個程序的時間複雜度為O(n)。比如在n個數中找最大值的演算法。程序需要在遍歷所有數值之後得到最大值。輸入數據的規模n增大，所需要遍歷的時間也等量增大。再比如像冒泡排序（bubble sort）這樣數據擴大2倍，執行時間延長4倍的程序，我們稱其複雜度為O(n2)。（冒泡排序是一種簡單的排序演算法，通過一次走訪並比較數列中的兩個元素，然後重複走訪需要排序的數列來達到排序的效果。）

而像一些窮舉法更有像O(a^n)甚至O(n!)這樣的階乘級複雜度，其中a為常數。在此基礎上，複雜度被分成了兩大類。第一種是像O(1), O(n), O(n^a)等，我們稱其為多項式級的複雜度。而像O(a^n), 和O(n!)等，我們稱其為非多項式級的複雜度。非多項式級的複雜度遠遠超過了多項式級，特別是在數據規模非常大的時候，其複雜度是計算機遠無法承受的。在這裡需要聲明的是多項式級的複雜度並不代表簡單，O(n^100)的複雜度也屬於多項式級，但即便是n=100的輸入數據也是一個很大的複雜度。

那麼是否所有問題都能找到一個複雜度為多項式級的演算法呢？答案是否定的。有些問題現在還不能用一個正確的演算法來描述，或者說根本不可能用一個正確的演算法來描述。比如之前提到的停機問題。圖靈巧妙地用自洽的角度證明了停機問題的不可解，從而使得用演算法來描述該類問題變得不可能。（具體參見《一個無法證明的邏輯問題》）。於是，所有問題因其不同的複雜度被分成了不同的集合。

首先是P類（Polynomial）問題。如果一個問題可以找到一個能在多項式的時間裡解決它的演算法，那麼這個問題就屬於P問題。其次是NP類（None-deterministic Polynomial）問題。需要注意的是，NP類問題並不是P類問題的對立面（或非P類問題），而是指可以在多項式的時間裡驗證（而非獲得）一個解的問題。換句話說，這類問題需要解題的人先猜一個答案，這個答案能在多項式時間裡得到驗證。這類問題通常解決起來很困難但驗證起來很簡單。比如判斷在起點到終點的各種路徑中是否有一條總路程小於10個單位長度的路徑。解決這種問題最壞的可能需要窮舉所有的路徑，屬於非多項式級的複雜度。而驗證一個答案卻很簡單。只需要花O(n)的時間把我猜出來的路徑長度加起來即可。這類問題就是NP問題。

我們按照常識判斷，一個屬於P類的問題，也一定屬於NP類。這個很容易理解，能在多項式時間裡找到答案就一定能在多項式時間裡驗證這個答案（大不了重做一次）。換句話說，P集合屬於NP集合。那麼問題來了，一個屬於NP類的問題，是否也屬於P類呢？換句話說，是否存在一個演算法，能在多項式時間裡找出NP類問題的解。也就是說，我們能否證明或者推翻P=NP？先別急著回答，因為它值一百萬美金。

雖然P=NP這個結論到現在還沒有得到證明或者被推翻，大多數研究者們普遍相信它是不成立的。2001年一項針對100名數學和計算機科學家的調查結果是其中61人相信P≠NP，2012年調查者重複了這一問卷，結果相信P≠NP的人增加到了84%。在研究方面，迄今為止最大的成果是史蒂芬庫克在上世紀70年代時的成果。他定義了一個新的問題集合，使得所有NP問題都能規約成為這類問題。也就是說如果我們能找到一個擁有多項式級複雜度的演算法來解答這個新集合里的任意一個問題，那麼所有的NP問題就都是在多項式時間內可解的。這個新的集合被稱作NP-完全（NP-Complete，簡稱NPC）問題。

為了進一步了解NPC問題，我們先來說一下規約。如果用解決問題B的辦法能夠也能夠解決問題A，那麼我們就說問題A可以被規約到問題B，儘管可能用解決問題B的方法解決問題A可能會增加不必要的複雜度。舉個例子，儘管沒有人會用解一元二次方程的通用公式來解一元一次方程，但至少我們也是能夠用這個公式來解一元一次方程。所以我們就可以將一元一次方程的問題規約到一元二次方程問題上。就這樣以此類推的規約下去，所有的NP問題都可以規約到一些更寬泛的問題里，而這些更寬泛的問題的集合就是NPC問題。由此，對P是否等價NP這一問題被簡化成了證明是否能用有多項式級複雜度的演算法來解決NPC問題。而史蒂芬庫克也因其在該領域的貢獻被授予了圖靈獎。

隨著計算機的普及，各個領域也開始使用計算機來做一些需要大量計算的研究。而多數這類研究最後都被證明是NPC問題。例如生物方面的基因序列比對[1]，經濟方面的納什均衡計算[2]，甚至是計算機領域本身的電路優化及核對[3]。所以對於P=NP這一問題的證明或推翻，大大的影響著各行各業的發展。

如果今後被證明了P=NP，那麼在信息學上面密碼的破解將變得容易，因為我們總能在多項式時間裡找出正確密碼。（正如之前提到的，多項式級的複雜度並不代表簡單，即便是我們能證明P=NP也並不代表我們能找到一個相對複雜度較低的演算法來破解密碼。所以對那些覺得證明了P=NP之後密碼將會形同虛設的說法，筆者還是抱持懷疑態度。）同時人工智慧的發展前景也會一片大好，因為機器學習的過程也總能在多項式時間內完成。我們也能設計出更加優化的晶元使得計算機的極限被大大拓展。

相反，如果證明出P≠NP這一結論，那麼傳統計算機能做到的東西（包括機器學習）就會相對變得有限很多。不僅如此，上期提到的程序可並行化的程度也將因此受到影響。要了解這個問題，我們需要了解另外一個概念—NC規約。

NC規約（Niche Class)是將P類問題規約到一個更小的PC類（P-Complete)[4]，使得這類問題能夠在具有多項式複雜度的集成電路上運行，換句話說，就是該類問題能被有效並行化。如同P類問題屬於NP類，NC類的問題也屬於P類。但同樣的問題是，我們無法證明是否P類問題也屬於NC類，也就是說，我們在無法證明P=NC的情況下，無法知道現下可有效執行的演算法（P類問題）是否都能被有效並行化。所以相信P≠NP這一結論的人同樣也相信P≠NC這一結論。也就是說，大多數人也相信PC類的問題是無法被有效並行化的。除非今後真的有人證明出了P=NP這一結論，不然程序可並行化的上限也會被程序本身的複雜度所限制。

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！