[科普中國]-復(fù)雜性理論

概述

所謂復(fù)雜性理論，從根本上說就是研究哪些工作可以很容易地用計算機完成，哪些工作不能的理論。

在復(fù)雜性理論中，最關(guān)鍵的事情是搞清楚隨著輸入數(shù)據(jù)的增長，解決一個問題所需的步驟會以什么樣的方式增加。1

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

在理論計算機科學(xué)領(lǐng)域，與此相關(guān)的概念有算法分析和可計算性理論。兩者之間一個關(guān)鍵的區(qū)別是前者致力于分析用一個確定的算法來求解一個問題所需的資源量，而后者則是在更廣泛意義上研究用所有可能的算法來解決相同問題。更精確地說，它嘗試將問題分成能或不能在現(xiàn)有的適當(dāng)受限的資源條件下解決這兩類。相應(yīng)地，在現(xiàn)有資源條件下的限制正是區(qū)分計算復(fù)雜性理論和可計算性理論的一個重要指標(biāo)：后者關(guān)心的是何種問題原則上可以用算法解決。

復(fù)雜性理論所研究的資源中最常見的是時間（要通過多少步演算才能解決問題）和空間（在解決問題時需要多少內(nèi)存）。其他資源亦可考慮，例如在并行計算中，需要多少并行處理器才能解決問題。

時間復(fù)雜度是指在計算機科學(xué)與工程領(lǐng)域完成一個算法所需要的時間，是衡量一個算法優(yōu)劣的重要參數(shù)。時間復(fù)雜度越小，說明該算法效率越高，則該算法越有價值。

空間復(fù)雜度是指計算機科學(xué)領(lǐng)域完成一個算法所需要占用的存儲空間，一般是輸入?yún)?shù)的函數(shù)。它是算法優(yōu)劣的重要度量指標(biāo)，一般來說，空間復(fù)雜度越小，算法越好。我們假設(shè)有一個圖靈機來解決某一類語言的某一問題，設(shè)有X個字（word）屬于這個問題，把X放入這個圖靈機的輸入端，這個圖靈機為解決此問題所需要的工作帶格子數(shù)總和稱為空間。

復(fù)雜度理論和可計算性理論不同，可計算性理論的重心在于問題能否解決，不管需要多少資源。而復(fù)雜性理論作為計算理論的分支，某種程度上被認(rèn)為和算法理論是一種“矛”與“盾”的關(guān)系，即算法理論專注于設(shè)計有效的算法，而復(fù)雜性理論專注于理解為什么對于某類問題，不存在有效的算法2。

歷史在20世紀(jì)50年代，Trahtenbrot和Rabin的論文被認(rèn)為是該領(lǐng)域最早的文獻(xiàn)。而一般說來，被公認(rèn)為奠定了計算復(fù)雜性領(lǐng)域基礎(chǔ)的是Hartmanis和Stearns的1960年代的論文On the computational complexity of algorithms。在這篇論文中，作者引入了時間

在20世紀(jì)50年代，Trahtenbrot和Rabin的論文被認(rèn)為是該領(lǐng)域最早的文獻(xiàn)。而一般說來，被公認(rèn)為奠定了計算復(fù)雜性領(lǐng)域基礎(chǔ)的是Hartmanis和Stearns的1960年代的論文On the computational complexity of algorithms。在這篇論文中，作者引入了時間復(fù)雜性類TIME(f(n))的概念，并利用對角線法證明了時間層級定理（Time Hierarchy Theorem）。

在此之后，許多研究者對復(fù)雜性理論作出了貢獻(xiàn)。期間重要的發(fā)現(xiàn)包括：對隨機算法的去隨機化（derandomization）的研究，對近似算法的不可近似性（hardness of approximation）的研究，以及交互式證明系統(tǒng)理論和零知識證明（Zero-knowledge proof）等。特別的復(fù)雜性理論對近代密碼學(xué)的影響非常顯著，而最近，復(fù)雜性理論的研究者又進(jìn)入了博弈論領(lǐng)域，并創(chuàng)立了“算法博弈論”（algorithmic game theory）這一分支3。

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

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

判定性問題和可計算性主條目：判定性問題

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

自然的，我們會發(fā)現(xiàn)對于一般的算法問題A，我們都可以這樣來問：首先，解是不是存在的？其次，如果解存在，這個解具體是什么？這就是A的判定型問題和A的搜索型問題（又稱函數(shù)型問題）區(qū)分來源的直觀解釋。對判定型問題的回答只需是“是”或“否”，而對搜索型問題，需要返回解的具體形式或者“解不存在”。所以一個對A的搜索型問題的算法自然的也是對A的判定型問題的算法。反之，給定了一個A的判定型問題的算法，是否存在A的搜索型問題的算法，在可計算性理論和計算復(fù)雜性理論中有著不同的回答，這也是理解計算復(fù)雜性理論與它的前身可計算性理論不同的一個基本的觀察。

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

