這個看似簡單的一個問題，實際上是理論計算機領域最大的未解難題。
2000年，在參考了一個世紀前希爾伯特提出的23個問題的做法之後，克雷數學研究所發佈了七道千禧年大獎難題，總價值七百萬美金。解答出任何一道問題的第一個人將被授予一百萬美金的獎勵。其中一道難題正是關於解決P和NP的複雜度問題。這個問題成為了整個計算機領域的焦點，因為這個問題的結論會直接給計算機領域帶來截然不同的理論極限和發展前景。
雖然從表面上看，P是否等於NP這個問題非常直接，但它的證明卻已困擾了研究人員長達數十年之久。簡單地說，P與NP問題問的是，能夠被容易解決的問題集合是否也屬於能夠被容易驗證的問題集合中。
讓我們來試想一個場景，假設你接收到了一項任務，內容是將一個打碎的茶杯重新粘合在一起。要想檢驗你是否成功地完成了這項任務是非常簡單的——如果成功了，你的面前就會有一個完整的茶杯。但是，將每一塊散落的碎片重新粘合起來是件很困難的事。這就是NP問題的一個例子：
難解，卻容易驗證。假如現在你的任務不是重新粘合破碎的茶杯，而是計算茶杯被打碎成了多少塊。這就變成了一個P類問題。相比而言，計算碎片的數量比計算它們之間的聯繫要容易得多。
為什麼叫做P與NP？
當委派給計算機一項任務時，計算機算法需要一定的時間來解決它。那麼，如何理解一個算法解決問題需要花費的時間呢？舉個例子，假設你有一個未經排序的數字列表，你想寫一個算法來找出其中最大的數。這個算法必須查看列表中的所有數字，這是無法避免的。但是，如果它只是記錄到目前為止看到的最大數字，那麼每個數字只需被查看一次。因此，算法的執行時間與它處理的單元數量成正比——計算機科學家稱其為N。
由於有些算法的效率會比其他的算法效率更高或更低，所以它們完成的時間可能與N、N²、N³……有關。其中的關鍵在於指數是一個常量——1、2、3等等。在這種情況下，算法被稱為在是
多項式時間內完成的，或簡稱為P。如果一個問題可以找到一個能在多項式的時間裡解決它的算法，那麼這個問題就屬於P類問題。（需要說明的是，一個對P類問題的常見誤解是以為它們都是能很快解決的問題，但其實，P類問題有可能是天荒地老都無法解出的問題。）但可惜的是，並不是所有的問題都這樣。一些問題的解決需要花費的時間正比於2ᴺ、3ᴺ……在這種情況下，N是指數，這意味著算法要處理的每個單元的複雜度都呈指數級增長。在這種情況下，算法可以在指數時間內完成，或簡稱為NP（它實際上意為不確定性多項式時間）。
這二者之間可以有非常巨大的差別。舉個例子，假如一個有100個單元的P算法，它完成工作的時間長度正比於N³，解決問題所需的時間大約是3小時；但如果它是一個NP算法，完成任務的時間與2ᴺ成正比，那麼它花費的時間可以達到約3億億年。
重要之處
問題“P是否等於NP”的另一種問法是，每一個困難問題是否都包含一個簡單但隱藏的解。這兩種類型的問題是否不可避免地彼此分離？是否一些問題的本質就是複雜的？
如果P確實等於NP，那麼它對我們的生活將產生重大影響。一個主要的好處是，許多NP問題被稱為NP完全問題，這意味著它們的解可以迅速適用於任何其他NP完全問題。因此，找到一種快速解決一個NP完全問題的方法，將在解決所有其他NP完全問題方面取得重大進展。
有哪些例子是NP問題呢？有一個主要問題是許多研究人員的關注焦點。現代密碼學主要依賴於難以破解但易於被檢查的代碼，比如你的帳戶密碼：檢查它們是否正確是很簡單的，但是要靠蠻力硬猜每一個字母和數字的排列就要花費很長很長的時間。在網上訂購商品時保護信用卡號碼背後的加密技術也是NP加密技術的一個例子。如果P = NP，那麼可能幾乎所有加密的破解都會突然變得非常容易。
雖然如果P = NP成立的話，我們將失去表面上的互聯網安全，造成損失慘重的後果，但它也將產生許多有益的後果。計算機科學家Lance Fortnow在一篇文章中歸納總結了一部分重要的結果：
各種形式的運輸方式的調度將被優化，從而能提供更快、更便宜的物流與交通。製造商可以提高生產力，減少浪費。我在這裡所說的還只觸及了一些表面問題。通過奧卡姆剃刀原理，學習將變得很容易——我們只需找到與數據一致的最小程序。近乎完美的視覺識別、語言理解和翻譯等一切學習任務都變得顯而易見。我們還能更好地預測天氣、地震和其他自然現象。P是否等於NP是非常基本的問題，能因其而得到巨大改善的任務數不甚數。例如，從蛋白質的氨基酸序列來預測蛋白質的結構將變得非常容易，這對藥物設計和生物技術來說是一個重要里程碑。另一個常被提到的NP問題是，如何確定計算機芯片上最有效的晶體管佈局，從而能顯著提高計算能力。
事實上，證明P = NP會使幾乎對所有其他數學問題的求解都變得更加容易。如果P = NP最終得到證明，將會徹底顛覆當前社會的技術和經濟基礎。這個問題的解決很有可能成為一個比互聯網的發明意義更重大的創新推動。
科學共識
不過，大多數計算機科學家並不相信P=NP 。根據2001年的一項調查顯示，有61%的人相信P≠NP；而2012年的調查則顯示，相信P≠NP的人達到了83%。要真的證明P ≠ NP是非常困難的，但是所有證明P = NP的嘗試都失敗了，這表明這兩類問題是互不相容的。麻省理工學院的科學家Scott Aronson寫過一篇博文，列出了P ≠ NP的10個原因，其中第9條提出了這樣一個論據，既有力地反駁了P = NP的觀點，又簡潔地描述了假如P = NP成立的結果：
如果P=NP，那麼世界將與我們通常所認為的完全不同。“創造性的飛躍”將沒有特殊價值；一旦找到問題的解，那麼在解決問題與認可解決方案之間沒有根本間隔。任何能欣賞交響樂的人都是莫扎特，每個能一步一步論證的人都是高斯，每個能認識到好的投資策略的人都是巴菲特。https://bigthink.com/technology-innovation/what-is-p-vs-np?rebelltitem=5#rebelltitem5
http://news.mit.edu/2009/explainer-pnp
https://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext
https://www.scottaaronson.com/blog/?p=122
http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf
閱讀更多 原理 的文章
