我昨天無意中的吐槽有十萬多盒友瀏覽，密碼學真經不起驚嚇，感覺大家對NP和P不是很瞭解，今天正好藉著這個機會介紹一下。
在介紹之前，首先需要引入算法複雜度的定義，什麼是算法複雜度，就是計算一個算法所需要的時間級別，也是衡量算法好壞的重要標準。
比如，我們我們設計一個相當簡單的算法，豎式加法，如果兩個數字都要n位，那麼它們做加法就要做n次，算法複雜度就是O(N)。
如果是乘法，n位數乘m位數，需要做m*m次運算，複雜度就是O(MN)
即算法的執行時間可以用問題的規模表示，當問題複雜度公式不同時，運算時間差別很大。下圖就是不同複雜度算法隨問題規模擴大時運行時間的變化：
下面我們把複雜度分成兩個大類，多項式級和指數級，多項式級就是說複雜度公式可以表示成n的多項式的模數，不管n的階數多大，都算多項式級，比如O(N^100)，即n的一百次方，普遍觀點認為，這個量級即使很巨大，但遲早會被窮盡，就像Intel的創始人摩爾提出的摩爾定律，集成電路上可容納的元器件的數目，約每隔18-24個月便會增加一倍，性能也將提升一倍。所以多項式級都是可以接受的複雜度。
但是與之對應的是第二類，即指數級的，如O(2^N)，看上去好像比之前的O(N^100）小好多，但是事實上如果N足夠大，指數增長的速度要遠大於高階多項式，且這個增長速度是不可接受的，算一輩子都算不完
明白了複雜度，接下來就可以引入 P 問題和 NP 問題，所謂的P 問題就是能夠在多項式的時間複雜度內解決的問題，這裡的 P 指的是多項式時間（polynomial time），對於那些不能在多項式的時間複雜度內解決的問題，比如說揹包問題，分配問題等等，我們會認為這個問題很難，可能需要在指數或階乘的時間複雜度內解決（之所以不把話說滿是因為萬一有人找到快速解法了呢），但是如果我們能夠在多項式的時間複雜度內驗證一個答案是否正確，我們就把這類問題稱為 NP 問題，其中 NP 表示不確定的多項式時間（non-deterministic polynomial time）。簡單來說就是解決 NP 問題很難，但驗證它卻很容易。打個比方，數獨是一個解決起來比較難的問題，但是如果我們往格子裡隨機填一些數字，然後驗證它是否滿足數獨的規則就會比較容易。因此，這類問題也是科學家們最關心的問題。
為了分析NP問題，有人發明了規約，所謂規約，就是問題A不會比問題B更難，那麼B可以規約到A，如果解決了B，那麼A也可以被解決。
那麼問題來了，規約過後的 NP 問題能否在多項式的複雜度內解決呢？換句話說，P 問題和 NP 問題是否等價。如果 P = NP ，就意味著任何能夠在多項式的複雜度驗證的問題也能夠在多項式的複雜度解決它！
它的意義何在呢？意義肯定是具有兩面性。
首先是好處：由於很多 NP 問題難以在多項式複雜度內解決，而若 P = NP，就意味著可以把 NP 問題轉換為 P 問題，這樣一來，很多當前覺得困難的問題就能輕易被解決。比如在圍棋方面會有終極解法，生物領域能輕鬆破解遺傳密碼並隨意操縱基因序列，很多數學猜想也可以藉助計算機進行演算推導，許多難題都能迎刃而解。
但隨之而來也有壞處：由於所有公鑰密碼學都基於NP不等於P的假設，所有公鑰加密和簽名認證算法會徹底失效，你的銀行卡，社交賬號變得不再安全，黑客能夠輕鬆進入你的電腦，我們都將沒有秘密可言；比特幣，區塊鏈這些基於密碼學的大熱領域將完全崩塌，你可以輕鬆挖幾百萬個比特幣，不過到時候它們將毫無價值。
最嚴重的是，我畢業就要失業（密碼學專業學生太慘了）
不過話說回來，目前學界大部分都傾向於NP不等於P，且這個千禧年七大難題之一沒那麼容易被證明，至於文章開頭那個宣稱證明NP=P的天才少年？如果他的證明是對的，中科院院長都得他來當。
參考：
一文理解NP完全理論，NP問題，NPC問題-騰訊雲開發者社區-騰訊雲 (tencent.com)
P問題、NP問題、NP完全問題和NP難問題 - 知乎 (zhihu.com)
怎麼理解 P 問題和 NP 問題？ - 知乎 (zhihu.com)