計算複雜性理論

計算複雜性理論（Computational complexity theory）是理論計算機科學和數學的一個分支，它致力於將可計算問題根據它們本身的複雜性分類，以及將這些類別聯繫起來。一個可計算問題被認為是一個原則上可以用計算機解決的問題，亦即這個問題可以用一系列機械的數學步驟解決，例如算法。

如果一個問題的求解需要相當多的資源（無論用什麼算法），則被認為是難解的。計算複雜性理論通過引入數學計算模型來研究這些問題以及定量計算解決問題所需的資源（時間和空間），從而將資源的確定方法正式化了。其他複雜性測度同樣被運用，比如通信量（應用於通信複雜性），電路中門的數量（應用於電路複雜性）以及中央處理器的數量（應用於並行計算）。計算複雜性理論的一個作用就是確定一個能或不能被計算機求解的問題的所具有的實際限制。

在理論計算機科學領域，與此相關的概念有算法分析和可計算性理論。兩者之間一個關鍵的區別是前者致力於分析用一個確定的算法來求解一個問題所需的資源量，而後者則是在更廣泛意義上研究用所有可能的算法來解決相同問題。更精確地說，它嘗試將問題分成能或不能在現有的適當受限的資源條件下解決這兩類。相應地，在現有資源條件下的限制正是區分計算複雜性理論和可計算性理論的一個重要指標：後者關心的是何種問題原則上可以用算法解決。

簡介

計算複雜性理論所研究的資源中最常見的是時間（要通過多少步演算才能解決問題）和空間（在解決問題時需要多少記憶體）。其他資源亦可考慮，例如在並行計算中，需要多少並行處理器才能解決問題。

時間複雜度是指在電腦科學與工程領域完成一個演算法所需要的時間，是衡量一個演算法優劣的重要參數。時間複雜度越小，說明該演算法效率越高，則該演算法越有價值。

空間複雜度是指電腦科學領域完成一個演算法所需要占用的存儲空間，一般是輸入參數的函數。它是演算法優劣的重要度量指標，一般來說，空間複雜度越小，演算法越好。我們假設有一個圖靈機來解決某一類語言的某一問題，設有$X$個字（word）屬於這個問題，把$X$放入這個圖靈機的輸入端，這個圖靈機為解決此問題所需要的工作帶格子數總和稱為空間。

複雜度理論和可計算性理論不同，可計算性理論的重心在於問題能否解決，不管需要多少資源。而複雜性理論作為計算理論的分支，某種程度上被認為和算法理論是一種「矛」與「盾」的關係，即算法理論專注於設計有效的算法，而複雜性理論專注於理解為什麼對於某類問題，不存在有效的算法。

歷史

在20世紀50年代，Trahtenbrot和Rabin的論文被認為是該領域最早的文獻。而一般說來，被公認為奠定了計算複雜性領域基礎的是Hartmanis和Stearns的1960年代的論文On the computational complexity of algorithms。在這篇論文中，作者引入了時間複雜性類${\text{TIME}}(f(n))$的概念，並利用對角線法證明了時間層級定理（Time Hierarchy Theorem）。

在此之後，許多研究者對複雜性理論作出了貢獻。期間重要的發現包括：對隨機算法的去隨機化（derandomization）的研究，對近似算法的不可近似性（hardness of approximation）的研究，以及交互式證明系統理論和零知識證明（Zero-knowledge proof）等。特別的複雜性理論對近代密碼學的影響非常顯著，而最近，複雜性理論的研究者又進入了博弈論領域，並創立了「算法博弈論」（algorithmic game theory）這一分支。

基本概念和工具

計算模型與計算資源

計算複雜性理論的研究對象是算法在執行時所需的計算資源，而為了討論這一點，我們必須假設算法是在某個計算模型上運行的。常討論的計算模型包括圖靈機（Turing machine）和電路（circuit），它們分別是一致性（uniform）和非一致性（non-uniform）計算模型的代表。而計算資源與計算模型是相關的，如對圖靈機我們一般討論的是時間、空間和隨機源，而對電路我們一般討論電路的大小。

由邱奇-圖靈論題（Church-Turing thesis），所有的一致的計算模型與圖靈機在多項式時間意義下是等價的。而由於我們一般將多項式時間作為有效算法的標誌，該論題使得我們可以僅僅關注圖靈機而忽略其它的計算模型。

