計算複雜性理論

計算複雜性理論是理論計算機科學和數學的一個分支，它致力於將可計算問題根據它們本身的複雜性分類，以及將這些類別聯絡起來。一個可計算問題被認為是一個原則上可以用計算機解決的問題，亦即這個問題可以用一系列機械的數學步驟解決，例如演算法。如果一個問題的求解需要相當多的資源。計算複雜性理論的一個作用就是確定一個能或不能被計算機求解的問題的所具有的實際限制。在理論計算機科學領域，與此相關的概念有演算法分析和可計算性理論。兩者之間一個關鍵的區別是前者致力於分析用一個確定的演算法來求解一個問題所需的資源量，而後者則是在更廣泛意義上研究用所有可能的演算法來解決相同問題。更精確地說，它嘗試將問題分成能或不能在現有的適當受限的資源條件下解決這兩類。相應地，在現有資源條件下的限制正是區分計算複雜性理論和可計算性理論的一個重要指標：後者關心的是何種問題原則上可以用演算法解決。簡介.計算複雜性理論所研究的資源中最常見的是時間。其他資源亦可考慮，例如在平行計算中，需要多少並行處理器才能解決問題。時間複雜度是指在電腦科學與工程領域完成一個演演算法所需要的時間，是衡量一個演演算法優劣的重要引數。時間複雜度越小，說明該演演算法效率越高，則該演演算法越有價值。空間複雜度是指電腦科學領域完成一個演演算法所需要佔用的儲存空間，一般是輸入引數的函式。它是演演算法優劣的重要度量指標，一般來說，空間複雜度越小，演演算法越好。我們假設有一個圖靈機來解決某一類語言的某一問題，設有formula_1個字屬於這個問題，把formula_1放入這個圖靈機的輸入端，這個圖靈機為解決此問題所需要的工作帶格子數總和稱為空間。複雜度理論和可計算性理論不同，可計算性理論的重心在於問題能否解決，不管需要多少資源。而複雜性理論作為計算理論的分支，某種程度上被認為和算法理論是一種“矛”與“盾”的關係，即算法理論專注於設計有效的演算法，而複雜性理論專注於理解為什麼對於某類問題，不存在有效的演算法。歷史.在20世紀50年代，Trahtenbrot和Rabin的論文被認為是該領域最早的而一般說來，被公認為奠定了計算複雜性領域基礎的是Hartmanis和Stearns的1960年代的論文On the computational complexity of algorithms。在這篇論文中，作者引入了時間複雜性類formula_3的概念，並利用對角線法證明了時間層級定理。在此之後，許多研究者對複雜性理論作出了貢獻。期間重要的發現包括：對隨機演算法的去隨機化這一分支。基本概念和工具.計算模型與計算資源.計算複雜性理論的研究物件是演算法在執行時所需的計算資源，而為了討論這一點，我們必須假設演算法是在某個計算模型上執行的。常討論的計算模型包括圖靈機計算模型的代表。而計算資源與計算模型是相關的，如對圖靈機我們一般討論的是時間、空間和隨機源，而對電路我們一般討論電路的大小。由邱奇-圖靈論題，所有的一致的計算模型與圖靈機在多項式時間意義下是等價的。而由於我們一般將多項式時間作為有效演算法的標誌，該論題使得我們可以僅僅關注圖靈機而忽略其它的計算模型。判定性問題和可計算性.我們考慮對一個演算法問題，什麼樣的回答是我們所需要的。比如搜尋問題：給定陣列formula_4，和一個數formula_5，我們要問formula_5在不在formula_4中。自然的，我們會發現對於一般的演算法問題formula_4，我們都可以這樣來問：首先，解是不是存在的？其次，如果解存在，這個解具體是什麼？這就是formula_4的判定型問題和formula_4的搜尋型問題區分直觀解釋。對判定型問題的回答只需是“是”或“否”，而對搜尋型問題，需要返回解的具體形式或者“解不存在”。所以一個對formula_4的搜尋型問題的演算法自然的也是對formula_4的判定型問題的演算法。反之，給定了一個formula_4的判定型問題的演算法，是否存在formula_4的搜尋型問題的演算法，在可計算性理論和計算複雜性理論中有著不同的回答，這也是理解計算複雜性理論與它的前身可計算性理論不同的一個基本的觀察。在可計算性理論中，可以說明，判定型問題和搜尋型問題在可計算性的意義下是等價的。而在計算複雜性中，Khuller和Vazirani在1990年代證明了在P≠NP的假設下，平面圖4-著色問題的判定型問題是在P中的，而尋找其字典序第一的著色是NP難的。所以在可計算性理論中，只關注判定型問題是合理的。在計算複雜性理論中，雖然一些基本的複雜性類，而且一些特別的函式型問題複雜性類，如TFNP，也正在逐漸受到關注。演算法分析.上面提到計算複雜性理論的研究物件是執行一項計算任務所用的資源，特別的，時間和空間是最重要的兩項資源。我們用時間作例子來討論演算法分析的一些基礎知識。如果將輸入的長度，我們使用大O表示式來表示formula_24，這使得我們可以忽略在不同計算模型上實現的常數因子。以搜尋這個計算任務為例。在搜尋問題中，給定了一個具體的數formula_5，和長度為formula_22的陣列formula_4，任務是當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。可以看出執行一項計算任務，不同的演算法在執行時間上是有很大差異的。複雜性類.將計算問題按照在不同計算模型下所需資源的不同予以分類，從而得到一個對演算法問題“難度”的類別，就是複雜性理論中複雜性類概念的例如一個問題如果在確定性圖靈機上所需時間不會超過一個確定的多項式等等複雜性類。定義複雜性類問題的目的是為了將所有的演算法問題進行分類，以確定當前演算法的難度，和可能的前進方向。這是複雜性理論的一個主線之一：對演算法問題進行抽象和分類。例如透過大O表示式，我們可以對忽略因計算模型不同而引入的常數因子。而第二個重要的理論假設，就是將多項式時間作為有效演算法的標誌在本文的其餘章節，“有效演算法”等價於“多項式演算法”歸約.歸約，它應該是什麼意思呢？從歸約的觀點來看，就是說如果我們有了formula_56的有效演算法formula_61，那麼我們有一個有效演算法formula_62，它可以引用formula_61，最終它要解決formula_4問題。我們以點集覆蓋問題為例來進行說明。這兩個問題都是圖論中的問題。假設給定了無向圖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作為“神諭”的解決formula_4問題的演算法formula_62，那麼如果formula_62是有效的，則我們有有效的解決formula_4問題的演算法formula_108——只需將formula_62中查詢B的操作換作具體的formula_61演算法即可。而這一性質的基本解釋是：將多項式的不定元用另一個多項式代替，那麼得到的仍是一個多項式。所以從歸約的觀點來看，下面的說法可以看作與“formula_4比formula_56簡單”等價：NP與P關係問題及相關理論.計算複雜性理論最成功的成果之一是NP完備理論。透過該理論，我們可以理解為什麼在程式設計與生產實踐中遇到的很多問題至今沒有找到多項式演算法。而該理論更為計算複雜性中的核心問題：P與NP的關係問題指明瞭方向。NP和P的定義.在上面我們已經知道，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中的三個問題。NP與P關係問題.由於在多項式時間可以判斷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完備理論。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年代的由史蒂芬·庫克和列昂尼德·列文分別發現的庫克-列文定理，證明了布林表示式是NP完備的。概括的說，他們證明了，有一個通用的過程對NP中任意語言在非確定性圖靈機上執行歷史用布林表示式來編碼，使得該布林表示式是可滿足的，當且僅當該執行歷史是對給定輸入，接受該輸入的。這樣，我們就有了第一個被證明是NP完備的問題。在庫克給出SAT問題是NP完備之後不久，理查德·卡普證明了21個圖論、組合數學中常見的問題都是NP完備的。這賦予了NP完備問題在實踐中的重要性。現在，已經有成千個在實踐中遇到的演算法問題被證明是NP完備的。由NP完備的定義，我們知道對這其中任何一個問題的多項式演算法都將給出所有NP問題，也包括所有NP完備問題的多項式演算法。然而儘管實際問題中遇到很多NP完備的問題，而且有很多問題在不同領域有著相當的重要性而被大量研究，至今，仍沒有對NP完備問題的多項式演算法，這是一些理論計算機科學家認為NP≠P的理由之一。對NP和P關係問題，NP完備理論給出瞭如下的暗示：如果要證明NP=P，一個可能的方向是對NP完備問題給出多項式演算法；如果要證明NP≠P，那麼必然的一個結果是NP完備問題沒有多項式演算法。電路複雜性.電路複雜性理論在1990年代以前，被眾多研究者認為是解決NP與P關係問題的可能的途徑之一。電路複雜性研究的物件是非一致性的計算模型電路，並考慮計算一個布林函式所需的最小的電路的深度。在1980年代，電路複雜性途徑取得了一系列的成功，其中包括奇偶性函式中指出，上面所用證明電路下界的方法，在單向函式存在的前提下是不可能分離NP和P的。該結果使很多專家對證明電路下界來分離NP和P的前景表示不樂觀。理論與實踐.計算複雜性的初衷是理解不同演算法問題的難度，特別的是一些重要演算法問題的困難性。為了確切的描述一個問題的困難性，計算複雜性的第一步抽象是認為多項式時間是有效的，非多項式時間是困難的。這基於指數函式增長速度的“違反直覺”的特性：如果一個演算法的時間複雜性為formula_189，取輸入的規模是100，在運算速度是formula_190每秒的情況下，該程式將會執行formula_191年，幾乎是宇宙年齡。這為多項式時間被看作是有效時間提供了直觀上的證據。然而多項式的指數很大的時候，演算法在實踐中也不能看作是有效的。如formula_193的多項式演算法，取問題規模大小為1000，那麼幾乎就是formula_194的大小。另一方面，即便一個問題沒有多項式演算法，它可能會有近似比很好的近似演算法和揹包問題。