大家好，我是大老李。今天跟大家聊聊算法復(fù)雜度(Complexcity)問題。學(xué)過計(jì)算機(jī)算法課程的聽眾肯定聽說過“多項(xiàng)式復(fù)雜度”，“指數(shù)復(fù)雜度”這些名詞，還有著名的“P vs NP問題”。本期節(jié)目就來聊聊“P vs NP問題”。

首先，要說明幾個(gè)概念。要討論復(fù)雜度問題，首先要考慮的就是如何衡量一個(gè)算法的復(fù)雜度？你能想到的第一個(gè)指標(biāo)應(yīng)該就是時(shí)間。在同樣的計(jì)算能力下，一個(gè)算法執(zhí)行的時(shí)間時(shí)間越長，我們感覺上這個(gè)算法就應(yīng)該越復(fù)雜。這是對(duì)的，但是不同的算法直接比較運(yùn)行時(shí)間似乎又是不合理的。比如一個(gè)求一些數(shù)的最小公倍數(shù)的算法和一個(gè)對(duì)10個(gè)數(shù)字排序的算法，你光比較時(shí)間的話，你很難說哪個(gè)算法更復(fù)雜，因?yàn)檫@就是兩個(gè)不同的問題，沒有可比性。

所以計(jì)算機(jī)科學(xué)家使用另一個(gè)標(biāo)準(zhǔn)，就是當(dāng)一個(gè)算法隨著計(jì)算量的變化，所需計(jì)算次數(shù)的變化程度。比如，排序問題。排序問題本身有很多種不同的算法，這些算法之間應(yīng)該是可以比較好壞的。人們發(fā)現(xiàn)，決定算法時(shí)間效率的根本問題在于，當(dāng)一個(gè)問題規(guī)模擴(kuò)大時(shí)，算法循環(huán)執(zhí)行的次數(shù)。比如一個(gè)算法處理100個(gè)對(duì)象時(shí)，需要1分鐘，那么處理1000個(gè)對(duì)象時(shí)，到是需要10分鐘，還是100分鐘，還是2分鐘，這時(shí)就能看出算法的效率區(qū)別。

因此人們就開始分析，一個(gè)問題隨處理對(duì)象增加時(shí)，算法消耗時(shí)間的增長速度。比如在“冒泡排序”算法中，算法操作時(shí)間是隨著按排序?qū)ο蟮钠椒皆黾拥模Q為

的時(shí)間復(fù)雜度，并且人們發(fā)明了“大O”記號(hào)。冒泡排序的算法復(fù)雜度就用符號(hào)

表示。意思是如果排序16個(gè)對(duì)象需要x秒，則排序32個(gè)對(duì)象大約需要4x秒。而最快的排序算法，“快速排序”的時(shí)間復(fù)雜度是

，意思是如果排序16個(gè)對(duì)象需要x秒，則排序32個(gè)對(duì)象大約需要

秒。通過以上分析，我們就能看出快速排序要比冒泡排序效率高。

算法時(shí)間估算過程： 假設(shè)計(jì)算冒泡排序每次運(yùn)算需要k秒，則因冒泡排序是

時(shí)間復(fù)雜度，且對(duì)16個(gè)對(duì)象排序需要x秒，則（大致）有：

則對(duì)32個(gè)對(duì)象排序所需時(shí)間是：

對(duì)快速排序，則有：

，則可以推出：

而在那么多復(fù)雜度中，人們發(fā)現(xiàn)大多數(shù)算法可以分為兩大類，一大類中，這種算法的復(fù)雜度在大O符號(hào)中， 括號(hào)里是一個(gè)n的多項(xiàng)式，比如之前的冒泡排序，

就是一個(gè)n的多項(xiàng)式。這種情況下，人們稱這種算法的復(fù)雜度為“多項(xiàng)式時(shí)間復(fù)雜度”。

而另一大類則n處于指數(shù)位置上，比如

的復(fù)雜度，這種情況下 ，稱這個(gè)算法具有“指數(shù)時(shí)間”的復(fù)雜度?！爸笖?shù)時(shí)間”的復(fù)雜度顯然比”多項(xiàng)式時(shí)間” 復(fù)雜度要復(fù)雜很多，因?yàn)?/p>