判定性問題和可計算性

主條目：判定性問題

我們考慮對一個算法問題，什麼樣的回答是我們所需要的。比如搜索問題：給定數組$A$，和一個數$s$，我們要問$s$在不在$A$中（判定性問題，decision problem）。而進一步的，$s$如果在$A$中的話，$s$的位置是什麼（搜索型問題，search problem）。再比如完美匹配問題（perfect matching）：給定一個二分圖$G=(V,E)$，我們問是不是存在邊集$E$，使得二分圖中每個結點恰好屬於該邊集的一條邊（判定型問題）。而進一步的，$E$存在的話，$E$具體是什麼（搜索型問題）。

自然的，我們會發現對於一般的算法問題$A$，我們都可以這樣來問：首先，解是不是存在的？其次，如果解存在，這個解具體是什麼？這就是$A$的判定型問題和$A$的搜索型問題（又稱函數型問題）區分來源的直觀解釋。對判定型問題的回答只需是「是」或「否」，而對搜索型問題，需要返回解的具體形式或者「解不存在」。所以一個對$A$的搜索型問題的算法自然的也是對$A$的判定型問題的算法。反之，給定了一個$A$的判定型問題的算法，是否存在$A$的搜索型問題的算法，在可計算性理論和計算複雜性理論中有着不同的回答，這也是理解計算複雜性理論與它的前身可計算性理論不同的一個基本的觀察。

在可計算性理論中，可以說明，判定型問題和搜索型問題在可計算性的意義下是等價的（見Decision problem）。而在計算複雜性中，Khuller和Vazirani在1990年代證明了在P≠NP的假設下，平面圖4-着色問題的判定型問題是在P中的，而尋找其字典序第一的着色是NP難的。

所以在可計算性理論中，只關注判定型問題是合理的。在計算複雜性理論中，雖然一些基本的複雜性類（如P，NP和PSPACE），以及一些基本的問題（P和NP關係問題等）是用判定型問題來定義的，但函數型問題複雜性類也被定義（如FP，FNP等），而且一些特別的函數型問題複雜性類，如TFNP，也正在逐漸受到關注。

算法分析

上面提到計算複雜性理論的研究對象是執行一項計算任務所用的資源，特別的，時間和空間是最重要的兩項資源。

我們用時間作例子來討論算法分析的一些基礎知識。如果將輸入的長度（設為$n$）作為變量，而我們關注的是算法運行時間與$n$的函數關係$T(n)$。因為一個算法在不同的計算模型上實現時$T(n)$可能會有常數因子的差別（參見可計算性理論），我們使用大O表達式來表示$T(n)$，這使得我們可以忽略在不同計算模型上實現的常數因子。

以搜索這個計算任務為例。在搜索問題中，給定了一個具體的數$s$，和長度為$n$的數組$A$（數組中數的位置用1到$n$作標記），任務是當$s$在$A$中時，找到$s$的位置，而$s$不在$A$中時，需要報告"未找到"。這時輸入的長度即為$n+1$。下面的過程即是一個最簡單的算法：我們依次掃過$A$中的每個數，並與$s$進行比較，如果相等即返回當前的位置，如果掃遍所有的數而算法仍未停止，則返回"未找到"。

如果我們假設$s$在$A$中每個位置的機率都相同，那麼算法在找到$s$的條件下需要${\frac {1}{n}}(1+2+\cdots +n)={\frac {n(n+1)}{2n}}={\frac {n+1}{2}}$的時間。如果$s$不在$A$中，那麼需要$(n+1)$的時間。由大O表達式的知識我們知道算法所需的時間即為$O(n)$。

而如果我們進一步假設$A$是已排序的，那麼我們有二分查找算法，使得算法的運行時間是$O(\log n)$。可以看出執行一項計算任務，不同的算法在運行時間上是有很大差異的。

複雜性類

