Can you summarize the following document?
        
  計算複雜性理論所研究的資源中最常見的是時間(要通過多少步演算才能解決問題)和空間(在解決問題時需要多少記憶體)。其他資源亦可考慮,例如在平行計算中,需要多少並行處理器才能解決問題。  時間複雜度是指在電腦科學與工程領域完成一個演算法所需要的時間,是衡量一個演算法優劣的重要引數。時間複雜度越小,說明該演算法效率越高,則該演算法越有價值。  空間複雜度是指電腦科學領域完成一個演算法所需要佔用的儲存空間,一般是輸入引數的函式。它是演算法優劣的重要度量指標,一般來說,空間複雜度越小,演算法越好。我們假設有一個圖靈機來解決某一類語言的某一問題,設有formula_1個字(word)屬於這個問題,把formula_1放入這個圖靈機的輸入端,這個圖靈機為解決此問題所需要的工作帶格子數總和稱為空間。  複雜度理論和可計算性理論不同,可計算性理論的重心在於問題能否解決,不管需要多少資源。而複雜性理論作為計算理論的分支,某種程度上被認為和演算法理論是一種“矛”與“盾”的關係,即演算法理論專注於設計有效的演算法,而複雜性理論專注於理解為什麼對於某類問題,不存在有效的演算法。

  在20世紀50年代,Trahtenbrot和Rabin的論文被認為是該領域最早的文獻。而一般說來,被公認為奠定了計算複雜性領域基礎的是Hartmanis和Stearns的1960年代的論文On the computational complexity of algorithms。在這篇論文中,作者引入了時間複雜性類formula_3的概念,並利用對角線法證明了時間層級定理(Time Hierarchy Theorem)。  在此之後,許多研究者對複雜性理論作出了貢獻。期間重要的發現包括:對隨機演算法的去隨機化(derandomization)的研究,對近似演算法的不可近似性(hardness of approximation)的研究,以及互動式證明系統理論和零知識證明(Zero-knowledge proof)等。特別的複雜性理論對近代密碼學的影響非常顯著,而最近,複雜性理論的研究者又進入了博弈論領域,並創立了“演算法博弈論”(algorithmic game theory)這一分支。

  

  計算複雜性理論的研究物件是演算法在執行時所需的計算資源,而為了討論這一點,我們必須假設演算法是在某個計算模型上執行的。常討論的計算模型包括圖靈機(Turing machine)和電路(circuit),它們分別是一致性(uniform)和非一致性(non-uniform)計算模型的代表。而計算資源與計算模型是相關的,如對圖靈機我們一般討論的是時間、空間和隨機源,而對電路我們一般討論電路的大小。  由邱奇-圖靈論題(Church-Turing thesis),所有的一致的計算模型與圖靈機在多項式時間意義下是等價的。而由於我們一般將多項式時間作為有效演算法的標誌,該論題使得我們可以僅僅關注圖靈機而忽略其它的計算模型。

  我們考慮對一個演算法問題,什麼樣的回答是我們所需要的。比如搜尋問題:給定陣列formula_4,和一個數formula_5,我們要問formula_5在不在formula_4中(判定性問題,decision problem)。而進一步的,formula_5如果在formula_4中的話,formula_5的位置是什麼(搜尋型問題,search problem)。再比如完美匹配問題(perfect matching):給定一個二分圖formula_11,我們問是不是存在邊集formula_12,使得二分圖中每個結點恰好屬於該邊集的一條邊(判定型問題)。而進一步的,formula_12存在的話,formula_12具體是什麼(搜尋型問題)。  自然的,我們會發現對於一般的演算法問題formula_4,我們都可以這樣來問:首先,解是不是存在的?其次,如果解存在,這個解具體是什麼?這就是formula_4的判定型問題和formula_4的搜尋型問題(又稱函式型問題)區分來源的直觀解釋。對判定型問題的回答只需是“是”或“否”,而對搜尋型問題,需要返回解的具體形式或者“解不存在”。所以一個對formula_4的搜尋型問題的演算法自然的也是對formula_4的判定型問題的演算法。反之,給定了一個formula_4的判定型問題的演算法,是否存在formula_4的搜尋型問題的演算法,在可計算性理論和計算複雜性理論中有著不同的回答,這也是理解計算複雜性理論與它的前身可計算性理論不同的一個基本的觀察。  在可計算性理論中,可以說明,判定型問題和搜尋型問題在可計算性的意義下是等價的(見Decision problem)。而在計算複雜性中,Khuller和Vazirani在1990年代證明了在P≠NP的假設下,平面圖4-著色問題的判定型問題是在P中的,而尋找其字典序第一的著色是NP難的。  所以在可計算性理論中,只關注判定型問題是合理的。在計算複雜性理論中,雖然一些基本的複雜性類(如P,NP和PSPACE),以及一些基本的問題(P和NP關係問題等)是用判定型問題來定義的,但函式型問題複雜性類也被定義(如FP,FNP等),而且一些特別的函式型問題複雜性類,如TFNP,也正在逐漸受到關注。

  上面提到計算複雜性理論的研究物件是執行一項計算任務所用的資源,特別的,時間和空間是最重要的兩項資源。  我們用時間作例子來討論演算法分析的一些基礎知識。如果將輸入的長度(設為formula_22)作為變數,而我們關注的是演算法執行時間與formula_22的函式關係formula_24。因為一個演算法在不同的計算模型上實現時formula_24可能會有常數因子的差別(參見可計算性理論),我們使用大O表示式來表示formula_24,這使得我們可以忽略在不同計算模型上實現的常數因子。  以搜尋這個計算任務為例。在搜尋問題中,給定了一個具體的數formula_5,和長度為formula_22的陣列formula_4(陣列中數的位置用1到formula_22作標記),任務是當formula_5在formula_4中時,找到formula_5的位置,而formula_5不在formula_4中時,需要報告"未找到"。這時輸入的長度即為formula_36。下面的過程即是一個最簡單的演算法:我們依次掃過formula_4中的每個數,並與formula_5進行比較,如果相等即返回當前的位置,如果掃遍所有的數而演算法仍未停止,則返回"未找到"。  如果我們假設formula_5在formula_4中每個位置的機率都相同,那麼演算法在找到formula_5的條件下需要formula_42的時間。如果formula_5不在formula_4中,那麼需要formula_45的時間。由大O表示式的知識我們知道演算法所需的時間即為formula_46。  而如果我們進一步假設formula_4是已排序的,那麼我們有二分查詢演算法,使得演算法的執行時間是formula_48。可以看出執行一項計算任務,不同的演算法在執行時間上是有很大差異的。

  將計算問題按照在不同計算模型下所需資源的不同予以分類,從而得到一個對演算法問題“難度”的類別,就是複雜性理論中複雜性類概念的來源。例如一個問題如果在確定性圖靈機上所需時間不會超過一個確定的多項式(以輸入的長度為多項式的不定元),那麼我們稱這類問題的集合為P(polynomial time Turing machine)。而將前述定義中的“確定性圖靈機”改為“不確定性圖靈機”,那麼所得到的問題集合為NP(non-deteministic polynomial time Turing machine)。類似的,設formula_22為輸入的長度,那我們可以定義“在確定性圖靈機上所需空間不超formula_48的演算法問題的集合”(即為formula_51),“存在深度為formula_48,輸入的度(fan-in)為formula_53的電路族(circuit family)的演算法問題的集合”(即為NC)等等複雜性類。  定義複雜性類問題的目的是為了將所有的演算法問題進行分類,以確定當前演算法的難度,和可能的前進方向。這是複雜性理論的一個主線之一:對演算法問題進行抽象和分類。例如透過大O表示式,我們可以對忽略因計算模型不同而引入的常數因子。而第二個重要的理論假設,就是將多項式時間作為有效演算法的標誌(與之對應的是指數時間)。這樣,複雜性類使得我們可以忽略多項式階的不同而專注於多項式時間和指數時間的差別。(對多項式時間作為有效演算法的標誌這一點是有一定爭議的,比如,如果演算法的執行時間formula_54,那它也可以看作是緩慢的,見理論與實踐。)在本文的其餘章節,“有效演算法”等價於“多項式演算法”

  歸約(reduction)是將不同演算法問題建立聯絡的主要的技術手段,並且在某種程度上,定義了演算法問題的相對難度。簡單來說,假設我們有演算法任務formula_4和formula_56,如果我們想說“formula_4比formula_56簡單”(記為formula_59),它應該是什麼意思呢?從歸約的觀點來看,就是說如果我們有了formula_56的有效演算法formula_61,那麼我們有一個有效演算法formula_62,它可以引用formula_61,最終它要解決formula_4問題。  我們以點集覆蓋問題(vertex cover)和獨立集問題(independent set)為例來進行說明。這兩個問題都是圖論中的問題。假設給定了無向圖formula_11,和一個自然數formula_66,點集覆蓋問題是要找到formula_67的子集formula_68,使得對formula_69,有formula_70,使得formula_71,且formula_72;而獨立集問題也是要找formula_67的子集formula_68,要求是formula_75,且formula_72。  一個簡單的觀察即是:對formula_11,一個formula_78是覆蓋點集,當且僅當formula_68在formula_80的補圖中是獨立點集(而且保持集合大小)。利用這個觀察,假設我們有了解決覆蓋點集問題的演算法formula_61,我們設計解決獨立點集的演算法N如下:  可以看出若產生補圖這一步是有效的,那麼如果formula_61有效,formula_62也是有效的。一般的,如果我們有一個formula_56有效的演算法formula_61,和利用formula_56作為“神諭”(oracle)的解決formula_4問題的演算法formula_62,那麼如果formula_62是有效的,則我們有有效的解決formula_4問題的演算法formula_108——只需將formula_62中查詢B的操作換作具體的formula_61演算法即可。而這一性質的基本解釋是:將多項式的不定元用另一個多項式代替,那麼得到的仍是一個多項式。  所以從歸約的觀點來看,下面的說法可以看作與“formula_4比formula_56簡單”(記為formula_59)等價:

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

  在上面我們已經知道,NP是指“在非確定性圖靈機上有多項式時間演算法的問題”的集合,而P是指“在確定性圖靈機上有多項式時間演算法的問題”的集合。這裡我們都考慮的是判定型問題,即考慮一個語言formula_51,我們要判斷一個字串formula_127是不是在formula_51中。那麼,一個等價的理解是:NP是指對在formula_51中的formula_127,有多項式長度的證據formula_131,而且對語言formula_132是有多項式時間演算法的;而P是指對formula_51中的formula_127,有多項式時間演算法判斷formula_127在不在formula_51中。  舉個例子,就是考慮完美匹配問題、點集覆蓋問題和圖不同構問題。這三個問題都有圖論背影,問題的描述如下:  關於這三個問題,它們在複雜性理論中,目前的地位如下:  這樣我們有了:在P中、在NP而不知道是不是在P中、在AM中而不知道是不是在NP中的三個問題。

  由於在多項式時間可以判斷formula_127在不在formula_51中,蘊含著formula_127本身就是其在formula_51中的證據的含義,所以P⊂NP。這個包含關係是不是嚴格的呢?或者說,是不是有語言formula_174NP,使得formula_175P?這就是著名的NP與P關係問題。從這個問題在1970年代被正式的提出之後,有NP完備理論賦予了它在實踐上的重要性,有證明複雜性理論賦予了它純數學理論上的重要性,有PCP理論和NP完備理論賦予了它演算法理論上的重要性。這些理論或者在根本上依賴於NP和P關係問題的某些假設,或者本身就是試圖去理解NP和P關係問題而發展出來的,這使得它成為了理論電腦科學乃至數學的中心問題之一。在2000年,克雷數學研究所 提出了新世紀的數學中七個中心問題,NP與P關係問題就是其中的一個。  關於NP與P關係問題最早發展出的理論是NP完備理論。我們在下面一節簡單瞭解NP完備理論。

  由上面歸約的知識我們知道,演算法問題之間可以根據歸約來定義相對的難度。即對問題formula_4和問題formula_56,我們認為formula_4比formula_56簡單,記為formula_59,就是存在使用formula_56問題解來解決formula_4問題的演算法formula_61,且formula_61是多項式時間的。那麼,在一個複雜性類中,有沒有可能存在“最難的問題”呢?具體的對NP,就是說是不是存在問題formula_185NP,使得對formula_186NP,有formula_187呢?對這樣的問題,我們稱它是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)在formula_188中的下界為指數,以及團問題(clique problem)在單調性電路(monotone circuit)中的下界為指數。然而在1994年Razborov和Rudich的著名論文自然性證明(Natural proof)中指出,上面所用證明電路下界的方法,在單向函式存在的前提下是不可能分離NP和P的。該結果使很多專家對證明電路下界來分離NP和P的前景表示不樂觀。

  計算複雜性的初衷是理解不同演算法問題的難度,特別的是一些重要演算法問題的困難性。為了確切的描述一個問題的困難性,計算複雜性的第一步抽象是認為多項式時間是有效的,非多項式時間是困難的。這基於指數函式增長速度的“違反直覺”的特性:如果一個演算法的時間複雜性為formula_189,取輸入的規模是100,在運算速度是formula_190每秒(關於CPU速度,參見Instructions per second,其中報告截止2009年,主流個人電腦的運算速度可以看作是formula_191每秒)的情況下,該程式將會執行formula_191年,幾乎是宇宙年齡。這為多項式時間被看作是有效時間提供了直觀上的證據。  然而多項式的指數很大的時候,演算法在實踐中也不能看作是有效的。如formula_193的多項式演算法,取問題規模大小為1000,那麼幾乎就是formula_194的大小。另一方面,即便一個問題沒有多項式演算法,它可能會有近似比很好的近似演算法(參見近似演算法),或有很好的啟發式演算法(heuristics)。啟發式演算法的特點是在理論上沒有精確的行為的分析,或者可以表明存在很壞的輸入,在這些輸入上執行很慢。然而在大多數時候,它都能快速解決問題。計算複雜性中對應的理論分析是平均複雜性理論(average-case complexity theory)和光滑分析(smooth analysis)。實際中的例子包括、布林可滿足性問題(參見SAT solver)和揹包問題。
計算複雜性理論(Computational complexity theory)是理論電腦科學和數學的一個分支,它致力於將可計算問題根據它們本身的複雜性分類,以及將這些類別聯絡起來。一個可計算問題被認為是一個原則上可以用計算機解決的問題,亦即這個問題可以用一系列機械的數學步驟解決,例如演算法。