增長速度是非?？斓摹?/p>

另外，在之前提到的快速排序算法中，它的時(shí)間復(fù)雜度

也被歸為多項(xiàng)式復(fù)雜度算法。因?yàn)?/p>

雖然不是典型的多項(xiàng)式，但它比大多數(shù)多項(xiàng)式的增長速度都慢，所以也歸類到多項(xiàng)式復(fù)雜度中。

還有一點(diǎn)，雖然“多項(xiàng)式時(shí)間”、“指數(shù)時(shí)間”這些術(shù)語都是衡量一個(gè)算法所需時(shí)間的增長速度，但為了表述簡便，我們有時(shí)也說“這個(gè)程序需要多項(xiàng)式時(shí)間”或者“需要指數(shù)時(shí)間”運(yùn)行等等。但你要知道，這其實(shí)是說這個(gè)程序的隨問題規(guī)模增加，其運(yùn)行時(shí)間的增長程度。

以上，我們簡單介紹了一下時(shí)間復(fù)雜度，那么我們可以開始聊聊什么是“P vs NP”問題。“P問題”是一類問題的總稱，這類問題的定義是這樣：如果一個(gè)問題存在一個(gè)多項(xiàng)式時(shí)間算法求解，則這個(gè)問題就是一個(gè)“P問題”。

其中的“P”是英語“多項(xiàng)式”一詞：polynomial的首字母。典型的P問題就是比如之前提到的排序問題。還有一個(gè)問題是質(zhì)數(shù)判定問題，給定一個(gè)整數(shù)，請(qǐng)判斷它是否為質(zhì)數(shù)。2002年，印度研究者發(fā)現(xiàn)了一個(gè)素?cái)?shù)判定算法，其算法復(fù)雜度為

，因此正式確認(rèn)了素?cái)?shù)判定是一個(gè)P問題。

你可能推測“NP問題”就是指所有不存在多項(xiàng)式算法時(shí)間的問題，或者就是“指數(shù)時(shí)間”問題，但這是一個(gè)誤解。NP問題的定義是這樣的：如果給你一個(gè)問題和這個(gè)問題的某個(gè)解答，存在一個(gè)多項(xiàng)式時(shí)間算法驗(yàn)證這個(gè)解答的正確性，則這個(gè)問題就是一個(gè)NP問題。聽起來有點(diǎn)拗口，我們還是可以舉個(gè)例子看看什么是驗(yàn)證解答：

給你一個(gè)整數(shù)和另一個(gè)比它小的整數(shù)，請(qǐng)你判斷這個(gè)小的整數(shù)是否是之前那個(gè)整數(shù)的因子，那你當(dāng)然可以簡單的去除一下，看看是否整除，這當(dāng)然是多項(xiàng)式時(shí)間內(nèi)可以完成的。

到這里，你是否發(fā)現(xiàn)一個(gè)情況：一個(gè)問題如果是P問題，則它必然也是NP問題。 比如給你一系列整數(shù)，問你這些整數(shù)是否從小到大排序好了？那我可以就用快速排序法，對(duì)這些整數(shù)進(jìn)行一次排序，然后看排序結(jié)果是否與你給定的順序一致就可以了， 而且肯定是在“多項(xiàng)式時(shí)間內(nèi)”完成了結(jié)果驗(yàn)證，所以排序問題是“NP問題”，雖然我用的判別方法很蠢。

以上證明中用到的就是數(shù)學(xué)中的“化歸”思想，就是將一個(gè)問題轉(zhuǎn)化成另一個(gè)問題的過程。通常我們是設(shè)法將一個(gè)未知問題轉(zhuǎn)化為一個(gè)已知解法的問題，這樣未知問題就可以用已知方法解決。

那我們用“化歸”思想證明命題–“所有P問題都是NP問題”：

對(duì)給定的一個(gè)P問題，用這個(gè)P問題的求解算法求解一次，然后與給定答案比較。則肯定能在多項(xiàng)式時(shí)間內(nèi)，判定這個(gè)答案是否正確，所以P問題就化歸為NP問題，即所有P問題都是NP問題。

