後端技術指南針
1 前言
今天和大家一起了解個高能知識點：P=NP問題。
看到這裡我們可能是一頭霧水，不由得發問：
- P問題是什麼？
- NP問題又是什麼？
- P=NP又是什麼意思？
- 研究并解決P=NP問題的意義是什麼？
這四個問題也是我們由表及裡去了解P=NP問題的重要切入點，通過本文你将了解到包括但不限于以下内容：
- 千禧年世紀難題
- P類問題和NP類問題特征定義
- P=NP的研究和NPC問題
- 解決P=NP問題的大方向
2 千禧年世紀難題
時間鏡頭拉回2000年數學界出現了一個裡程碑事件：千禧年大獎難題
千禧年大獎難題 Millennium Prize Problems 是七個由美國克雷數學研究所 Clay Mathematics Institute 于2000年5月24日公布的數學難題。根據克雷數學研究所訂定的規則，所有難題的解答必須發表在數學期刊上，并經過各方驗證，隻要通過兩年驗證期，每解破一題的解答者，會頒發獎金100萬美元。
這些難題是呼應1900年德國數學家大衛·希爾伯特在巴黎提出的23個曆史性數學難題，經過一百年，許多難題已獲得解答。而千禧年大獎難題的破解，極有可能為密碼學以及航天、通訊等領域帶來突破性進展。
大概意思就是2000年5月美國的一個私人非盈利機構出了7個意義重大的問題，解答任何1道會得到100w美元獎金，說到錢忽然精神起來了，不妨看下這7個多金的題目：
- P/NP問題（P versus NP）
- 霍奇猜想（The Hodge Conjecture）
- 龐加萊猜想（The Poincaré Conjecture）
- 黎曼猜想（The Riemann Hypothesis）
- 楊-米爾斯存在性與品質間隙（Yang-Mills Existence and Mass Gap）
- 納維-斯托克斯存在性與光滑性（Navier-Stokes existence and smoothness)
- 貝赫和斯維讷通-戴爾猜想（The Birch and Swinnerton-Dyer Conjecture）
黎曼猜想去年鬧得沸沸揚揚，相信都有所耳聞，不過黎曼猜想是研究素數分布規律的問題，相比之下P=NP問題和計算機領域的關系更為密切，是以P=NP問題被認為是理論計算機和數學領域的綜合問題，該問題的研究成果将對計算機領域和現實生活帶來巨大的影響。
如克雷數學研究所的約定隻要證明或者證僞P=NP問題即可赢取100w美元獎金，其實相比P=NP問題的證明或證否的影響和意義，100w獎金隻是皇冠上的一粒塵埃而已。
前面鋪墊了一些賣了個關子，快馬加鞭一起先來看下 P和NP，到底是個怎樣的問題？
3 P類和NP類問題特征
我在克雷數學研究所官網找到了關于 P和NP問題 的簡單說明：
簡單意譯一下：
假設你正在為400名大學生組織住宿，但是空間有限隻有100名學生能在宿舍裡找到位置。更複雜的是還給了你一份不相容學生的名單，并要求在你的最終選擇中不要出現這份名單中的任何一對。
這是計算機科學家稱之為NP問題的一個例子，因為很容易檢查一個同僚提出的一百個學生的給定選擇是否令人滿意，然而從頭開始生成這樣一個清單的任務似乎太難了以至于完全不切實際。
事實上從400名申請者中選擇100名學生的方法總數比已知宇宙中的原子數量還要多！這類其答案可以被快速檢查，但是通過任何直接的程式需要不可接受長度的時間來解決，比如300年或者更多...
斯蒂芬·庫克和列昂尼德·萊文在1971年獨立地提出了P(即容易找到)和NP(即容易檢查)問題。
P和NP問題是斯蒂芬·庫克和列昂尼德·萊文在1971年提出的，從上文的描述中大概知道了P問題和NP問題的主要特征：
P 問題(easy to find)
all problems solvable, deterministically, in polynomial time
譯：多項式時間内可解決的問題(當然在多項式時間是可驗證的)
NP 問題(esay to check)
non-deterministic Polynomial time
譯：非确定性多項式時間可解決的問題
舉幾個例子來加深印象：
計算1-1000的連續整數之和：這個問題就比較簡單，無論是程式設計還是使用高斯求和公式都可以在有限可接受的時間内完成，這種算是P類問題。
計算地球上所有原子個數之和：這個問題就很困難甚至無解，但是現在有個答案是300個，顯然是錯的，是以很容易驗證但不容易求解，這種算NP類問題。
看到這裡我們get了一個非常重要的概念(敲黑闆劃重點)：P類問題是可以在多項式時間内解決并驗證的一類問題，NP類問題是可以多項式時間驗證但是不确定能否在多項式時間内解決的一類問題。
等等！讓我捋一捋，前面一直說 多項式時間 ，那麼到底啥樣的時間是多項式時間呢？
4 多項式時間
其實多項式時間的概念我們還是很熟悉的，在做算法題或者日常工作時我們都會說，這個解法的時間複雜度是O(n^2)性能不是很好，那個解法的時間複雜度是O(nlogn)(注:計算機中的log一般指底數=2)還可以。
這裡的大O就是時間複雜度的表示法，看到這裡仿佛清晰一些了，不過還是看下多項式表達：
多項式的概念我們在國小國中的時候就開始接觸了，對于計算機來說有更特别的含義，我們都知道算法時間複雜度的大O表示法，取表達式中的最高次其他項忽略，因為随着輸入規模的增大最高次的影響最大，對計算機來說可以做這樣的近似處理，比如上面的多項式表達式可以了解為O(n^k)的複雜度。
這個世界并不是隻有多項式時間這麼簡單，我們還知道有指數函數形如2^n這個計算量已經非常可怕，更不要說n^n和n!這種問題了。
對于計算機而言，它不知道問題難不難，對它而言就是拆解成非常多的步驟去執行，去衡量計算機認為難或者不難或許可以從其執行時間來看，在排除代碼實作差異來說，執行時間越長的問題通常都會比較難。
我們通常将多項式時間看作是計算機解決問題的分水嶺，因為超過多項式時間之後時間消耗上就不太好接受了。
直覺感受一下，随着不同輸入規模下，多項式時間和非多項式時間的時間消耗曲線差異吧：
圖檔來自網絡：複雜度對比
看到這裡恍然大悟，多項式時間内可解決的意義所在。
回過頭看看NP問題是non-deterministic Polynomial time，也就是NP問題能否在多項式時間内解決存在不确定性。
也就是說很多NP類問題如果無法在多項式時間内解決，那麼于我們目前的計算能力而言是幾乎無解的，量子計算機目前還處于初級階段，或許若幹年後這些問題對于量子計算機而言是可以接受的...
或許你會問像超級計算機這種能行嗎？我們從時間增長曲線來看，問題規模擴大一點點，我們需要的算力就是更大倍數的增加，這樣堆砌機器不是好辦法，我們最好寄托于其他解決思路。
看到這裡聰明的讀者會不由感歎：要是把NP問題轉化到多項式時間内解決，那将是多麼的進步啊！如果你已經開始有這個想法了，那也就開始深入 P=NP 的腹地了，我們繼續前進~
等等！我們一直在提 NP 類問題，聽着這列問題還挺有意義并且很難，能不能舉幾個現實的 NP 問題的例子呢？這個問題很好呀！我們來看看現實中的 NP 問題吧。
5 現實中的NP類問題
其實作實中的 NP 類問題非常多，并且很多都有非常重要的意義，舉幾個大家耳熟能詳的例子，比如旅行商問題(又稱旅行推銷員問題)。
先來看下旅行商問題 TSP 的定義：
旅行推銷員問題 Travelling salesman problem是這樣一個問題：給定一系列城市和每對城市之間的距離，求解通路每一座城市一次并回到起始城市的最短回路。它是組合優化中的一個NP難問題，在運籌學和理論計算機科學中非常重要。
最早的旅行商問題的數學規劃是由 Dantzig（1959）等人提出，并且是在最優化領域中進行了深入研究。許多優化方法都用它作為一個測試基準。盡管問題在計算上很困難，但已經有了大量的啟發式算法和精确方法來求解數量上萬的執行個體，并且能将誤差控制在1%内。
圖檔來自網絡：旅行商問題地圖示意圖
我們都知道在城市規模比較小時比如3個/5個 我們可以進行窮舉來确定最優的路線，但是經過幾次窮舉我們發現窮舉複雜度是O(n!)。
啊呀！O(n!)太大了，在 n=100 時，那麼有多大呢？
啊呀！這麼大，但是好像你還覺得不直覺，那麼來看看宇宙的原子數有多大吧：
知乎問題：為什麼說宇宙原子總數差不多是10的80次方？https://www.zhihu.com/question/63852727
這個數字是按照宇宙中星系數量、每個星系恒星數量、每個恒星品質等角度結合原子品質進行的估算，數量級上有一些誤差，但是遠小于100的階乘，這裡我們深深感受了指數級膨脹的威力。
是以當TSP問題的輸入規模在100時，如果仍然進行窮舉的話，計算量将無效大，天荒地老滄海桑田那種...
NP問題不僅存在于運籌學，在醫學領域的蛋白質折疊問題也屬于NP問題，該問題對研究癌症、阿爾茲海默症、帕金森症等都有非常重大的現實意義。
是以對于NP類問題的現實影響意義我們不用質疑，充分認識到這類問題的研究價值所在是我們進步的源動力。
畫外音：清華大學2016年大學特等獎獲得者95後陳立傑，無敵超神的傳奇人物在特獎答辯時提到希望在自己有生之年看到p=np問題被解決，知乎上有答辯視訊，超贊感興趣可前往觀看，是以p=np問題可以說是全世界最聰明的那撥人魂牽夢繞的問題了。
了解了NP類問題的現實意義之後，看看全世界的學者都做了哪些研究，取得了哪些進展。
6 大突破之NPC問題
從特征上看，我們可以知道P類問題屬于NP問題，因為P類問題屬于NP類問題中可在多項式時間驗證并解決的問題，可以簡單認為P類問題屬于特例最基本簡單的NP問題。
P類問題是在我們目前能力範圍内的，但是NP類問題要尋找最優解可能超越多項式時間，我們知道P類問題屬于NP類問題。那麼NP類問題是否可以歸類為P類問題呢？
好了，截止到這裡我們終于引出了 P=NP 問題在表達什麼：是否所有NP類問題都可以在多項式時間内解決并驗證，也就是轉化為P類問題。
雖然目前 P=NP 問題還沒有被證明或者證僞，但是經過多年的研究，學術界的一個方向性的共識是 P=NP 問題應該是不成立的，換句話說就是至少存在一個 NP類問題是無法在多項式時間内解決的。
不由得問為什麼會有這個不成立的傾向呢？因為很多學者做了很多研究之後，雖然沒有解決問題，但是仍然取到了很大的進步提供了研究方向：NPC問題的發現。
俗語有雲：射人先射馬 擒賊先擒王。沒錯，NPC類就是NP類問題的王。
NPC問題Non-deterministic Polynomial complete problem又稱NP完全問題，NP問題就是大量的NP問題經過歸約化而發現的終極bossNP問題。
等等...歸約化是嘛意思...
我在搜尋了一些定義，感覺不是很好後來看到 CMU 的一個課件，雖然是英文的，但是表達的比較清晰一起看下(以下圖檔均來自下述連結)：
【推薦】關于歸約化的和npc問題的解釋：https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/npcomplete.pdf
課件裡的解釋還是很通俗的，其中注意一個詞彙Reductions，這個單詞是Reduce的名詞，reduce是減少的意思，是以我們大緻猜測到歸約化的意思了。
歸約化是解決複雜問題的一種思路工具，課件中展示了将問題Y歸約化到問題X的過程，其中提到了多項式歸約，如果我們找到了問題X的多項式時間解法，那麼我們有理由相信問題Y同樣可以找到多項式時間解法。
歸約化具備傳遞性：問題A可歸約為問題B，問題B可歸約為問題C，那麼問題A可歸約為問題C，正是基于這個特性我們才能把很多小的NP類問題串起來，最終出現NPC問題。
相比而言問題X比問題Y更難也更普遍，回到NP問題上來說，NP問題的歸約化就是去尋找一個終極NP問題，這個問題更普遍更難但是可以cover很多小範圍的NP問題，這類終極NP問題就是 NP完全問題。
課件中也給出了 NPC問題的基本定義：
是以 NPC 問題是研究的重點，其實 TSP 問題就是一個 NPC 問題，這裡簡單翻譯下課件給出 NPC問題的兩個基本特征定義：
- NPC問題屬于NP問題
- 對于所有NP問題都可以歸約化到它
先注意下這個定義，後面會用到，因為還有一類更複雜的問題...
寫到這裡如果你還在看，那就值得給你點個贊，因為P=NP的話題相比具體的技術點更晦澀，筆者也是在B站在谷歌看了許多資料之後才稍微清晰一些的，是以沒看懂沒關系，多看幾遍就好了。
事情到這裡就結束了嗎？并沒有...
7 NP-Hard問題
前面我知道了NPC問題，但是仍然有一部分特别的問題稱為NPH問題。
NP-Hard問題是滿足NPC問題定義的第二條，但不滿足第一條，也就是說所有NP問題可以歸約化到NPH問題，但是HP-Hard問題不一定是NP問題，是以NPH問題比NPC問題更難。
NPH問題比NPC問題難了解一些，看個回答：
NP-Complete VS NP-Hard https://stackoverflow.com/questions/20523578/np-complete-vs-np-hard
圖檔來自網絡：NPH問題的特征
截止到這裡，該說的基本上都說了，再回到最初的問題P=NP是否成立呢？如果成立或者不成立，問題的集合該是怎麼樣的呢？
維基百科給出了在P=NP成立和不成立情況下的集合關系，如圖(敲黑闆劃重點)：
寫在最後
本文也是筆者不熟悉但是還比較感興趣的領域，最近一周花了一些時間去看這個話題，其中在B站的媽咪說和遇見數學的科普介紹很不錯，在觀看過程中也是反複看，但是對于其中細緻的問題也捉襟見肘，是以文章可能存在問題，如果讀者是這方面的大神可以直接私信我提出，我們一起看下。
最後還是想感歎幾句吧，在寫作過程中我不斷想起大劉三體中的水滴，地球人枕戈待旦地準備迎接三體艦隊，但是一個水滴就幾乎讓地球艦隊全軍覆沒，水滴的神奇讓我們感受到了渺小。
巨人的肩膀
- http://www.matrix67.com/blog/archives/105
- https://www.zhihu.com/question/63852727
- https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/npcomplete.pdf
- https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_np_hard_complete_classes.htm
- https://stackoverflow.com/questions/20523578/np-complete-vs-np-hard