1 前言

今天和大家一起了解個高能知識點：P=NP問題。

看到這里我們可能是一頭霧水，不由得發(fā)問：

• P問題是什么？
• NP問題又是什么？
• P=NP又是什么意思？
• 研究并解決P=NP問題的意義是什么？

這四個問題也是我們由表及里去理解P=NP問題的重要切入點，通過本文你將了解到包括但不限于以下內(nèi)容：

• 千禧年世紀難題
• P類問題和NP類問題特征定義
  
• P=NP的研究和NPC問題
  
• 解決P=NP問題的大方向

2 千禧年世紀難題

時間鏡頭拉回2000年數(shù)學(xué)界出現(xiàn)了一個里程碑事件：千禧年大獎難題

千禧年大獎難題 Millennium Prize Problems 是七個由美國克雷數(shù)學(xué)研究所 Clay Mathematics Institute 于2000年5月24日公布的數(shù)學(xué)難題。根據(jù)克雷數(shù)學(xué)研究所訂定的規(guī)則，所有難題的解答必須發(fā)表在數(shù)學(xué)期刊上，并經(jīng)過各方驗證，只要通過兩年驗證期，每解破一題的解答者，會頒發(fā)獎金100萬美元。 

這些難題是呼應(yīng)1900年德國數(shù)學(xué)家大衛(wèi)·希爾伯特在巴黎提出的23個歷史性數(shù)學(xué)難題，經(jīng)過一百年，許多難題已獲得解答。而千禧年大獎難題的破解，極有可能為密碼學(xué)以及航天、通訊等領(lǐng)域帶來突破性進展。

大概意思就是2000年5月美國的一個私人非盈利機構(gòu)出了7個意義重大的問題，解答任何1道會得到100w美元獎金，說到錢忽然精神起來了，不妨看下這7個多金的題目：

• P/NP問題 （P versus NP）
• 霍奇猜想 （The Hodge Conjecture）
• 龐加萊猜想 （The Poincaré Conjecture）
• 黎曼猜想 （The Riemann Hypothesis）
• 楊-米爾斯存在性與質(zhì)量間隙（Yang-Mills Existence and Mass Gap）
• 納維-斯托克斯存在性與光滑性（Navier-Stokes existence and smoothness)
• 貝赫和斯維訥通-戴爾猜想（The Birch and Swinnerton-Dyer Conjecture）

黎曼猜想去年鬧得沸沸揚揚，相信都有所耳聞，不過黎曼猜想是研究素數(shù)分布規(guī)律的問題，相比之下P=NP問題和計算機領(lǐng)域的關(guān)系更為密切，所以P=NP問題被認為是理論計算機和數(shù)學(xué)領(lǐng)域的綜合問題，該問題的研究成果將對計算機領(lǐng)域和現(xiàn)實生活帶來巨大的影響。

如克雷數(shù)學(xué)研究所的約定只要證明或者證偽P=NP問題即可贏取100w美元獎金，其實相比P=NP問題的證明或證否的影響和意義，100w獎金只是皇冠上的一粒塵埃而已。

前面鋪墊了一些賣了個關(guān)子，快馬加鞭一起先來看下 P和NP，到底是個怎樣的問題？

3 P類和NP類問題特征

我在克雷數(shù)學(xué)研究所官網(wǎng)找到了關(guān)于 P和NP問題 的簡單說明：

簡單意譯一下：

假設(shè)你正在為400名大學(xué)生組織住宿，但是空間有限只有100名學(xué)生能在宿舍里找到位置。更復(fù)雜的是還給了你一份不相容學(xué)生的名單，并要求在你的最終選擇中不要出現(xiàn)這份名單中的任何一對。

這是計算機科學(xué)家稱之為NP問題的一個例子，因為很容易檢查一個同事提出的一百個學(xué)生的給定選擇是否令人滿意，然而從頭開始生成這樣一個列表的任務(wù)似乎太難了以至于完全不切實際。

事實上從400名申請者中選擇100名學(xué)生的方法總數(shù)比已知宇宙中的原子數(shù)量還要多！這類其答案可以被快速檢查，但是通過任何直接的程序需要不可接受長度的時間來解決，比如300年或者更多...