這意味著，如果問：這個(gè)問題是P問題還是NP問題？這個(gè)問題是不太對(duì)的，因?yàn)槿绻@個(gè)問題是P問題，那么它也是NP問題。但我們?yōu)槭裁催€會(huì)這么問？那是因?yàn)槲覀儭澳J(rèn)”存在一些NP問題，它不存在多項(xiàng)式時(shí)間的求解算法，也就是它不是P問題。

為什么要說“默認(rèn)”二字？因?yàn)檫@是沒有證明過的事情。如果你能確切的證明某個(gè)問題存在多項(xiàng)式時(shí)間內(nèi)的驗(yàn)證算法，又不存在多項(xiàng)式時(shí)間內(nèi)的求解算法，那么恭喜你，你解決了克雷數(shù)學(xué)研究所提出的千禧年七大數(shù)學(xué)難題之一，即P與NP問題，并可獲得百萬美元的獎(jiǎng)金。

當(dāng)然，你可以反過來證明NP問題就是P問題，即NP與P互相可以“化歸”，那么你同樣也算解決了這個(gè)問題，盡管這看上去非常不可能。

那我們來舉些例子，看看我們默認(rèn)了哪些問題是NP問題，而不是P問題。

第一個(gè)問題叫“三色著色問題”。你可能知道有一個(gè)“四色定理”，它說：“任何一副地圖都可以用最多四種顏色著色，使得任何相鄰兩個(gè)區(qū)域有不同的顏色”。那現(xiàn)在給你一副地圖，問你“這幅地圖能不能用三種顏色著色，使得任何相鄰兩個(gè)區(qū)域有不同顏色”，當(dāng)然，有些地圖是可以做到，也有些地圖無法只用三種顏色著色。人們發(fā)現(xiàn)，找不到一個(gè)多項(xiàng)式時(shí)間算法，可以肯定找到一幅地圖的三色著色方案，所以，它看上去不是P問題。

但是如果我給你一副已經(jīng)用三種顏色著色的地圖，問你這是不是一種合理的著色方案，這個(gè)問題就太簡單了，你可以簡單檢查所有相鄰的區(qū)域，看是否存在相鄰區(qū)域用同一種顏色。如果不存在，那么這就是一個(gè)合理的著色方案。這種檢查，是可以在多項(xiàng)式時(shí)間里完成的。所以“三色著色”問題是一個(gè)NP問題。

第二個(gè)例子可以叫“整數(shù)求定和問題”。給你一大堆整數(shù)，問是否可以從中找到若干整數(shù)，使它們相加之和是0，或是其他任何一個(gè)給定的整數(shù)？你會(huì)發(fā)現(xiàn)，你不能找到一個(gè)多項(xiàng)式時(shí)間來求解。

以下這些整數(shù)中，存在若干數(shù)字之和為0嗎（大老李也不知道）？

91 74 -2 -86 75 21 50 -88 -22 26 -27 -16 -5 -89 -30 -4 85 50 73 -29

第三個(gè)例子，我給它名叫“小圈子問題”，這個(gè)問題是有關(guān)社交網(wǎng)絡(luò)的。假設(shè)我給你一大群人的社交網(wǎng)絡(luò)數(shù)據(jù)，比如這些人的微信賬號(hào)，以及這些人之間誰與誰是微信好友。現(xiàn)在我的問題是，你能否從中找出一些小圈子？比如：能否至少找出至少6個(gè)人，這6個(gè)人與其他所有人都不是好友？如果有的話，那么這6個(gè)人就構(gòu)成了一個(gè)小圈子。但是，你稍微思考下，要找出這樣的小圈子，多項(xiàng)式時(shí)間算法是沒有的。

另一方面，給你6個(gè)人或若干人，問你這些人是否構(gòu)成一個(gè)小圈子，那也是一瞬間就能判斷完成的事，所以，這個(gè)小圈子問題也是一個(gè)NP問題。

