大家好，我是大老李。上一期我們聊了什么是“時間復(fù)雜度”和“P vs NP”問題。 上期結(jié)尾留下一個疑問是：除了P和NP問題外，還有其他復(fù)雜度的問題嗎？答案是肯定的，而且非常多?？茖W(xué)家對不同的可以用算法求解的問題分類了多達(dá)數(shù)百種的復(fù)雜度，有人稱其為“復(fù)雜度動物園”。但是動物園里的動物太多了，我們一般愛好者沒有必要了解那么多。

但大老李可以帶大家了解其中最主要的一組復(fù)雜度，而且它們是沿著P和NP問題自然延伸的，所以比較容易記憶。 上一期我們了解到P問題是NP問題的子集，接下來大老李要介紹的一組復(fù)雜度，它們的特點都是：前一個復(fù)雜度都是后一個的子集。所以它們像俄羅斯套娃一般套在一起，越后面的復(fù)雜度，越復(fù)雜，它也會包含之前所有復(fù)雜度的問題。

第一個要介紹的復(fù)雜度叫PH問題(Polynomial Hierarchy)，中文可以叫做：“多項式層級問題”。PH問題是NP問題的一般化，它的一種定義是：“能以二階邏輯所表示語言的集合”。對“二階邏輯”，大老李之前在“不可證明的證明”那一期節(jié)目提到過，這里可以再簡單介紹下。

很多數(shù)學(xué)命題都以“存在”，或者“對任意”這兩個關(guān)鍵字開始。比如上一期提到的小圈子問題：“存在一個6人小圈子”，使得這6個人其他人都不是好友關(guān)系”。這個命題就是以“存在”二字開始。但如果一個命題同時有多個“存在”和“對任意”這兩個關(guān)鍵詞的話，這個命題的復(fù)雜度就會增長。比如把“小圈子”命題增強(qiáng)一下，改為“存在一個6人小圈子，使得這6個人其他人都不是好友關(guān)系，且不存在一個7人的小圈子，使這7人與其他人都不是好友關(guān)系”。你看，這個命題是不是要比之前的命題強(qiáng)許多？這種出現(xiàn)兩個“存在”或“對任意”關(guān)鍵詞的命題，往往就是“二階邏輯”命題。

當(dāng)然，我還可以增強(qiáng)下之前的命題，改成：對6-100之間的所有自然數(shù)n，存在一個n人小圈子，且不存在一個n+1人的小圈子”。雖然這個命題肯定是假命題，但是它的描述復(fù)雜度要比之前的更增加許多。總之，PH問題就是通過邏輯上的遞歸，使得表述復(fù)雜度層疊遞增的那些命題，它是NP問題的一般化。當(dāng)然，所有NP問題都是PH問題。

而且科學(xué)家發(fā)現(xiàn)，如果“P問題=NP問題”，則可以推出“P=PH”，這說明PH問題相比于NP并沒有出現(xiàn)復(fù)雜度本質(zhì)上的增加。所以反過來證明PH!=P，也許是一個證明P!=NP的思路。以上是有關(guān)PH問題。

接下來介紹的一個復(fù)雜度叫“多項式空間”問題，英語叫“P-SPACE”。這里“P”還是“多項式”的意思，“Space”就是英語“空間”一詞。之前我們都是考慮的時間復(fù)雜度，但是一個算法運(yùn)行時，不但要消耗時間，同樣要消耗內(nèi)存，這個內(nèi)存我們可以抽象為“空間”。我們問：一個算法的處理對象增加時，其消耗的內(nèi)存增加程度如何？這就是”空間復(fù)雜度”。那“多項式空間”復(fù)雜度就太容易理解了，就是程序隨處理對象增加，其消耗的內(nèi)存量是按多項式增加的。

科學(xué)家已經(jīng)證明所有PH問題都是“多項式空間問題”，推論就是：所有NP問題都是“多項式空間問題”，這一點還是可以用化歸思想簡單證明：

當(dāng)求解一個NP問題時，我們只需要保留我們已經(jīng)枚舉過的情況序號。還是以“小圈子問題”為例，當(dāng)我們不考慮時間消耗時，我們可以用枚舉法暴力求解，則我們需要對n個人里取6個人的組合的情況一一枚舉。這種枚舉組合可以通過循環(huán)語句構(gòu)造出來，而不需要事先在內(nèi)存里保留所有組合。只需要枚舉一種，檢查是否為小圈子，如果不是，則丟棄這種組合，枚舉下一種等等，這樣算法的內(nèi)存消耗幾乎是個常量，所以這個“小圈子問題”是一個“多項式空間問題”。用類似方法，可以證明NP問題都是多項式空間問題。