斯蒂芬·庫克和列昂尼德·萊文在1971年獨立地提出了P(即容易找到)和NP(即容易檢查)問題。

P和NP問題是斯蒂芬·庫克和列昂尼德·萊文在1971年提出的，從上文的描述中大概知道了P問題和NP問題的主要特征：

P 問題(easy to find)

all problems solvable, deterministically, in polynomial time
譯：多項式時間內(nèi)可解決的問題(當(dāng)然在多項式時間是可驗證的)

NP 問題(esay to check)

non-deterministic Polynomial time
譯：非確定性多項式時間可解決的問題

舉幾個例子來加深印象：

計算1-1000的連續(xù)整數(shù)之和：這個問題就比較簡單，無論是編程還是使用高斯求和公式都可以在有限可接受的時間內(nèi)完成，這種算是P類問題。

計算地球上所有原子個數(shù)之和：這個問題就很困難甚至無解，但是現(xiàn)在有個答案是300個，顯然是錯的，所以很容易驗證但不容易求解，這種算NP類問題。

看到這里我們get了一個非常重要的概念(敲黑板劃重點)：P類問題是可以在多項式時間內(nèi)解決并驗證的一類問題，NP類問題是可以多項式時間驗證但是不確定能否在多項式時間內(nèi)解決的一類問題。

等等！讓我捋一捋，前面一直說 多項式時間 ，那么到底啥樣的時間是多項式時間呢？

4 多項式時間

其實多項式時間的概念我們還是很熟悉的，在做算法題或者日常工作時我們都會說，這個解法的時間復(fù)雜度是O(n^2)性能不是很好，那個解法的時間復(fù)雜度是O(nlogn)(注:計算機中的log一般指底數(shù)=2)還可以。

這里的大O就是時間復(fù)雜度的表示法，看到這里仿佛清晰一些了，不過還是看下多項式表達：

多項式的概念我們在小學(xué)初中的時候就開始接觸了，對于計算機來說有更特別的含義，我們都知道算法時間復(fù)雜度的大O表示法，取表達式中的最高次其他項忽略，因為隨著輸入規(guī)模的增大最高次的影響最大，對計算機來說可以做這樣的近似處理，比如上面的多項式表達式可以理解為O(n^k)的復(fù)雜度。

這個世界并不是只有多項式時間這么簡單，我們還知道有指數(shù)函數(shù)形如2^n這個計算量已經(jīng)非?？膳拢灰fn^n和n!這種問題了。

對于計算機而言，它不知道問題難不難，對它而言就是拆解成非常多的步驟去執(zhí)行，去衡量計算機認為難或者不難或許可以從其執(zhí)行時間來看，在排除代碼實現(xiàn)差異來說，執(zhí)行時間越長的問題通常都會比較難。

我們通常將多項式時間看作是計算機解決問題的分水嶺，因為超過多項式時間之后時間消耗上就不太好接受了。

直觀感受一下，隨著不同輸入規(guī)模下，多項式時間和非多項式時間的時間消耗曲線差異吧：

圖片來自網(wǎng)絡(luò)：復(fù)雜度對比

看到這里恍然大悟，多項式時間內(nèi)可解決的意義所在。

回過頭看看NP問題是non-deterministic Polynomial time，也就是NP問題能否在多項式時間內(nèi)解決存在不確定性。

也就是說很多NP類問題如果無法在多項式時間內(nèi)解決，那么于我們當(dāng)前的計算能力而言是幾乎無解的，量子計算機目前還處于初級階段，或許若干年后這些問題對于量子計算機而言是可以接受的...

或許你會問像超級計算機這種能行嗎？我們從時間增長曲線來看，問題規(guī)模擴大一點點，我們需要的算力就是更大倍數(shù)的增加，這樣堆砌機器不是好辦法，我們最好寄托于其他解決思路。

看到這里聰明的讀者會不由感嘆：要是把NP問題轉(zhuǎn)化到多項式時間內(nèi)解決，那將是多么的進步啊！如果你已經(jīng)開始有這個想法了，那也就開始深入 P=NP 的腹地了，我們繼續(xù)前進~