類似的問題還有很多，你大可上網(wǎng)搜索一下。那“NP問題”中的“NP”到底是什么含義？其實(shí)它的全稱叫“Non-deterministic polynomial”，中文為”非確定性多項(xiàng)式時(shí)間”問題。這個(gè)名字起得有點(diǎn)奧妙，其實(shí)意思也不難。在學(xué)術(shù)上，在判定一個(gè)問題的復(fù)雜度時(shí)，都是問一個(gè)是非題，這是非題的最后一句永遠(yuǎn)是：“這個(gè)程序或算法會(huì)停機(jī)嗎？”，“停機(jī)”的意思就是程序運(yùn)行終止，并（對(duì)NP問題）輸出一個(gè)“是”或“非”的結(jié)果。

當(dāng)然 ，之前提到的所有NP問題都必然會(huì)停機(jī)的，只要你枚舉所有情況。所以，我們問的會(huì)更具體點(diǎn)：“這個(gè)程序會(huì)在多項(xiàng)式時(shí)間里停機(jī)嗎”？P問題顯然都會(huì)在多項(xiàng)式時(shí)間內(nèi)停機(jī)，NP問題就有意思了。

比如那個(gè)三色地圖問題，如果這幅地圖存在某種三種顏色的著色方案，你運(yùn)氣也比較好，嘗試不久就找到一種合理的著色方案，那么程序就很快停機(jī)了。但如果這幅地圖不存在三種顏色著色方案，那么你必須等到程序枚舉了所有方案，才能等到一個(gè)否定的答案。這樣程序運(yùn)行時(shí)間就是成指數(shù)時(shí)間增加了。所以，你能看出“非確定性多項(xiàng)式時(shí)間”的含義，就是這個(gè)問題如果有解，那么你可能可以在多項(xiàng)式時(shí)間內(nèi)停機(jī)，但這是“非確定性的”。

有人還提出一個(gè)更強(qiáng)力的論據(jù)，就是搞一堆計(jì)算機(jī)，并行執(zhí)行程序。比如，如果這幅地圖可能的著色方案有1萬種，那我就用1萬臺(tái)電腦，分別檢查這1萬種不同的著色情況，那 必然在多項(xiàng)式時(shí)間就里給出結(jié)果了。所有的“NP問題”都有這樣的特點(diǎn)，就是你可以靠“堆CPU”來大幅縮短計(jì)算時(shí)間，因?yàn)闄z查某個(gè)答案是快的。

所以人們就問，以上這種問題與多項(xiàng)式時(shí)間算法問題有本質(zhì)區(qū)別嗎？是否存在某個(gè)問題，檢查它的答案很快，但不可能有一個(gè)多項(xiàng)式時(shí)間內(nèi)的求解算法？

你可能會(huì)說，這些問題出來那么久，都沒有人找到多項(xiàng)式時(shí)間算法，那不就說明它們會(huì)不會(huì)有多項(xiàng)式算法了？但是數(shù)學(xué)家都是“杠精”，沒有證明就不能下結(jié)論。

另一方面“P問題是否等于NP問題”，這個(gè)問題本身也很重要?，F(xiàn)在絕大多數(shù)人認(rèn)為“P!=NP”，但如果最終證明“P問題等于NP問題”，那后果很嚴(yán)重。因?yàn)槲覀儸F(xiàn)在絕大多數(shù)加密算法，都是基于“P問題不等于NP問題”這個(gè)假設(shè)。如果P=NP，那糟糕了，意味著很多加密算法都可以有多項(xiàng)式時(shí)間算法破解密碼，那這種加密算法也就崩潰了。另外有很多實(shí)用算法都是NP的，比如一些藥物分子形狀的計(jì)算、導(dǎo)航儀的路徑規(guī)劃，都與NP問題相關(guān)。這是P與NP問題的實(shí)用意義。

從理論意義上來講，P與NP問題是有在數(shù)理邏輯領(lǐng)域，有關(guān)問題復(fù)雜度分類中，兩種最基礎(chǔ)和最常見的問題形態(tài)，所以人們當(dāng)然想搞清楚它們之間的關(guān)系。