但是否存在某個多項式空間問題不是NP問題？這是未解決的問題。目前找到的一些可能的問題是有關(guān)棋類游戲的問題，比如圍棋的官子問題。圍棋是一種確定性的博弈問題，如果到了官子階段，還剩十幾二十個位置可以下，理論上可以畫出一棵完整博弈樹，把雙方從開始到結(jié)尾的每一步的組合都出來。

那么從這棵博弈樹里找出最佳著法的一種算法，人稱“極小-極大算法”（ min-max算法），其實就是模擬人腦計算的一個過程：我下一步的最佳著法，就是對方在他的下一步采取最佳著法時，我的最佳著法。 而對方下一步的最佳著法，又是我的下下一步最佳著法前提下，他的最佳著法，依此類推，如此遞歸驗算到最后一步，再反向回溯，就能找到雙方的最佳著法。

對以上算法考察空間復(fù)雜度的話，你會發(fā)現(xiàn)你只需要存儲博弈樹某一層的一個或幾個著法。如果這一層是我落子，那就存儲我的最佳著法，如果下一層是對方落子，則存儲對方最佳著法。如此推算，則我需要的存儲的空間應(yīng)該是正比例于博弈樹的深度，博弈樹的深度一般就是可落子的位置數(shù)，所以以上算法是“多項式空間”算法。這也是可以理解的，如果圍棋的計算需要指數(shù)級的空間增長 ，大概誰的腦容量都無法計算了。

但是官子問題看上去又不是一個NP問題。如果給你一個雙方官子落子的順序，你如何用算法判斷出這是否是雙方最佳官子順序呢？如果用以上“極小-極大算法”，其時間復(fù)雜度肯定是“指數(shù)時間”，你也不能說九段高手的判斷就一定正確。所以目前沒有一個能在多項式時間內(nèi)，判定某個官子順序是否最佳的算法，因此圍棋官子問題是一個屬于“多項式空間問題”，而看起來不是“NP問題”的問題。

比“多項式空間問題”更復(fù)雜一級的， 就是大家熟悉的“指數(shù)時間問題”，意思就是”算法執(zhí)行時間隨問題規(guī)模成指數(shù)增長。同樣，所有“多項式空間問題”都是“指數(shù)時間問題”。如何把“多項式空間問題”化歸為“指數(shù)時間問題”，我就留給聽眾思考，這是一道不錯的思考題。

另一方面，如你所猜測，目前科學(xué)家還沒有證明：存在某個問題，它是“指數(shù)時間問題”，但不是“多項式空間問題”。也就是，這個問題需要指數(shù)時間的計算，也肯定需要指數(shù)級的內(nèi)存消耗。一個完整的國際象棋或者圍棋博弈問題，可能是符合前述條件的，但目前無法證明。

以上，我們構(gòu)建了一條復(fù)雜度鏈條，從簡單到復(fù)雜是：NP, PH，多項式空間和指數(shù)時間。上一期我們還談到了P是NP的子集。有意思的是，P與NP之間，人們在研究量子計算機(jī)過程中，還定義兩種介于P與NP之間的復(fù)雜度。

首先的一種名叫：BPP問題（Bounded-error Probabilistic Polynomial time），中文可以叫做：“具有有界錯誤概率的多項式時間算法”。顧名思義，BPP問題首先具有一個多項式時間算法，但我們允許這種算法有一定的錯誤概率，但這個錯誤概率必須足夠小，有一個固定的上界。

根據(jù)定義，P問題顯然都是BPP問題，因為對P問題來說，這個錯誤率上界就是0。但BPP問題的算法可能輸出錯誤結(jié)果，那它有什么意義呢？當(dāng)然有。比如對NP問題，我們知道枚舉所有情況所需時間太久了，那實際求解時，我們當(dāng)然不會總是傻傻地開始枚舉。

我們可以用一些“啟發(fā)式”手段，來盡量找到合理的解。比如你讓我求解“三色地圖著色問題”，我肯定會隨便嘗試對某個區(qū)域畫一種顏色，然后從這個區(qū)域擴(kuò)散出來，盡量使用三種顏色，這是每個人都能找到的思路。

也許中途，我會發(fā)現(xiàn)沒法繼續(xù)著色，產(chǎn)生沖突了，這樣就不得不在之前某一步推倒重來。但我可以規(guī)定，我就從地圖中每個區(qū)域為起始，對它分別嘗試三種不同顏色的起始情況。這樣，如果圖中有n個區(qū)域，嘗試最多3乘以n輪之后，仍然沒有答案的話，我就宣告“無解”。

用電腦程序完全可以模擬以上過程，這個算法能夠在多項式時間內(nèi)結(jié)束。如果有解，那是最好；如果“無解”，那么這個“無解”是有一定錯誤概率的，因為沒有枚舉到所有情況。但是我可以說，我已經(jīng)嘗試了很多次，這個錯誤率應(yīng)該是很低的，并且我能證明錯誤率是%5以下等等。這種算法在實踐中是很有用的，因為很多情況下，我們希望在一定時間內(nèi)得出一個結(jié)果，哪怕它有一定錯誤幾率，這總比等不到結(jié)果好。以上就是BPP問題的含義。

