?「複雜度動物園」中的「俄羅斯套娃」
大家好，我是大老李。上一期我們聊了什麼是「時間複雜度」和「P vs NP」問題。 上期結尾留下一個疑問是：除了P和NP問題外，還有其他複雜度的問題嗎？答案是肯定的，而且非常多。科學家對不同的可以用演算法求解的問題分類了多達數百種的複雜度，有人稱其為「複雜度動物園」。但是動物園裡的動物太多了，我們一般愛好者沒有必要了解那麼多。
但大老李可以帶大家了解其中最主要的一組複雜度，而且它們是沿著P和NP問題自然延伸的，所以比較容易記憶。 上一期我們了解到P問題是NP問題的子集，接下來大老李要介紹的一組複雜度，它們的特點都是：前一個複雜度都是後一個的子集。所以它們像俄羅斯套娃一般套在一起，越後面的複雜度，越複雜，它也會包含之前所有複雜度的問題。
第一個要介紹的複雜度叫PH問題(Polynomial Hierarchy)，中文可以叫做：「多項式層級問題」。PH問題是NP問題的一般化，它的一種定義是：「能以二階邏輯所表示語言的集合」。對「二階邏輯」，大老李之前在「不可證明的證明」那一期節目提到過，這裡可以再簡單介紹下。
很多數學命題都以「存在」，或者「對任意」這兩個關鍵字開始。比如上一期提到的小圈子問題：「存在一個6人小圈子」，使得這6個人其他人都不是好友關係」。這個命題就是以「存在」二字開始。但如果一個命題同時有多個「存在」和「對任意」這兩個關鍵詞的話，這個命題的複雜度就會增長。比如把「小圈子」命題增強一下，改為「存在一個6人小圈子，使得這6個人其他人都不是好友關係，且不存在一個7人的小圈子，使這7人與其他人都不是好友關係」。你看，這個命題是不是要比之前的命題強許多？這種出現兩個「存在」或「對任意」關鍵詞的命題，往往就是「二階邏輯」命題。
當然，我還可以增強下之前的命題，改成：對6-100之間的所有自然數n，存在一個n人小圈子，且不存在一個n+1人的小圈子」。雖然這個命題肯定是假命題，但是它的描述複雜度要比之前的更增加許多。總之，PH問題就是通過邏輯上的遞歸，使得表述複雜度層疊遞增的那些命題，它是NP問題的一般化。當然，所有NP問題都是PH問題。
而且科學家發現，如果「P問題=NP問題」，則可以推出「P=PH」，這說明PH問題相比於NP並沒有出現複雜度本質上的增加。所以反過來證明PH!=P，也許是一個證明P!=NP的思路。以上是有關PH問題。
接下來介紹的一個複雜度叫「多項式空間」問題，英語叫「P-SPACE」。這裡「P」還是「多項式」的意思，「Space」就是英語「空間」一詞。之前我們都是考慮的時間複雜度，但是一個演算法運行時，不但要消耗時間，同樣要消耗內存，這個內存我們可以抽象為「空間」。我們問：一個演算法的處理對象增加時，其消耗的內存增加程度如何？這就是」空間複雜度」。那「多項式空間」複雜度就太容易理解了，就是程序隨處理對象增加，其消耗的內存量是按多項式增加的。
科學家已經證明所有PH問題都是「多項式空間問題」，推論就是：所有NP問題都是「多項式空間問題」，這一點還是可以用化歸思想簡單證明：
當求解一個NP問題時，我們只需要保留我們已經枚舉過的情況序號。還是以「小圈子問題」為例，當我們不考慮時間消耗時，我們可以用枚舉法暴力求解，則我們需要對n個人里取6個人的組合的情況一一枚舉。這種枚舉組合可以通過循環語句構造出來，而不需要事先在內存里保留所有組合。只需要枚舉一種，檢查是否為小圈子，如果不是，則丟棄這種組合，枚舉下一種等等，這樣演算法的內存消耗幾乎是個常量，所以這個「小圈子問題」是一個「多項式空間問題」。用類似方法，可以證明NP問題都是多項式空間問題。
但是否存在某個多項式空間問題不是NP問題？這是未解決的問題。目前找到的一些可能的問題是有關棋類遊戲的問題，比如圍棋的官子問題。圍棋是一種確定性的博弈問題，如果到了官子階段，還剩十幾二十個位置可以下，理論上可以畫出一棵完整博弈樹，把雙方從開始到結尾的每一步的組合都出來。
那麼從這棵博弈樹里找出最佳著法的一種演算法，人稱「極小-極大演算法」（ min-max演算法），其實就是模擬人腦計算的一個過程：我下一步的最佳著法，就是對方在他的下一步採取最佳著法時，我的最佳著法。 而對方下一步的最佳著法，又是我的下下一步最佳著法前提下，他的最佳著法，依此類推，如此遞歸驗算到最後一步，再反向回溯，就能找到雙方的最佳著法。
對以上演算法考察空間複雜度的話，你會發現你只需要存儲博弈樹某一層的一個或幾個著法。如果這一層是我落子，那就存儲我的最佳著法，如果下一層是對方落子，則存儲對方最佳著法。如此推算，則我需要的存儲的空間應該是正比例於博弈樹的深度，博弈樹的深度一般就是可落子的位置數，所以以上演算法是「多項式空間」演算法。這也是可以理解的，如果圍棋的計算需要指數級的空間增長 ，大概誰的腦容量都無法計算了。
但是官子問題看上去又不是一個NP問題。如果給你一個雙方官子落子的順序，你如何用演算法判斷出這是否是雙方最佳官子順序呢？如果用以上「極小-極大演算法」，其時間複雜度肯定是「指數時間」，你也不能說九段高手的判斷就一定正確。所以目前沒有一個能在多項式時間內，判定某個官子順序是否最佳的演算法，因此圍棋官子問題是一個屬於「多項式空間問題」，而看起來不是「NP問題」的問題。
比「多項式空間問題」更複雜一級的， 就是大家熟悉的「指數時間問題」，意思就是」演算法執行時間隨問題規模成指數增長。同樣，所有「多項式空間問題」都是「指數時間問題」。如何把「多項式空間問題」化歸為「指數時間問題」，我就留給聽眾思考，這是一道不錯的思考題。
另一方面，如你所猜測，目前科學家還沒有證明：存在某個問題，它是「指數時間問題」，但不是「多項式空間問題」。也就是，這個問題需要指數時間的計算，也肯定需要指數級的內存消耗。一個完整的國際象棋或者圍棋博弈問題，可能是符合前述條件的，但目前無法證明。
以上，我們構建了一條複雜度鏈條，從簡單到複雜是：NP, PH，多項式空間和指數時間。上一期我們還談到了P是NP的子集。有意思的是，P與NP之間，人們在研究量子計算機過程中，還定義兩種介於P與NP之間的複雜度。
首先的一種名叫：BPP問題（Bounded-error Probabilistic Polynomial time），中文可以叫做：「具有有界錯誤概率的多項式時間演算法」。顧名思義，BPP問題首先具有一個多項式時間演算法，但我們允許這種演算法有一定的錯誤概率，但這個錯誤概率必須足夠小，有一個固定的上界。
根據定義，P問題顯然都是BPP問題，因為對P問題來說，這個錯誤率上界就是0。但BPP問題的演算法可能輸出錯誤結果，那它有什麼意義呢？當然有。比如對NP問題，我們知道枚舉所有情況所需時間太久了，那實際求解時，我們當然不會總是傻傻地開始枚舉。
我們可以用一些「啟發式」手段，來盡量找到合理的解。比如你讓我求解「三色地圖著色問題」，我肯定會隨便嘗試對某個區域畫一種顏色，然後從這個區域擴散出來，盡量使用三種顏色，這是每個人都能找到的思路。
也許中途，我會發現沒法繼續著色，產生衝突了，這樣就不得不在之前某一步推倒重來。但我可以規定，我就從地圖中每個區域為起始，對它分別嘗試三種不同顏色的起始情況。這樣，如果圖中有n個區域，嘗試最多3乘以n輪之後，仍然沒有答案的話，我就宣告「無解」。
用電腦程序完全可以模擬以上過程，這個演算法能夠在多項式時間內結束。如果有解，那是最好；如果「無解」，那麼這個「無解」是有一定錯誤概率的，因為沒有枚舉到所有情況。但是我可以說，我已經嘗試了很多次，這個錯誤率應該是很低的，並且我能證明錯誤率是%5以下等等。這種演算法在實踐中是很有用的，因為很多情況下，我們希望在一定時間內得出一個結果，哪怕它有一定錯誤幾率，這總比等不到結果好。以上就是BPP問題的含義。
最後一個複雜度叫BQP（Bounded-error Quantum Polynomial time）問題，中文叫「具有有界錯誤概率的量子多項式時間」，其實就比BPP問題多了「量子」二字。這種問題的一個簡單定義就是：可以用量子計算機快速（在多項式時間內）處理的問題。那量子計算機與傳統計算機的關鍵區別在哪裡呢？
上一期提到過，NP問題可以依靠「堆CPU」來快速求解，只要讓不同的電腦分別驗證不同的情況。而量子計算機利用了量子的「疊加態」，可以用少數幾個量子，來模擬非常多的CPU進行並行運算，並且通過量子最後「坍縮」結果，來得到我們需要的結果。這樣很多NP問題就成為多項式時間問題了，這也是我們研發量子計算機的一個最主要動力。
但是，另一方面量子的行為是不受控的，都是「概率性」的行為，「計算」結果總是會有誤差的。按「平行宇宙」理論說法，每次「測量」量子計算機的計算結果後，有些宇宙中的我們得到了正確的結果，有些則只能得到錯誤的結果。但好在錯誤概率是可以計算的，大不了我就多算幾次吧。多做幾次後，可以讓錯誤率降低到可以接受的程度。
但不管怎樣，總有誤差，所以量子計算機可以快速處理的問題被叫做：「具有有界錯誤概率的量子多項式時間」問題，簡稱BQP問題。目前一個典型的BQP問題是質因數分解問題。之前說過，判斷一個數是否為質數，是一個P問題，但是判斷出一個數不是質數，並不表示我們能對這個數進行質因數分解。目前傳統計算機上最快的質因數分解演算法是一個接近於指數時間 ( )的演算法。
而1994年，數學家彼得· 秀爾提出了一個質因數分解的量子演算法，其複雜度只有 ，所以是一個標準的多項式時間問題，因此質因數分解就是一個BQP問題。這也是為何我們說，一旦量子計算機突破到某個「量子霸權」時刻，一些加密演算法會失效，就是因為一些加密演算法依賴我們無法快速進行質因數分解這一前提。
但是不是所有的NP問題都是量子計算機都能快速求解的？目前科學家還不能證明，但科學家傾向於認為NP問題與BQP問題是互不包容的。即存在一些NP問題，是量子計算機不能快速求解的，也存在一些BQP問題，是比NP問題更複雜的，即無法再多項式時間內檢查答案的。但這都是有待證明的領域。
好了，以上就是今天關於「複雜度動物園」的介紹，複習一下幾個要點：
- 演算法複雜度分類多達數百種，但它們之間許多有包含的關係。
- 以下這組複雜度，從簡單到複雜，有點像俄羅斯套娃，層層嵌套：它們是：P問題, NP問題，PH問題，多項式空間問題，指數時間問題。其中之前的每一個都是後面的複雜度的子集，但除NP與PH問題外，其他每兩種複雜度之間是否是「真子集」（即，是否可以排除「等於」）關係，都還未證明。
- 以下這組複雜度，也構成一組「套娃」：P問題，BPP問題，BQP問題。
- 科學家認為BQP問題，即量子計算機能快速處理的問題，雖然含有很多NP問題，但與NP問題互不包含。但這仍然是待證明的領域。
好了，下期再見！
參考鏈接：
https://en.wikipedia.org/wiki/PSPACE
https://zh.m.wikipedia.org/zh-hans/PH_(%E8%A4%87%E9%9B%9C%E5%BA%A6)Complexity Zoo:N
推薦閱讀：