所以在可計算性理論中，只關(guān)注判定型問題是合理的。在計算復(fù)雜性理論中，雖然一些基本的復(fù)雜性類（如P，NP和PSPACE），以及一些基本的問題（P和NP關(guān)系問題等）是用判定型問題來定義的，但函數(shù)型問題復(fù)雜性類也被定義（如FP，F(xiàn)NP等），而且一些特別的函數(shù)型問題復(fù)雜性類，如TFNP，也正在逐漸受到關(guān)注。

算法分析上面提到計算復(fù)雜性理論的研究對象是執(zhí)行一項計算任務(wù)所用的資源，特別的，時間和空間是最重要的兩項資源。

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

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

如果我們假設(shè)s在A中每個位置的概率都相同，那么算法在找到s的條件下需要1/n (1+2+...+n)=n(n+1)/2n=(n+1)/2的時間。如果s不在A中，那么需要(n+1)的時間。由大O表達(dá)式的知識我們知道算法所需的時間即為O(n)。

而如果我們進(jìn)一步假設(shè)A是已排序的，那么我們有二分查找算法，使得算法的運行時間是O(logn)?？梢钥闯鰣?zhí)行一項計算任務(wù)，不同的算法在運行時間上是有很大差異的4。

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

定義復(fù)雜性類問題的目的是為了將所有的算法問題進(jìn)行分類，以確定當(dāng)前算法的難度，和可能的前進(jìn)方向。這是復(fù)雜性理論的一個主線之一：對算法問題進(jìn)行抽象和分類。例如透過大O表達(dá)式，我們可以對忽略因計算模型不同而引入的常數(shù)因子。而第二個重要的理論假設(shè)，就是將多項式時間作為有效算法的標(biāo)志（與之對應(yīng)的是指數(shù)時間）。這樣，復(fù)雜性類使得我們可以忽略多項式階的不同而專注于多項式時間和指數(shù)時間的差別。（對多項式時間作為有效算法的標(biāo)志這一點是有一定爭議的，比如，如果算法的運行時間n，那它也可以看作是緩慢的，見理論與實踐。）在本文的其余章節(jié)，“有效算法”等價于“多項式算法”

歸約歸約（reduction）是將不同算法問題建立聯(lián)系的主要的技術(shù)手段，并且在某種程度上，定義了算法問題的相對難度。簡單來說，假設(shè)我們有算法任務(wù)A和B，如果我們想說“A比B簡單”（記為A≤B），它應(yīng)該是什么意思呢？從歸約的觀點來看，就是說如果我們有了B的有效算法M，那么我們有一個有效算法N，它可以引用M，最終它要解決A問題。

我們以點集覆蓋問題（vertex cover）和獨立集問題（independent set）為例來進(jìn)行說明。這兩個問題都是圖論中的問題。假設(shè)給定了無向圖G=(V, E)，和一個自然數(shù)k，點集覆蓋問題是要找到V的子集S，使得對?e∈E，有s∈ S，使得s∈ e，且|S|≤k；而獨立集問題也是要找V的子集S，要求是?s1, s2∈S，(s1, s2)? E，且|S|≤k。

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

算法N。

輸入：給定無向圖G=(V, E)，自然數(shù)k；

輸出：一個大小≤ k的獨立點集（如果存在，否則返回“不存在”）；

已知：算法M，輸入為(無向圖G, 自然數(shù)k)，輸出大小≤ k的覆蓋點集，如果這樣的點集存在。否則返回“不存在”；

算法步驟：

對G，產(chǎn)生G的補圖G'；

調(diào)用M，輸入為(G', k)；

如果M返回“不存在”，輸出不存在。如果M返回S?V，輸出S。

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

所以從歸約的觀點來看，下面的說法可以看作與“A比B簡單”（記為A≤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）。

理論與實踐計算復(fù)雜性的初衷是理解不同算法問題的難度，特別的是一些重要算法問題的困難性。為了確切的描述一個問題的困難性，計算復(fù)雜性的第一步抽象是認(rèn)為多項式時間是有效的，非多項式時間是困難的。這基于指數(shù)函數(shù)增長速度的“違反直覺”的特性：如果一個算法的時間復(fù)雜性為2的n次方，取輸入的規(guī)模是100，在運算速度是10的12次方每秒（關(guān)于CPU速度，參見Instructions per second，其中報告截止2009年，主流個人電腦的運算速度可以看作是4X10的10次方每秒）的情況下，該程序?qū)\行4X10的10次方年，幾乎是宇宙年齡。這為多項式時間被看作是有效時間提供了直觀上的證據(jù)。

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