計算復雜性理論

計算復雜性理論理論計算機科學分支學科01理論簡介基本概念理論實踐發(fā)展歷史相關理論目錄03050204基本信息計算復雜性理論（Computationalcomplexitytheory）是理論計算機科學和數(shù)學的一個分支，它致力于將可計算問題根據(jù)它們本身的復雜性分類，以及將這些類別聯(lián)系起來。一個可計算問題被認為是一個原則上可以用計算機解決的問題，亦即這個問題可以用一系列機械的數(shù)學步驟解決，例如算法。理論簡介理論簡介計算復雜性理論（Computationalcomplexitytheory）是計算理論的一部分，研究計算問題時所需的資源，比如時間和空間，以及如何盡可能的節(jié)省這些資源。計算復雜性理論所研究的資源中最常見的是時間（要通過多少步才能解決問題）和空間（在解決問題時需要多少內(nèi)存）。其他資源亦可考慮，例如在并行計算中，需要多少并行處理器才能解決問題。時間復雜度是指在計算機科學與工程領域完成一個算法所需要的時間，是衡量一個算法優(yōu)劣的重要參數(shù)。時間復雜度越小，說明該算法效率越高，則該算法越有價值?？臻g復雜度是指計算機科學領域完成一個算法所需要占用的存儲空間，一般是輸入?yún)?shù)的函數(shù)。它是算法優(yōu)劣的重要度量指標，一般來說，空間復雜度越小，算法越好。我們假設有一個圖靈機來解決某一類語言的某一問題，設有X個字（word）屬于這個問題，把X放入這個圖靈機的輸入端，這個圖靈機為解決此問題所需要的工作帶格子數(shù)總和稱為空間。復雜度理論和可計算性理論不同，可計算性理論的重心在于問題能否解決，不管需要多少資源。而復雜性理論作為計算理論的分支，某種程度上被認為和算法理論是一種“矛”與“盾”的關系，即算法理論專注于設計有效的算法，而復雜性理論專注于理解為什么對于某類問題，不存在有效的算法。發(fā)展歷史發(fā)展歷史在20世紀50年代，Trahtenbrot和Rabin的論文被認為是該領域最早的文獻。而一般說來，被公認為奠定了計算復雜性領域基礎的是Hartmanis和Stearns的1960年代的論文Onthecomputationalcomplexityofalgorithms。在這篇論文中，作者引入了時間復雜性類TIME(f(n))的概念，并利用對角線法證明了時間層級定理（TimeHierarchyTheorem）。在此之后，許多研究者對復雜性理論作出了貢獻。期間重要的發(fā)現(xiàn)包括：對隨機算法的去隨機化（derandomization）的研究，對近似算法的不可近似性（hardnessofapproximation）的研究，以及交互式證明系統(tǒng)（Interactiveproofsystem）理論和零知識證明（Zero-knowledgeproof）等。特別的復雜性理論對近代密碼學的影響非常顯著，而最近，復雜性理論的研究者又進入了博弈論領域，并創(chuàng)立了“算法博弈論”（algorithmicgametheory）這一分支?；靖拍罨靖拍钣嬎隳Ｐ团c計算資源計算復雜性理論的研究對象是算法在執(zhí)行時所需的計算資源，而為了討論這一點，我們必須假設算法是在某個計算模型上運行的。常討論的計算模型包括圖靈機（Turingmachine）和電路（circuit），它們分別是一致性（uniform）和非一致性（non-uniform）計算模型的代表。而計算資源與計算模型是相關的，如對圖靈機我們一般討論的是時間、空間和隨機源，而對電路我們一般討論電路的大小。由邱奇-圖靈論題（Church-Turingthesis），所有的一致的計算模型與圖靈機在多項式時間意義下是等價的。而由于我們一般將多項式時間作為有效算法的標志，該論題使得我們可以僅僅**圖靈機而忽略其它的計算模型。判定型問題和可計算性我們考慮對一個算法問題，什么樣的回答是我們所需要的。比如搜索問題：給定數(shù)組A，和一個數(shù)s，我們要問s在不在A中（判定性問題，decisionproblem）。而進一步的，s如果在A中的話，s的位置是什么（搜索型問題，searchproblem）。再比如完美匹配問題（perfectmatching）：給定一個二分圖G=(V,E)，我們問是不是存在邊集E，使得二分圖中每個結點恰好屬于該邊集的一條邊（判定型問題）。而進一步的，E存在的話，E具體是什么（搜索型問題）。相關理論相關理論計算復雜性理論最成功的成果之一是NP完備理論。通過該理論，我們可以理解為什么在程序設計與生產(chǎn)實踐中遇到的很多問題至今沒有找到多項式算法。而該理論更為計算復雜性中的核心問題：P與NP的關系問題指明了方向。NP和P的定義在上面我們已經(jīng)知道，NP是指“在非確定性圖靈機上有多項式時間算法的問題”的集合，而P是指“在確定性圖靈機上有多項式時間算法的問題”的集合。這里我們都考慮的是判定型問題，即考慮一個語言L，我們要判斷一個字符串x是不是在L中。那么，一個等價的理解是：NP是指對在L中的x，有多項式長度的證據(jù)w，而且對語言(x,w)是有多項式時間算法的；而P是指對L中的x，有多項式時間算法判斷x在不在L中。舉個例子，就是考慮完美匹配問題、點集覆蓋問題和圖不同構問題。這三個問題都有圖論背影，問題的描述如下：完美匹配問題：給定圖G=(V,E)，找到邊的子集F?E，使得對任意的v∈V，存在唯一的e∈F，v∈e；點集覆蓋問題：給定圖G=(V,E)，和自然數(shù)k，找到點的子集U?V，使得對任意的e∈E，存在v∈U，v∈e，且|U|≤k；圖不同構問題：給定圖G=(V,E)，H=(U,F)，|G|=|H|。我們說G和H是同構的，是指?T:V→U，對任意的s,t∈V，滿足E(s,t)=F(T(s),T(t))（這里我們把邊集E看作V×V→{0,1}的映射）。理論實踐理論實踐計算復雜性的初衷是理解不同算法問題的難度，特別的是一些重要算法問題的困難性。為了確切的描述一個問題的困難性，計算復雜性的第一步抽象是認為多項式時間是有效的，非多項式時間是困難的。這基于指數(shù)函數(shù)增長速度的“違反直覺”的特性：如果一個算法的時間復雜性為2n，取輸入的規(guī)模是100，在運算速度是1012每秒的情況下，該程序將會運行年，幾乎是宇宙年齡。這為多項式時間被看作是有效時間提供了直觀上的證據(jù)。然而多項式的指數(shù)很大的時候，算法在實踐中也不能看作是有效的。如n10的多項式算法，取問題規(guī)模大小為1000，那么幾乎就是2100的大小。另一方面，即便一個問題沒有多項式算法，它可能會有近似比很好的近似算法，或有很好的啟發(fā)式算法（heuristics）。啟發(fā)式算法的特點是在理論上沒有精確的行為的分析，或者可以表明存在很壞的輸入，在這些輸入上運行很