那P vs NP問題為什么這么難呢？如果你要證明P=NP，那么你就要證明一個(gè)問題有多項(xiàng)式時(shí)間的檢查算法，就肯定有多項(xiàng)式時(shí)間的求解算法，這看來是不太可能的。

如果要證明P!=NP，那么只要找到一個(gè)NP問題，它不存在多項(xiàng)式時(shí)間的求解算法。數(shù)學(xué)里，這種證明“不存在…”類型的問題，一般都是用反證法。但是這個(gè)問題怎么從反證中導(dǎo)出矛盾還是一個(gè)很大的問題。

此外，還有人考慮“P與NP問題”可能是如同“連續(xù)統(tǒng)假設(shè)”一樣，“無法證明”的問題，根據(jù)“P vs NP”問題與數(shù)理邏輯和圖靈機(jī)的緊密聯(lián)系，這種可能性是完全存在的。

最后，你會(huì)發(fā)現(xiàn)以上NP問題，都是在計(jì)算機(jī)課程中，被稱為“指數(shù)時(shí)間復(fù)雜度”的問題，那為什么不把 “NP問題”稱為“指數(shù)時(shí)間問題”呢？這個(gè)問題其實(shí)說對(duì)了一半。確實(shí)，所有NP問題都是“指數(shù)時(shí)間”問題，但與P vs NP問題類似，我們還沒有找到任何一個(gè)“指數(shù)時(shí)間問題”，肯定不是“NP問題”的。也就是“NP問題是否等于指數(shù)時(shí)間問題”仍然是一個(gè)未確定的問題。

在下一期節(jié)目里，我將介紹一下復(fù)雜度分類中其他若干種主要分類，以及它們之間的關(guān)系。簡單復(fù)習(xí)一下今天內(nèi)容的要點(diǎn)：

1. 我們用一個(gè)問題隨規(guī)模增長時(shí)，其計(jì)算量的增長的幅度，來對(duì)一個(gè)問題復(fù)雜度進(jìn)行度量?！岸囗?xiàng)式時(shí)間”和“指數(shù)時(shí)間”就是兩種最基本的時(shí)間復(fù)雜度問題。

2. 如果一個(gè)問題存在多項(xiàng)式時(shí)間的求解方法，則它就是P問題。一個(gè)問題存在多項(xiàng)式時(shí)間的驗(yàn)證方法，則它就是NP問題。

3. 已知P問題是NP問題的子集，但不知道是否為真子集。證明“P=NP”或者“P是NP的真子集”就是克雷研究所提出懸賞的“P vs NP”問題。

4. NP問題都是指數(shù)時(shí)間復(fù)雜度問題，但還不確定“NP問題”是否是“指數(shù)時(shí)間問題”的真子集。

?(上圖：P問題是NP問題的子集)

好，今天節(jié)目到這里。因?yàn)楸酒诠?jié)目是第三季的第一期，所以我再插播點(diǎn)新聞：

首先，大老李最近加入了“科學(xué)聲音”組織。感謝汪詰老師的垂青，大老李現(xiàn)在也是有組織的人了。希望有更多的人能支持科學(xué)聲音， 支持科普節(jié)目的傳播。

其次，大老李也有視頻節(jié)目了，請(qǐng)移步嗶哩嗶哩或海外觀眾上油管，并搜索“大老李聊數(shù)學(xué)”，可以搜到我的節(jié)目。目前我的視頻內(nèi)容主要是將音頻配上圖片或網(wǎng)頁配合觀眾理解。因?yàn)橹谱饕曨l非常費(fèi)精力，所以目前暫時(shí)內(nèi)容還不多。我也希望聽到各位反饋，告訴我你想看到的視頻內(nèi)容。

最后，如果你目前還只在喜馬拉雅上訂閱了我第二季節(jié)目的話，請(qǐng)一定搜索一下“大老李聊數(shù)學(xué)第三季”或“大老李聊數(shù)學(xué)全集”，以便得到后續(xù)節(jié)目的通知。第二季的專輯我就關(guān)閉了。

今天節(jié)目到這里，下期再見！