將計算問題按照在不同計算模型下所需資源的不同予以分類，從而得到一個對算法問題「難度」的類別，就是複雜性理論中複雜性類概念的來源。例如一個問題如果在確定性圖靈機上所需時間不會超過一個確定的多項式（以輸入的長度為多項式的不定元），那麼我們稱這類問題的集合為P（polynomial time Turing machine）。而將前述定義中的「確定性圖靈機」改為「不確定性圖靈機」，那麼所得到的問題集合為NP（non-deteministic polynomial time Turing machine）。類似的，設$n$為輸入的長度，那我們可以定義「在確定性圖靈機上所需空間不超$O(\log n)$的算法問題的集合」（即為$L$），「存在深度為$O(\log n)$，輸入的度（fan-in）為$O(1)$的電路族（circuit family）的算法問題的集合」（即為NC¹）等等複雜性類。

定義複雜性類問題的目的是為了將所有的算法問題進行分類，以確定當前算法的難度，和可能的前進方向。這是複雜性理論的一個主線之一：對算法問題進行抽象和分類。例如透過大O表達式，我們可以對忽略因計算模型不同而引入的常數因子。而第二個重要的理論假設，就是將多項式時間作為有效算法的標誌（與之對應的是指數時間）。這樣，複雜性類使得我們可以忽略多項式階的不同而專注於多項式時間和指數時間的差別。（對多項式時間作為有效算法的標誌這一點是有一定爭議的，比如，如果算法的運行時間$n^{10}$，那它也可以看作是緩慢的，見理論與實踐。）在本文的其餘章節，「有效算法」等價於「多項式算法」

歸約

歸約（reduction）是將不同算法問題建立聯繫的主要的技術手段，並且在某種程度上，定義了算法問題的相對難度。簡單來說，假設我們有算法任務$A$和$B$，如果我們想說「$A$比$B$簡單」（記為$A\leq B$），它應該是什麼意思呢？從歸約的觀點來看，就是說如果我們有了$B$的有效算法$M$，那麼我們有一個有效算法$N$，它可以引用$M$，最終它要解決$A$問題。

我們以點集覆蓋問題（vertex cover）和獨立集問題（independent set）為例來進行說明。這兩個問題都是圖論中的問題。假設給定了無向圖$G=(V,E)$，和一個自然數$k$，點集覆蓋問題是要找到$V$的子集$S$，使得對$\forall e\in E$，有$s\in S$，使得$s\in e$，且$|S|\leq k$；而獨立集問題也是要找$V$的子集$S$，要求是$\forall s_{1},s_{2}\in S,(s_{1},s_{2})\notin E$，且$|S|\leq k$。

一個簡單的觀察即是：對$G=(V,E)$，一個$S\subset V$是覆蓋點集，當且僅當$S$在$G$的補圖中是獨立點集（而且保持集合大小）。利用這個觀察，假設我們有了解決覆蓋點集問題的算法$M$，我們設計解決獨立點集的算法N如下：

• 算法$N$。
  • 輸入：給定無向圖$G=(V,E)$，自然數$k$；
  • 輸出：一個大小小於等於$k$的獨立點集（如果存在，否則返回「不存在」）；
  • 已知：算法$M$，輸入為(無向圖$G$, 自然數$k$)，輸出大小小於等於$k$的覆蓋點集，如果這樣的點集存在。否則返回「不存在」；