等等！我們一直在提 NP 類問題，聽著這列問題還挺有意義并且很難，能不能舉幾個現(xiàn)實的 NP 問題的例子呢？這個問題很好呀！我們來看看現(xiàn)實中的 NP 問題吧。

5 現(xiàn)實中的NP類問題

其實現(xiàn)實中的 NP 類問題非常多，并且很多都有非常重要的意義，舉幾個大家耳熟能詳?shù)睦?，比?span style="color: rgb(255, 41, 65);">旅行商問題(又稱旅行推銷員問題)。

先來看下旅行商問題 TSP 的定義：

旅行推銷員問題 Travelling salesman problem是這樣一個問題：給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次并回到起始城市的最短回路。它是組合優(yōu)化中的一個NP難問題，在運籌學(xué)和理論計算機科學(xué)中非常重要。

最早的旅行商問題的數(shù)學(xué)規(guī)劃是由 Dantzig（1959）等人提出，并且是在最優(yōu)化領(lǐng)域中進行了深入研究。許多優(yōu)化方法都用它作為一個測試基準。盡管問題在計算上很困難，但已經(jīng)有了大量的啟發(fā)式算法和精確方法來求解數(shù)量上萬的實例，并且能將誤差控制在1%內(nèi)。

圖片來自網(wǎng)絡(luò)：旅行商問題地圖示意圖

我們都知道在城市規(guī)模比較小時比如3個/5個 我們可以進行窮舉來確定最優(yōu)的路線，但是經(jīng)過幾次窮舉我們發(fā)現(xiàn)窮舉復(fù)雜度是O(n!)。

啊呀！O(n!)太大了，在 n=100 時，那么有多大呢？

啊呀！這么大，但是好像你還覺得不直觀，那么來看看宇宙的原子數(shù)有多大吧：

知乎問題：為什么說宇宙原子總數(shù)差不多是10的80次方？https://www.zhihu.com/question/63852727

這個數(shù)字是按照宇宙中星系數(shù)量、每個星系恒星數(shù)量、每個恒星質(zhì)量等角度結(jié)合原子質(zhì)量進行的估算，數(shù)量級上有一些誤差，但是遠小于100的階乘，這里我們深深感受了指數(shù)級膨脹的威力。

所以當(dāng)TSP問題的輸入規(guī)模在100時，如果仍然進行窮舉的話，計算量將無效大，天荒地老滄海桑田那種...

NP問題不僅存在于運籌學(xué)，在醫(yī)學(xué)領(lǐng)域的蛋白質(zhì)折疊問題也屬于NP問題，該問題對研究癌癥、阿爾茲海默癥、帕金森癥等都有非常重大的現(xiàn)實意義。

所以對于NP類問題的現(xiàn)實影響意義我們不用質(zhì)疑，充分認識到這類問題的研究價值所在是我們進步的源動力。

畫外音：清華大學(xué)2016年本科特等獎獲得者95后陳立杰，無敵超神的傳奇人物在特獎答辯時提到希望在自己有生之年看到p=np問題被解決，知乎上有答辯視頻，超贊感興趣可前往觀看，所以p=np問題可以說是全世界最聰明的那撥人魂牽夢繞的問題了。

了解了NP類問題的現(xiàn)實意義之后，看看全世界的學(xué)者都做了哪些研究，取得了哪些進展。

6 大突破之NPC問題

從特征上看，我們可以知道P類問題屬于NP問題，因為P類問題屬于NP類問題中可在多項式時間驗證并解決的問題，可以簡單認為P類問題屬于特例最基本簡單的NP問題。

P類問題是在我們目前能力范圍內(nèi)的，但是NP類問題要尋找最優(yōu)解可能超越多項式時間，我們知道P類問題屬于NP類問題。那么NP類問題是否可以歸類為P類問題呢？

好了，截止到這里我們終于引出了 P=NP 問題在表達什么：是否所有NP類問題都可以在多項式時間內(nèi)解決并驗證，也就是轉(zhuǎn)化為P類問題。