最后一個復(fù)雜度叫BQP（Bounded-error Quantum Polynomial time）問題，中文叫“具有有界錯誤概率的量子多項式時間”，其實就比BPP問題多了“量子”二字。這種問題的一個簡單定義就是：可以用量子計算機(jī)快速（在多項式時間內(nèi)）處理的問題。那量子計算機(jī)與傳統(tǒng)計算機(jī)的關(guān)鍵區(qū)別在哪里呢？

上一期提到過，NP問題可以依靠“堆CPU”來快速求解，只要讓不同的電腦分別驗證不同的情況。而量子計算機(jī)利用了量子的“疊加態(tài)”，可以用少數(shù)幾個量子，來模擬非常多的CPU進(jìn)行并行運(yùn)算，并且通過量子最后“坍縮”結(jié)果，來得到我們需要的結(jié)果。這樣很多NP問題就成為多項式時間問題了，這也是我們研發(fā)量子計算機(jī)的一個最主要動力。

但是，另一方面量子的行為是不受控的，都是“概率性”的行為，“計算”結(jié)果總是會有誤差的。按“平行宇宙”理論說法，每次“測量”量子計算機(jī)的計算結(jié)果后，有些宇宙中的我們得到了正確的結(jié)果，有些則只能得到錯誤的結(jié)果。但好在錯誤概率是可以計算的，大不了我就多算幾次吧。多做幾次后，可以讓錯誤率降低到可以接受的程度。

但不管怎樣，總有誤差，所以量子計算機(jī)可以快速處理的問題被叫做：“具有有界錯誤概率的量子多項式時間”問題，簡稱BQP問題。目前一個典型的BQP問題是質(zhì)因數(shù)分解問題。之前說過，判斷一個數(shù)是否為質(zhì)數(shù)，是一個P問題，但是判斷出一個數(shù)不是質(zhì)數(shù)，并不表示我們能對這個數(shù)進(jìn)行質(zhì)因數(shù)分解。目前傳統(tǒng)計算機(jī)上最快的質(zhì)因數(shù)分解算法是一個接近于指數(shù)時間 (

)的算法。

而1994年，數(shù)學(xué)家彼得· 秀爾提出了一個質(zhì)因數(shù)分解的量子算法，其復(fù)雜度只有

，所以是一個標(biāo)準(zhǔn)的多項式時間問題，因此質(zhì)因數(shù)分解就是一個BQP問題。這也是為何我們說，一旦量子計算機(jī)突破到某個“量子霸權(quán)”時刻，一些加密算法會失效，就是因為一些加密算法依賴我們無法快速進(jìn)行質(zhì)因數(shù)分解這一前提。

但是不是所有的NP問題都是量子計算機(jī)都能快速求解的？目前科學(xué)家還不能證明，但科學(xué)家傾向于認(rèn)為NP問題與BQP問題是互不包容的。即存在一些NP問題，是量子計算機(jī)不能快速求解的，也存在一些BQP問題，是比NP問題更復(fù)雜的，即無法再多項式時間內(nèi)檢查答案的。但這都是有待證明的領(lǐng)域。

好了，以上就是今天關(guān)于“復(fù)雜度動物園”的介紹，復(fù)習(xí)一下幾個要點：

1. 算法復(fù)雜度分類多達(dá)數(shù)百種，但它們之間許多有包含的關(guān)系。
   

2. 以下這組復(fù)雜度，從簡單到復(fù)雜，有點像俄羅斯套娃，層層嵌套：它們是：P問題, NP問題，PH問題，多項式空間問題，指數(shù)時間問題。其中之前的每一個都是后面的復(fù)雜度的子集，但除NP與PH問題外，其他每兩種復(fù)雜度之間是否是“真子集”（即，是否可以排除“等于”）關(guān)系，都還未證明。
   

3. 以下這組復(fù)雜度，也構(gòu)成一組“套娃”：P問題，BPP問題，BQP問題。
   

4. 科學(xué)家認(rèn)為BQP問題，即量子計算機(jī)能快速處理的問題，雖然含有很多NP問題，但與NP問題互不包含。但這仍然是待證明的領(lǐng)域。
   

好了，下期再見！

參考鏈接：

https://en.wikipedia.org/wiki/PSPACEen.wikipedia.org

https://en.wikipedia.org/wiki/P_versus_NP_problemen.wikipedia.org

A Short Guide to Hard Problems | Quanta Magazinewww.quantamagazine.org

https://zh.m.wikipedia.org/zh-hans/PH_(%E8%A4%87%E9%9B%9C%E5%BA%A6)

Complexity Zoo:Ncomplexityzoo.uwaterloo.ca