• 算法步驟：
  1. 對$G$，產生$G$的補圖$G'$；
  2. 調用$M$，輸入為$(G',k)$；
  3. 如果$M$返回「不存在」，輸出不存在。如果$M$返回$S\subset V$，輸出$S$。

可以看出若產生補圖這一步是有效的，那麼如果$M$有效，$N$也是有效的。一般的，如果我們有一個$B$有效的算法$M$，和利用$B$作為「神諭」（oracle）的解決$A$問題的算法$N$，那麼如果$N$是有效的，則我們有有效的解決$A$問題的算法$N'$——只需將$N$中查詢B的操作換作具體的$M$算法即可。而這一性質的基本解釋是：將多項式的不定元用另一個多項式代替，那麼得到的仍是一個多項式。

所以從歸約的觀點來看，下面的說法可以看作與「$A$比$B$簡單」（記為$A\leq B$）等價：

• $A$歸約到$B$（reduces $A$ to $B$, or $A$ is reducible to $B$, or $A$ can be reduced to $B$）；
• 存在通過查詢$B$問題來解決$A$問題的算法（there exists an algorithm that asks oracles of $B$, and solves $A$）。

NP與P關係問題及相關理論

計算複雜性理論最成功的成果之一是NP完備理論。通過該理論，我們可以理解為什麼在程序設計與生產實踐中遇到的很多問題至今沒有找到多項式算法。而該理論更為計算複雜性中的核心問題：P與NP的關係問題指明了方向。

NP和P的定義

在上面我們已經知道，NP是指「在非確定性圖靈機上有多項式時間算法的問題」的集合，而P是指「在確定性圖靈機上有多項式時間算法的問題」的集合。這裡我們都考慮的是判定型問題，即考慮一個語言$L$，我們要判斷一個字符串$x$是不是在$L$中。那麼，一個等價的理解是：NP是指對在$L$中的$x$，有多項式長度的證據$w$，而且對語言$(x,w)$是有多項式時間算法的；而P是指對$L$中的$x$，有多項式時間算法判斷$x$在不在$L$中。

舉個例子，就是考慮完美匹配問題、點集覆蓋問題和圖不同構問題。這三個問題都有圖論背影，問題的描述如下：

• 完美匹配問題：給定圖$G=(V,E)$，找到邊的子集$F\subset E$，使得對任意的$v\in V$，存在唯一的$e\in F,v\in e$；
• 點集覆蓋問題：給定圖$G=(V,E)$，和自然數$k$，找到點的子集$U\subset V$，使得對任意的$e\in E$，存在$v\in U,v\in e$，且$|U|\leq k$；
• 圖不同構問題：給定圖$G=(V,E),H=(U,F),|G|=|H|$。我們說$G$和$H$是同構的，是指$\exists T:V\rightarrow U$，對任意的$s,t\in V$，滿足$E(s,t)=F(T(s),T(t))$（這裡我們把邊集$E$看作$V\times V\rightarrow \{0,1\}$的映射）。圖不同構是問對$G$和$H$，是不是不存在這樣的映射。

關於這三個問題，它們在複雜性理論中，目前的地位如下：

• 完美匹配問題：在P中。可以利用艾德蒙德算法得到$O({\sqrt {V}}E)$運行時間的算法；
• 點集覆蓋問題：在NP中，而不知道是否在P中。實際上，它是NP完備問題，給出它的多項式算法將意味着證明NP=P。它在NP中，原因是給定一個點的子集$U\subset V$，我們可以在多項式時間中驗證這是否是一個滿足$|U|\leq k$的點集覆蓋：$U$的大小很好驗證。然後只需對每一條邊$e$，遍歷$U$中每一個元素$v$，檢查是否有$v\in e$即可。運行時間至多為$O(VE)$；
• 圖不同構問題：在AM中，而不知道是否在NP中。它之所以困難，一個直觀的想法是：給定兩個圖$G$和$H$，首先這個問題的「證據」很難定義——不像點集覆蓋問題中，一個解就是一個點集，而且點集大小$\leq k\leq |V|$是多項式大小。這裡最直接的證據的定義，是說必須遍歷所有的映射$T:V\rightarrow U$，並對所有的映射驗證是否滿足同構的定義。而這樣一個證據是指數大小的。

這樣我們有了：在P中、在NP而不知道是不是在P中、在AM中而不知道是不是在NP中的三個問題。

NP與P關係問題

在P ≠ NP前提下複雜性類的關係圖解。在該前提下，不在P也不是NP完備的問題的存在性由Ladner解決。

由於在多項式時間可以判斷$x$在不在$L$中，蘊含着$x$本身就是其在$L$中的證據的含義，所以P⊂NP。這個包含關係是不是嚴格的呢？或者說，是不是有語言$L\in$NP，使得$L\notin$P？這就是著名的NP與P關係問題。從這個問題在1970年代被正式的提出之後，有NP完備理論賦予了它在實踐上的重要性，有證明複雜性理論賦予了它純數學理論上的重要性，有PCP理論和NP完備理論賦予了它算法理論上的重要性。這些理論或者在根本上依賴於NP和P關係問題的某些假設，或者本身就是試圖去理解NP和P關係問題而發展出來的，這使得它成為了理論計算機科學乃至數學的中心問題之一。在2000年，克雷數學研究所 提出了新世紀的數學中七個中心問題，NP與P關係問題就是其中的一個。

關於NP與P關係問題最早發展出的理論是NP完備理論。我們在下面一節簡單了解NP完備理論。

NP完備理論

主條目：NP完備

由上面歸約的知識我們知道，算法問題之間可以根據歸約來定義相對的難度。即對問題$A$和問題$B$，我們認為$A$比$B$簡單，記為$A\leq B$，就是存在使用$B$問題解來解決$A$問題的算法$M$，且$M$是多項式時間的。那麼，在一個複雜性類中，有沒有可能存在「最難的問題」呢？具體的對NP，就是說是不是存在問題$A\in$NP，使得對$\forall B\in$NP，有$B\leq A$呢？對這樣的問題，我們稱它是NP完備的。

這個問題乍看起來很不容易把握。因為這需要對所有的NP中的語言L，去找到一個L到A的歸約算法。然而1970年代的由史蒂芬·庫克和列昂尼德·列文分別發現的庫克-列文定理，證明了布爾表達式（Boolean formula）的可滿足性問題（SAT問題）是NP完備的。概括的說，他們證明了，有一個通用的過程對NP中任意語言在非確定性圖靈機上運行歷史用布爾表達式來編碼，使得該布爾表達式是可滿足的，當且僅當該運行歷史是對給定輸入，接受該輸入的。這樣，我們就有了第一個被證明是NP完備的問題。

在庫克給出SAT問題是NP完備之後不久，理查德·卡普證明了21個圖論、組合數學中常見的問題都是NP完備的。這賦予了NP完備問題在實踐中的重要性。現在，已經有成千個在實踐中遇到的算法問題被證明是NP完備的（參見NP完備問題列表），特別的有許多問題，如旅行商問題等的最優算法會帶來很大的經濟效益（旅行商問題的最優解可以給出最優的電路布線方案，而SAT的最優算法會促進程序驗證等問題的進步）。由NP完備的定義，我們知道對這其中任何一個問題的多項式算法都將給出所有NP問題，也包括所有NP完備問題的多項式算法。然而儘管實際問題中遇到很多NP完備的問題，而且有很多問題在不同領域有着相當的重要性而被大量研究，至今，仍沒有對NP完備問題的多項式算法，這是一些理論計算機科學家認為NP≠P的理由之一。

對NP和P關係問題，NP完備理論給出了如下的暗示：如果要證明NP=P，一個可能的方向是對NP完備問題給出多項式算法；如果要證明NP≠P，那麼必然的一個結果是NP完備問題沒有多項式算法。

電路複雜性

主條目：電路複雜性

電路複雜性理論在1990年代以前，被眾多研究者認為是解決NP與P關係問題的可能的途徑之一。電路複雜性研究的對象是非一致性的計算模型電路，並考慮計算一個布爾函數所需的最小的電路的深度（depth）和大小（size）等資源。其中，大小為多項式大小的電路族可以計算的布爾函數被記為P/poly。可以證明，P包含在P/poly之中，而卡普-利普頓定理（Karp-Lipton theorem）表明若P/poly在NP之中，則多項式層級（polynomial hierarchy）將會坍縮至第二層，這是一個不大可能的結果。這兩個結果結合起來表明，P/poly可以當作是分離NP與P的一個中間的工具，具體的途徑就是證明任一個NP完全問題的電路大小的下界。在直觀上說，電路複雜性也繞過了NP與P問題的第一個困難：相對化證明困難（relativizing proofs）。

在1980年代，電路複雜性途徑取得了一系列的成功，其中包括奇偶性函數（Parity function）在$AC^{0}$中的下界為指數，以及團問題（clique problem）在單調性電路（monotone circuit）中的下界為指數。然而在1994年Razborov和Rudich的著名論文自然性證明（Natural proof）中指出，上面所用證明電路下界的方法，在單向函數存在的前提下是不可能分離NP和P的。該結果使很多專家對證明電路下界來分離NP和P的前景表示不樂觀。

其它NP與P關係問題相關的理論

• 去隨機化理論：包括偽隨機數發生器dom generator）和extractor的構造等；
• 不可近似性：以PCP定理為基礎，基於NP≠P和更強的唯一性遊戲假設（Unique game conjecture），可以證明對一些問題不存在某近似比的近似算法；

理論與實踐

計算複雜性的初衷是理解不同算法問題的難度，特別的是一些重要算法問題的困難性。為了確切的描述一個問題的困難性，計算複雜性的第一步抽象是認為多項式時間是有效的，非多項式時間是困難的。這基於指數函數增長速度的「違反直覺」的特性：如果一個算法的時間複雜性為$2^{n}$，取輸入的規模是100，在運算速度是$10^{12}$每秒（關於CPU速度，參見Instructions per second，其中報告截止2009年，主流個人電腦的運算速度可以看作是$4\times 10^{10}$每秒）的情況下，該程序將會運行$4\times 10^{10}$年，幾乎是宇宙年齡。這為多項式時間被看作是有效時間提供了直觀上的證據。

然而多項式的指數很大的時候，算法在實踐中也不能看作是有效的。如$n^{10}$的多項式算法，取問題規模大小為1000，那麼幾乎就是$2^{100}$的大小。另一方面，即便一個問題沒有多項式算法，它可能會有近似比很好的近似算法（參見近似算法），或有很好的啟發式算法（heuristics）。啟發式算法的特點是在理論上沒有精確的行為的分析，或者可以表明存在很壞的輸入，在這些輸入上運行很慢。然而在大多數時候，它都能快速解決問題。計算複雜性中對應的理論分析是平均複雜性理論（average-case complexity theory）和光滑分析（smooth analysis）。實際中的例子包括Presburger arithmetic、布爾可滿足性問題（參見SAT solver）和背包問題。

參見

• 時間複雜度
• 遊戲複雜度
• 空間複雜度
• 計算理論
  • 可計算性理論
  • 計算複雜性理論

參考文獻

來源

書籍

• Arora, Sanjeev; Barak, Boaz, Computational Complexity: A Modern Approach, Cambridge, 2009 [2018-06-22], ISBN 978-0-521-42426-4, Zbl 1193.68112, （原始內容存檔於2021-03-20） 
• Downey, Rod; Fellows, Michael, Parameterized complexity, Berlin, New York: Springer-Verlag, 1999 
• Du, Ding-Zhu; Ko, Ker-I, Theory of Computational Complexity, John Wiley & Sons, 2000, ISBN 978-0-471-34506-0 
• Template:Garey-Johnson
• Goldreich, Oded, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008 [2018-06-22], （原始內容存檔於2021-11-08） 
• van Leeuwen, Jan (編), Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, 1990, ISBN 978-0-444-88071-0 
• Papadimitriou, Christos, Computational Complexity 1st, Addison Wesley, 1994, ISBN 0-201-53082-1 
• Sipser, Michael, Introduction to the Theory of Computation 2nd, USA: Thomson Course Technology, 2006, ISBN 0-534-95097-3 

期刊文章

• Khalil, Hatem; Ulery, Dana, A Review of Current Studies on Complexity of Algorithms for Partial Differential Equations, Proceedings of the annual conference on - ACM 76 (ACM '76 Proceedings of the 1976 Annual Conference), 1976: 197, doi:10.1145/800191.805573 
• Cook, Stephen, An overview of computational complexity (PDF), Commun. ACM (ACM), 1983, 26 (6): 400–408 [2018-06-22], ISSN 0001-0782, doi:10.1145/358141.358144, （原始內容 (PDF)存檔於2018-07-22） 
• Fortnow, Lance; Homer, Steven, A Short History of Computational Complexity (PDF), Bulletin of the EATCS, 2003, 80: 95–133 [2018-06-22], （原始內容存檔 (PDF)於2021-03-20） 
• Mertens, Stephan, Computational Complexity for Physicists, Computing in Science and Eng. (Piscataway, NJ, USA: IEEE Educational Activities Department), 2002, 4 (3): 31–47, ISSN 1521-9615, arXiv:cond-mat/0012185 , doi:10.1109/5992.998639 

外部連結

• The Complexity Zoo （頁面存檔備份，存於網際網路檔案館）
• Hazewinkel, Michiel (編), Computational complexity classes, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4 
• What are the most important results (and papers) in complexity theory that every one should know?
• Scott Aaronson: Why Philosophers Should Care About Computational Complexity （頁面存檔備份，存於網際網路檔案館）