雖然目前 P=NP 問題還沒有被證明或者證偽，但是經(jīng)過多年的研究，學(xué)術(shù)界的一個方向性的共識是 P=NP 問題應(yīng)該是不成立的，換句話說就是至少存在一個 NP類問題是無法在多項式時間內(nèi)解決的。

不由得問為什么會有這個不成立的傾向呢？因為很多學(xué)者做了很多研究之后，雖然沒有解決問題，但是仍然取到了很大的進步提供了研究方向：NPC問題的發(fā)現(xiàn)。

俗語有云：射人先射馬 擒賊先擒王。沒錯，NPC類就是NP類問題的王。

NPC問題Non-deterministic Polynomial complete problem又稱NP完全問題，NP問題就是大量的NP問題經(jīng)過歸約化而發(fā)現(xiàn)的終極bossNP問題。

等等...歸約化是嘛意思...

我在搜索了一些定義，感覺不是很好后來看到 CMU 的一個課件，雖然是英文的，但是表達的比較清晰一起看下(以下圖片均來自下述鏈接)：

【推薦】關(guān)于歸約化的和npc問題的解釋：https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/npcomplete.pdf

課件里的解釋還是很通俗的，其中注意一個詞匯Reductions，這個單詞是Reduce的名詞，reduce是減少的意思，所以我們大致猜測到歸約化的意思了。

歸約化是解決復(fù)雜問題的一種思路工具，課件中展示了將問題Y歸約化到問題X的過程，其中提到了多項式歸約，如果我們找到了問題X的多項式時間解法，那么我們有理由相信問題Y同樣可以找到多項式時間解法。

歸約化具備傳遞性：問題A可歸約為問題B，問題B可歸約為問題C，那么問題A可歸約為問題C，正是基于這個特性我們才能把很多小的NP類問題串起來，最終出現(xiàn)NPC問題。

相比而言問題X比問題Y更難也更普遍，回到NP問題上來說，NP問題的歸約化就是去尋找一個終極NP問題，這個問題更普遍更難但是可以cover很多小范圍的NP問題，這類終極NP問題就是 NP完全問題。

課件中也給出了 NPC問題的基本定義：

所以 NPC 問題是研究的重點，其實 TSP 問題就是一個 NPC 問題，這里簡單翻譯下課件給出 NPC問題的兩個基本特征定義：

• NPC問題屬于NP問題
• 對于所有NP問題都可以歸約化到它

先注意下這個定義，后面會用到，因為還有一類更復(fù)雜的問題...

寫到這里如果你還在看，那就值得給你點個贊，因為P=NP的話題相比具體的技術(shù)點更晦澀，筆者也是在B站在谷歌看了許多資料之后才稍微清晰一些的，所以沒看懂沒關(guān)系，多看幾遍就好了。

事情到這里就結(jié)束了嗎？并沒有...

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

圖片來自網(wǎng)絡(luò)：NPH問題的特征

截止到這里，該說的基本上都說了，再回到最初的問題P=NP是否成立呢？如果成立或者不成立，問題的集合該是怎么樣的呢？

維基百科給出了在P=NP成立和不成立情況下的集合關(guān)系，如圖(敲黑板劃重點)：

寫在最后

本文也是筆者不熟悉但是還比較感興趣的領(lǐng)域，最近一周花了一些時間去看這個話題，其中在B站的媽咪說和遇見數(shù)學(xué)的科普介紹很不錯，在觀看過程中也是反復(fù)看，但是對于其中細致的問題也捉襟見肘，因此文章可能存在問題，如果讀者是這方面的大神可以直接私信我提出，我們一起看下。

最后還是想感嘆幾句吧，在寫作過程中我不斷想起大劉三體中的水滴，地球人枕戈待旦地準備迎接三體艦隊，但是一個水滴就幾乎讓地球艦隊全軍覆沒，水滴的神奇讓我們感受到了渺小。

科幻還是未來，取決于現(xiàn)在，最后依然感謝各位讀者的傾情閱讀，完結(jié)。

巨人的肩膀

• 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