在所有的千年之謎中，有一個極其特殊的問題。它的誕生和計算機的出現息息相關。雖然距離它的提出，已經度過了47年的悠悠歲月，卻仍然是
最年輕的千年難題。令人驚異的是，其它所有千年問題的解決都強烈依賴於高度專業的數學訓練，唯有開啟它的鑰匙卻可能掌握在一個“無名的業餘愛好者”手中。無需擁有高深的數學知識，一個人就可能在突發奇想間找到破譯它的密碼。要打開這座塵封半個世紀的寶藏，人們需要的，僅僅是天馬行空的想象力。這就是著名的P與NP問題。
計算機之於信息時代
進入信息時代以來，人們的生活愈發離不開計算機的輔助。無論是個人的學習、工作、娛樂，甚至衣食住行，又或是群體的商業往來、競技比賽、交通運輸、信息通訊、工業製造等等都因為計算機的參與而被納入到信息時代的軌道之中。計算機因為其強大的效率和生產力，已經滲透到當代人們生活的每一個角落。
不僅如此，最尖端的科學研究、國防軍工、航空航天以及人工智能、大數據分析都已經深深地依賴於計算機的性能。歷史上從來沒有一個時代，人們如此地仰仗於一個工具來塑造自己的生活。
計算機對人們生活的影響主要體現在硬件和軟件之上。一方面，昔日“失之毫釐、謬以千里”的古訓在今天已經成為現實。基於硬件的半導體工藝水平伴隨著摩爾定律每隔18個月就會翻倍。這意味著即使計算機的性能落後2年，整體的性能就可能落後3倍。這在科技競爭和國防事業中會造成不可承受的天壤之別。也因此，每一個有志立足於世界民族之林、在世界尖端科技的潮流中勇爭一席之地的國家，都將計算機的發展視為最重要的國之利器。
另一方面，在硬件技術遠遠落後的情況下，後發者想取得先發優勢，唯有充分利用已有計算機的計算能力，將軟件的效能發揮到極致。P與NP問題也就誕生於人們追求計算機解決問題的效率之中。這一切，又起源於希爾伯特在1900年提出的第十問題。
希爾伯特的問題是設想是否存在一系列的機械步驟，使之能判定一般的丟番圖方程是否有解。在那個年代，人們對機械步驟的定義尚不明確，但這意外地激發了英國數學家圖靈（Turing）的興趣。圖靈機的概念就在他研究希爾伯特第十問題的過程中橫空出世。這為後世計算機的理論奠定了牢不可破的基礎。
1931年，奧地利數學家哥德爾（Godel）天才般地證明了“不完備定理”，顛覆了希爾伯特希望通過公理化體系來完成一切數學證明的願望。在文章中，哥德爾展示瞭如何將可證明性的問題轉化為與之等價的某種可計算性的問題，從而建立了“可計算函數”概念的形式理論。“可計算性”概念的澄清和圖靈機的構想，終於幫助人們打開了通往現代計算機的大門。
P=NP?
隨著計算機的廣泛應用，它能處理的問題也愈來愈複雜，隨之而來對計算機的性能和軟件的效率提出了極高的要求。因此，一門關於計算機解決問題效率的複雜性理論應運而生。這其中的首要問題就是要找出一種方法來度量在一臺計算機上執行一項特定任務需要多長的時間。很明顯，一個問題具有的數據越多，花費在計算機上的時間就越長。人們迫切希望知道，計算機解決問題的時間與數據量的增長額度的關係。人們把這種關係稱作這個過程的“時間複雜性函數”。而P問題，就是多項式問題，指代的是時間過程以多項式表達式為時間複雜性函數的過程。
幸運的是，P問題是計算機能夠有效處理的問題，人們可以為解決一個問題而等待多項式複雜度的時間。比如計算機做乘法計算就是多項式時間複雜度的典型例子。不幸的是，還存在著一類問題，它消耗的計算機時間以指數函數為複雜度。每增加一個計算量，就可以導致計算時間翻倍，比如圍棋的博弈。這遠遠超過了人們能夠等待的生命時間。
多項式時間過程與指數時間過程之間存在著巨大的鴻溝，人們逐漸意識到需要尋找一種中間尺度的複雜性過程。於是，第三種模型：NP問題也呼之欲出。NP問題指代一種非確定性多項式的時間過程。一般而言，計算機都是確定性的過程——它們按照事先規定好的規則以一種完全確定的方式工作。非確定性則代表這樣一種可能，計算機在執行某個任務時，可以隨機地猜測下一步的行動，如果這個選擇的運氣足夠好，使得它每次都能做出最佳的選擇，那麼它就能在多項式時間內解決該問題。
NP問題介於多項式問題和指數時間問題之間，但是它建立在一個完全不現實的想法基礎之上，即有一種計算機總是能在每一步做出最佳的隨機選擇，然而它卻在隨後的生產實踐中發揮著重大的作用。事實上，在工業和管理中出現的大多數指數時間問題都是NP型的。
因此，NP分類在20世紀60年代被提出之後，人們就希望P與NP類問題並不是同一類問題。然而，誰也無法證實這一猜測。此時，來自美國的庫克（Cook）於1971年證明了一個匪夷所思的結論。在那篇著名的論文中，庫克斷言，存在一個特殊的NP問題，它具有一種奇特的性質，如果這個特殊的問題能用多項式時間過程解決，那麼其他任何的NP問題也能！這個性質被庫克命名為NP完全性。隨後，很多重大的工業和商業問題都被證明是NP完全問題，比如郵差送信、旅行路線規劃問題等等。然而，NP完全問題因為其詭異的性質而被認為最不可能是P類的問題。不久，庫克和樂文（Levin）各自獨立提出瞭如今的第三個千年之謎，NP完全問題是否可能由計算機在多項式時間內解決，即P與NP問題是否是同一類問題？
結語
P與NP的等價性及其證明，將徹底顛覆人們對所有可計算問題的認識，其影響力將衝擊到現代世界的每一個角落。如果P與NP問題最終被證明是等價的，那麼基於數字密碼的所有加密系統都將是不安全的，它都能在多項式時間內被計算機破解，從而破壞人們賴以生存的信息安全網絡。這會對基於互聯網的安全產生極其嚴重的後果，對世界經濟強烈依賴於電子通信安全的基礎給予致命性的打擊。因此，不管P與NP問題最終的結果如何，它的解決必將帶來世界經濟和安全格局的煥然一新。
閱讀更多 IDGAF 的文章
