什么是P=NP問題？

1 前言

今天和大家一起了解個(gè)高能知識點(diǎn)：P=NP問題。

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

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

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

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

2 千禧年世紀(jì)難題

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

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

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

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

• 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）

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

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

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

3 P類和NP類問題特征

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

簡單意譯一下：

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

這是計(jì)算機(jī)科學(xué)家稱之為NP問題的一個(gè)例子，因?yàn)楹苋菀讬z查一個(gè)同事提出的一百個(gè)學(xué)生的給定選擇是否令人滿意，然而從頭開始生成這樣一個(gè)列表的任務(wù)似乎太難了以至于完全不切實(shí)際。

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

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

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

P 問題(easy to find)

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

NP 問題(esay to check)

non-deterministic Polynomial time
譯：非確定性多項(xiàng)式時(shí)間可解決的問題

舉幾個(gè)例子來加深印象：

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

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

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

等等！讓我捋一捋，前面一直說 多項(xiàng)式時(shí)間 ，那么到底啥樣的時(shí)間是多項(xiàng)式時(shí)間呢？

4 多項(xiàng)式時(shí)間

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

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

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

這個(gè)世界并不是只有多項(xiàng)式時(shí)間這么簡單，我們還知道有指數(shù)函數(shù)形如2^n這個(gè)計(jì)算量已經(jīng)非常可怕，更不要說n^n和n!這種問題了。

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

我們通常將多項(xiàng)式時(shí)間看作是計(jì)算機(jī)解決問題的分水嶺，因?yàn)槌^多項(xiàng)式時(shí)間之后時(shí)間消耗上就不太好接受了。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 大突破之NPC問題

從特征上看，我們可以知道P類問題屬于NP問題，因?yàn)镻類問題屬于NP類問題中可在多項(xiàng)式時(shí)間驗(yàn)證并解決的問題，可以簡單認(rèn)為P類問題屬于特例最基本簡單的NP問題。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

先注意下這個(gè)定義，后面會(huì)用到，因?yàn)檫€有一類更復(fù)雜的問題...

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

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

7 NP-Hard問題

前面我知道了NPC問題，但是仍然有一部分特別的問題稱為NPH問題。

NP-Hard問題是滿足NPC問題定義的第二條，但不滿足第一條，也就是說所有NP問題可以歸約化到NPH問題，但是HP-Hard問題不一定是NP問題，所以NPH問題比NPC問題更難。

NPH問題比NPC問題難理解一些，看個(gè)回答：

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)系，如圖(敲黑板劃重點(diǎn))：

寫在最后

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

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

科幻還是未來，取決于現(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