1、計算復雜性的回顧Stephen A.Cook1早期的論文算法復雜性問題的前史大概可以追溯到艾倫圖靈在1937年的這篇論文，論文是論可計算數機器在判定問題中的應用。圖靈介紹了他著名的圖靈機，提出了使人信服的公式化觀點，這個觀點是有效的可計算函數。曾經這個想法正好被壓制了，對于可計算的不可能證據出現了可能。在同一篇論文中，圖靈提出了給定一個可預測的微積分的任意的一個公式，在有限的時間內沒有任何一種算法可以證明這個公式是可滿足的。在解釋什么樣的問題能被計算機解決或不能解決這個理論很好的發展之后，很自然的想到可計算函數的相關計算難度在哪。這就是計算復雜性問題。Rabin是第一批詳細的從事這類問題人之一

2、：f比g更難計算是什么意思？Rabin提供了抽象復雜性理論的基礎，這個理論被Blum和其他人所發展。第三篇論文是Alan Cobham寫的內在的計算難度。Alan Cobham強調“內在”，換句話說，他對獨立機器理論感興趣。他想知道乘法是否比加法難，并且他相信直到這個理論完全發展了，這個問題才能解決。Cobham也定義了和刻畫了函數的重要的類：這些函數在自然數內和有限時間內是可計算的，時間限制是輸入的十進制長度的多項式。另外三篇論文影響著以上作者和其他研究復雜性的工作者，他們是Yamada，Bennett，Ritchie。有趣的是Rabin，Stearns，Bennett和Ritchie同時都

3、是普林斯頓大學的學生。2早期的觀點和概念幾個早期的作者關心這個問題：什么是正確的復雜性度量？大多數人認為復雜性時間和空間是明顯的選擇，但是不能確定這些是唯一的或者正確的。比如，Cobham說和物理相關的概念的工作的一些測量可指導最滿意的分析。Rabin引入了可以使復雜性度量可滿足的公理。根據20多年的經驗觀點，我現在認為時間和空間，尤其是時間是最重要的復雜性度量。評價一個算法的效率，第一個能體現算法價值的應該是算法的運行時間。然而，近年來，并行時間和硬件資源越來越是度量復雜性的重要手段。另一個重要的復雜性度量是組合復雜性。這里假定函數f是把有限的位字符串轉化為有限的位字符串，對于所有長度為n的

4、輸入，f的復雜度C（n）是所有組合中最小的復雜度。這個普通的測量和計算時間緊緊相關，也發展成為理論。Cobham提出的另外一個問題是在計算問題中，“步”由什么組成？對于度量一個算法的可計算時間，哪種計算機模型是正確的模型？多圖靈機在這篇文獻中經常被用到，但是他們被算法的執行效率所局限。比如，沒有強制性的原因說存儲介質必須是線性磁帶。為什么不是平坦的矩陣或是樹型？為什么不允許隨機存儲記憶？事實上，自1960年來，好多計算模型被提出。因為真實的計算機有隨機存儲記憶，很自然的被用到這個模型中。但是怎么用是一個很棘手的問題。如果機器在一個步內能存儲整型，對他們的大小必須要限制。（如果2被平方100次，

5、結果將有2的100次方位，這些位能存儲世界上所有已存在的存儲介質。）我在文獻19里面提出了RAMs，每次logx的代價都能得到，x可以存儲也可以查找。一個流行的隨機存儲模型是Aho，Hopcroft和Ullman在文獻3里面提出的，每次涉及到整型的操作都有一個單元的代價，但是不能達到不合理的大?。ū热纾@些數字的大小被固定多項式限制，這些多項式是輸入的長度）?；蛟S最滿意的計算模型是舍恩洛克的存儲修正機器，這個機器可以被看成是圖靈機，它有自己的存儲機構，或者被看做一個單元代價RAM，它在每一個步只能復制，增加或存儲或查找。舍恩洛克的機器。對于我來說意味著大多數機器都能在每一步做有限制的工作。困難

6、是可能只有一點強大。（看第三部分的大數乘法）。回到Cobham的問題，什么是“步”。我認為在最近的20年內沒有一個明確的答案。幸運的是，完全的計算模型在可計算時間內都沒有很大的區別?？偟膩碚f，每一個都能模仿另一個。（有些這方面的爭論在文獻37中）。在這些最主要的隨機存取模型中，只有log計算時間這個重要因素正在被討論。這導致了在1965年形成的最終重要的概念：在輸入的多項式時間內可以解決的問題的分類的定義。在多項式時間和指數時間的特征的算法早在1953年由von Neumann提出。然而，這個類別沒有被正式定義和研究直到Cobham在1964年提出函數的類（看第一部分）。Cobham指出這個類

7、被很好的定義，和選擇的計算模型無關，在回歸函數理論中給它描述了一個定義。Edmonds第一次在出版的論文里提出在多項式時間的計算是比較容易的，他認為多項式時間的算法是好的算法。Karp引入了現在標準符號P，表示可認識的多項式時間類的字符串集合。從1970年早期開始，P在這個領域代表易處理的問題被人們廣泛接受。不是立即很明顯的知道這應該是正確的，因為一個算法的運行時間是多項式n的1000次是不可行的，相反的，誰的運行時間是指數2的0.0001n次在實際上是可行的。這好像是個經驗事實，然而，這個狠自然提出的問題在這樣一個運行時間內沒有最優化的算法。有最壞指數運行時間的最明顯實際的算法是線性規劃中單

8、一算法。在文獻75和76中試圖解釋展示這個問題，從某種意義上說，平均運行時間很快，但是Khachian用其他算法展示了在P時間內的線性規劃也是值得重視的。因此，我們大部分的論文沒有違背P相當于可解決的問題這個觀點。3.時間上界計算機科學研究的內容包括設計和分析的大規模數據高效算法。（從計算復雜性的角度來看）特別重要的算法必須以某種方式，他們通常提供一個解決一個重要問題，令人驚訝的簡單或快速的方法。下面我列出一些更有趣的自1960年發明。（順便說一句，猜測是有史以來最重要的算法是件有趣的事；無疑算術運算+， - *和 - 十進制數字是基本的算符，我認為快速排序和查找，高斯消去法及歐幾里得算法和單

9、純形算法是比較重要的自1960年以來。）參數n是指對輸入的大小和時間界限是最壞情況下的時間范圍，并適用于一多帶圖靈機除特別注明（或任何合理的隨機存取機）。快速傅里葉變換，要求為O（nlogn）的算術運算，是科學計算中最常用的算法之一； （2）大數乘法。最基本的方法需要O（n 2）的位操作乘以兩個N位數字。 1962年Karatsuba和Ofman 41發表的方法只需要為O（nl.59）復雜度,之后不久Toom84，展示了如何構建（任意小> 0）大小為O（）布爾電路，以開展乘法運算。我是當時在哈佛大學畢業的學生，由Cobham的問題啟發“是乘法難度比加法大？”我是天真地試圖證明乘法，乘法需

10、要一個圖靈機（n2）的步驟。Toom提交的文件給了我很大的驚喜。在Aanderaa 22幫助下，我減少乘法的復雜性，即使用的“在線”圖靈機需要（nlogn /（loglogn）2）步驟；我也指出，Toom的方法可適應乘法圖靈機，需要O（）的步驟，在這一點上Toom與我肯定有相同的看法。目前運行速度最快的漸進圖靈機在數值乘法中異步運行時間為O（nlognloglogn），是由Sch6nhage和Strassen 70（1971年）采用快速傅立葉變換的設計。然而，Sch6nhage 69最近由一個復雜的參數修改，他的存儲設備（見第2節）乘法運行的時間為為O（n）（線性時間！）。我們不得不得出這樣的

11、結論要么乘法是比我們想象的更容易或Sch6nhage的機器作弊。（3）矩陣乘法。最明顯的方法需要）算術操作，將兩個nxn的矩陣，并嘗試進行了證明，這在1950年和1960年最佳方法的。當Strassen的81(1969年)發布了他的方法只需要4.7Tm運算時間。相當多的工作一直致力于減少2.81指數，目前已知的最佳時間是O（112496）操作，是科珀和Winograd 24做出的。還有很多改進的空間，因為眾所周知的下界是2n2 - 1（見13）（4）一般無向圖的最大匹配。這也許是第一個問題明確的顯示誰的成員在P中的算法比較復雜。Edmonds有影響力的論文27給出了結果并討論了多項式的時間算法

12、（參見第二部分）。他指出簡單的滿足雙邊的情況并不適用一般的無向圖。（5）確認素數?，F在主要問題是確定這個問題是不是在P中。換句話說，是否有一個算法總能告訴我們輸入的n位數字是不是一個素數，一個固定的有界n項多項式是否停止？Gary Miller 53 (1976年)表明，有這樣的算法，其有效性取決于擴展的黎曼算法。Solovay 和Strassen 77發明了一種快速的蒙特卡羅素數識別算法，但是如果輸入的數字是合成的那么有一定的小概率會誤判?，F在知道的最好的證明算法是Adleman, Pomerance, and Rumely 2提出的，時間復雜度為，稍微差于多項式算法。由于這方面的變化，H.

13、 Cohen 和 H.W. Lenstra Jr. 17經常可以處理多達一百個十進制數大約需時45秒鐘。最近，在類P中三個重要的問題已經被證明了。第一個問題是線性規劃問題由Khachian 43（參見55）于1979年證明。第二個問題是判定兩個圖的度數之多d是同構的，由Luks 50 于1980年證明（該算法是多項式的頂點固定d，但是指數在d）。第三個問題是考慮有理系數多項式因子，這被Lenstra,Lenstra, and Lovasz 48 在1982年，證明是含一個變量的多項式。Kaltofen's result 39, 40證明它可以被化為一般的變量固定的多項式。所有重要時間復

14、雜度或者空間復雜度的下界都是基于“對角線的理論”。圖靈和與他同期的人使用對角線理論去證明些問題而不是通過算法可解。他們也用1960年之前確定的多層次可計算0-1函數。在1960年，Rabin 60證明了任何合理的復雜性措施，如計算時間或空間（內存），允許充分增加時間、空間等條件，也允許更多的0-1計算。大約在同一時間，Ritchie在他的論文65中在空間允許的數量內，定義一個特定的功能層次結構（他證明了0-1函數的平凡性）。之后，Rabin的結論被Hartmanis 和 Stearns 37更詳細研究用于時序多帶圖靈機，被Stearns, Hartmanis, and Lewis 78用于空間

15、復雜度。上述的層次結構的結果可用來各處計算特定函數所需的時間和空間的下限，但這些函數看起來是“人為的”。例如，很容易看到函數f(x,y),在輸入x后經過計算輸出y，不能再時間內算出。知道1972年，Albert Meyer and Larry Stockmeyer 52證明了正則表達式的等價問題需要指數空間，因此，指數時間，一個對一般模型平凡的更低的下界，一個“自然的”問題被發現（自然指的是有趣，而不是關于計算機的）。4.1 非人為可決定的問題被證明是不可解的綜合考慮到上述因素得出的分層結果，給出了計算特定函數所需時間和空間的下界。但是，所有這樣的函數看起來都是“勉強”的。例如，需經過 (|x

16、|+|y|)2 個步驟的計算，功能為基于輸入y計算x從而給出輸出的第一個數字的函數f(x,y)，顯然不可能在 (|x|+|y|)2 的時間內完成計算。直到1972年，Albert Meyer和Larry Stockmeyer證明了對于帶有平方的正則表達式需要指數級的空間和指數級的時間，即發現了對“自然的”問題計算的一般模型的重要下界（自然的指的是感興趣的感覺，而不是指計算機）。在那之后不久，Meyer找到了在時間方面非常確定的下界，這個下界需要利用一種叫做WSIS確定的形式可解方法（弱一元二階繼承理論）來判斷其正確性。他證明了任何一臺運行時間在某個確定的指數時間（2n，22n，222n等）以內

17、的計算機不能正確地判斷WSIS。Meyer的博士生，Stockmeyer繼續計算，得出結論：如果一種邏輯電路（可以理解為計算機）想要正確判斷任意一個長度為616個字符的WSIS公式的正確與否，那么它需要擁有超過10123個門電路。如果把10123這個數字想像成10123個質子，那么這些質子將填滿目前人類已知的宇宙。這是一個對不可解性很有說服力的證明。從Meyer和Stockmeyer開始，涌現出大量關于可解的形式理論的復雜性的下界的討論（相見參考文獻29和80）。其中最值得關注的一種理論是由Fischer和Rabin提出的，需要雙指數級的時間作為下界，用以解決Presburger算術問題（一種

18、自然數相加的理論）的理論。這與利用這種方法得到的已知最佳時間上界，三指數級時間，相差不多。最佳的空間上界是雙指數級的。除了上面的一些成績，證明更小規模復雜性問題的下界的記錄，同樣令人震驚。事實上，對于通常意義上的自然界存在的NP問題模型并沒有非線性時間的降低，特別是對列出的300個問題。當然，我們可以從反面證明，現有的NP問題，當給定k時，它的解時間是nk。然而，對于降低解空間下界，我們甚至不知道如何證明現有的NP問題在O(logn)的空間當中可以通過非線性圖靈機解決。這里討論的不包括那些自然界中許多問題的已知最好解空間是n的線性。 4.2 結構化的下界盡管我們對于證明有價值的通用計算機模型上

19、的具體問題的下界，幾乎沒有取得成績，但我們任然得到了關于“結構”模型的有價值結果?！敖Y構”這個表述是由Borodin引入的是用來描述在計算機環境下，對我們碰到問題的相應的操作。一個簡單的例子是n個數的排序問題。我們可以毫不費力的證明，如果假定計算機一次只能對一對數進行比較，那么解決這個問題至少需要nlogn次比較。這個下界的得到同圖靈機或者布爾循環無關；但是，假定除法是不被允許的，這個問題的結論能夠被擴展到任意的以隨機代價進入的機器。第二個比較巧妙的結構下界是由Strassen（1973）提出的，他在研究多項式插值時發現：假定只有算術運算是允許的，那么計算通過給定n個點的n-1維多項式的系數，

20、需要至少（nlogn）次乘法。有趣的是，Strassen的初始證明是依據一個有很深的代數幾何背景的Bezout的理論。直到最近，Baur和Strassen拓展了下界來說明，甚至計算通過n個點的多項式插值的中間系數，也需要至少（nlogn）次乘法。所有這些結構性結果的一些引人注目的地方是：結構下界接近已知的最好上界，并且已知的最好算法能夠通過結構模型得到的下界來完善。（注：例如基數排序，有些說法說它線性時間可解，解決它需要nlogn步，但是如果假定輸入的數字有足夠的數位，那么兩種說法卻是截然不同的）。4.3 時空復雜度下界另一個陷入僵局的對時間和空間的下界的證明是：如何證明時間下界在一個小的范圍

21、之內。Cobham在1966第一個證明了類似的結論，當時他得出的結論是，用非線性圖靈機求解n位完全平方的時空復雜度，至少是n2。（求解有n個符號的回文也是同樣的情況。）這里，輸入是通過一個雙向的只讀磁帶，而掃描圖靈機可用的工作磁帶的數目的平方作為空間。因此，假如空間被限定在log3n（足夠使用）內，那么時間一定至少是（n2/log3n）步。Cobham的結論的缺陷是，盡管非線性圖靈機是一個分別衡量計算時間復雜性和空間復雜性的好的模型，但當把時間和空間一起考慮的話，它的限制太多了些。例如，如果允許可以從兩端同步的掃描輸入磁帶，那么回文問題顯然可以在2n步和常數的空間內被解決。通過證明對從1到n2

22、范圍內的n個數進行排序，至少需要(n2/log n)的時空復雜度，Borodin和我部分的修正了這一缺陷。這個證明適用于任何“一般時序機”，其中“一般時序機”包括多輸入端甚至包括可以隨機進入輸入磁帶的非線性圖靈機。不幸的是我們的證明需要許多輸出位，而且是否存在適用于相似的一系列問題的一個近似的下界，仍然是一個值得探討的開放性課題。例如，是否所有的n輸入數是不同的。（最近，我們對于排序問題的下界獲得了微小的改進。）4.4 NP完全問題可以肯定NP完全理論是算法復雜性理論中最重大的進步。由于該理論已經很有名，并且已被寫入教科書，所以在此我不再贅述。Garey和Johnson的著作是了解該理論的上佳

23、選擇。NP問題包括所有利用非確定性圖靈機在多項式時間內可被認知的集合。據我所知，1962年James Bennett在他的博士論文4中第一次定義了數學等價類的概念。Bennett使用了“基本的積極擴展關系”定義這種歸類，并且在他的定義中使用了邏輯量詞，而不是計算機器。我讀過他的論文的這部分之后意識到，他的分類方法和現在為人們所熟悉的NP問題的定義在本質上是相同的。在我1971年發表的論文18中，我使用了符號 +（在Cobham的 分類之后），而Karp在他1972年發表的論文42中給出了現在對該分類的稱呼：NP。同時，完全獨立于形式方面的發展，早在1965年Edmonds就對于有著“完善描述”

24、的問題進行了非正式的討論，即給出一個本質上等同于NP的概念。在1971年，我提出了NP完全的概念并且證明了3個可滿足性條件和子圖問題是NP完全的。一年后，Karp證明了21個問題是NP完全的，從而有力地證明了這一理論的重要性。在前蘇聯，獨立于這一理論，Leonid Levin（現在任教于波士頓大學）在稍晚一些定義了一個相似的（更嚴格的）概念，并且證明了在他的理論中6個問題是完全的?！八阉鲉栴}”這一非正式的概念是蘇聯文學中的標準，并且Levin稱他研究的問題為“通用搜索問題”。NP這類問題包括了大量商業和工業中的實際應用問題（參見31）。證明一個NP問題是NP完全的就是證明這個問題是非P的（不存

25、在一個在多項式時間內可解的算法）除非每個NP問題都是P的。因為后面的條件將會引起計算機科學的改革，所以NP完全的實際效果就是下界。這就是我在下界這部分介紹這一理論的原因。4.5 #P完全問題NP完全是和集合有關的概念。通常情況下，欲證明一個集合是NP完全的可以理解為證明這個集合是不可解的。但是存在著大量與非NP完全的證明可能相關的不可解的函數。于是Leslie Valiant 86,87定義了#P完全的概念來補救這個問題。一個函數被證明是#P完全的，則此函數是不可計算的，同樣地，一個集合被證明是NP完全的，則此集合是不可識別的；也就是說，如果一個#P完全的函數可以在多項式時間內被計算，那么P=

26、NP。Valiant 給出了很多#P完全函數的例子，其中最有趣的應該是整數矩陣的永久式。永久式的定義和行列式的定義很相近，但是行列式可以利用高斯消去法輕松得到結果，而在過去的一百多年里很多對永久式計算的可行方法的探索都以失敗告終。當Valiant證明永久式問題是#P完全問題之后，對于上述探尋失敗的原因，他第一次給出了令人信服的解釋。5概率算法在計算實踐中使用隨機數來模擬或近似隨機過程是很自然的，而且已很好地確立起來。然而，隨機輸入在解決確定的組合問題中非常有用的思想，在滲透到計算機科學界中進展卻要慢得多。這里我將把注意力限制于概率(硬幣投擲)多項式時間算法，它們(在一個合理的意義下)求解不知道

27、有確定多項式時間算法的問題。第一個這樣的算法似乎是由貝勒卡姆普于1970年給出的，該算法用于對p個元素的域GF(p)上的一個多項式f進行因式分解。貝勒卡姆普的算法在關于f的次數以及logp的多項式之下的時間運行，而且它至少以一半的概率找出f的正確因式分解，否則它以失敗告終。由于這個算法可以被重復任意次而且出錯事件是獨立的，因而這個算法實際上總是在一個可行數量的時間中進行因式分解。一個更卓越的例子是由索羅偉和斯特拉森 (1974年投稿)給出的識別質數的算法。這個算法以輸入m的長度的多項式時間內運行，輸出或者是“質數”或者是“合數”。如果m事實上是質數，則輸出肯定是“質數”，但如果m是合數，則以至

28、多一半的概率，答案也可能是“質數”。對于一個輸入m，這個算法可以重復任意多次且有獨立的結果。因此，如果答案正是“合數”，則用戶知道m是“合數”；如果在比如說100運行次之后，答案一致地是“質數”，則用戶有m是質數的很好證據，因為任何固定的合數m將以很小的概率(小于2-100)給出這樣的結果。拉賓給出了其性質類似于上述之一的一個不同的概率算法，并且發現它在計算機試驗時非?？?。在幾分鐘之內，數2400-593就被標識為(大概是)質數。里維斯特(Rivest)、薩米爾(Shamir)和阿德爾曼(Adleman)在他們1978年關于公開鑰加密系統里程碑式的論文中，提出了概率質數測試程序的一個有趣應用。

29、他們的系統要求很大的(100位數字)隨機質數。他們提出，使用索羅偉斯特拉森的方法測試隨機的100位數字，直到發現在上面概述的意義下它大概是質數為止。實際上，通過在第3節中提到的科恩和里斯特拉新的高次冪確定的質數測試程序，一旦發現一個隨機的100位數字“大概是質數”，如果確實地知道是重要的話，就可以在大約45秒內進行測試以進行證實。在索羅偉和斯特拉森的意義下具有多項式和概率識別算法的集合類在參考文獻中稱為R(或有時稱為RP)。因此一個集合在R中當且僅當有一個概率識別算法，它總是在多項式時間內停止，而且對于不在R中的輸入決不出錯，而對于R中的每個輸入，它以至少一半的概率每次運行給出正確答案。因此，

30、合數集合在R中，而且一般地PRNP，還有其他在R中的有趣集合，但不知它們是否在P中，例如，施瓦茨(Schwartz)證明，其元素為許多變量的多項式的非奇矩陣集合在P中。該算法以隨機小的整數值計算多項式并且計算結果的行列式(行列式顯然不能能行地直接加以計算，因為所計算的多項式一般說來將有指數級多的項)。R=P是否成立是個有趣的開放問題。在哲學的基礎上猜測答案肯定這一點是有趣的，即隨機的硬幣投擲當要尋求的答案是明確定義的是或不是時，不應有太多用處。有關的問題是，概率算法(證明一個問題在R中)對于所有實用目的而言是否和一個確定算法一樣好。畢竟，概率算法可以使用在大多數計算機上都可利用的擬隨機數生成來

31、運行，且2-100的出錯概率是可以忽略的，蹊蹺之處在于擬隨機數生成程序并不產生真正隨機的數，因此沒有人知道對于一個給定的概率算法它們是否有效.事實上，經驗表明它們似乎有效。但如果它們總是有效，則由此得出R=P，因為擬隨機數是確定生成的，因此真正的隨機性將毫無幫助。另一個可能性是使用一個物理過程例如熱噪聲來生成隨機數。但是在科學原理上，真正會是怎樣的隨機的本質也是一個開放的問題。現在讓我通過提及關于類R的阿德爾曼的一個有趣定理來結束這一節。容易看出，如果一個集合在P中，則對每個n，有一個其大小以n的一個固定多項式為界的布爾線路，它確定長度為n的一個任意的串是否在集合中。阿德爾曼證明的是，對類R來

32、說，同一結果成立。因此，例如，對每個n，有一個小的“計算機線路”，它正確地并迅速地測試n位數字的數是否質數。其蹊蹺之處在于這些線路并非對n都一致，而且事實上對于100個數字的情況，想像出如何構造這個線路可能不是能行的。隨著VLSI技術（在一塊芯片上置入一個或多個處理器）的來臨，很自然地就會想到未來的計算機由成千上萬個處理器組合而成，并且它們并行地處理簡單的問題。盡管這種類型的非常大的通用機沒有被建造出來，但建造這樣的通用機的項目正在進行。這激發了一個非常可喜的計算復雜性的分支機構的最新發展：大規模同步并行計算的原理，在連續的復雜性理論中處理機的個數用參數H(n)(H指的是硬件)表示；同樣空間用

33、S(n)表示。通常H(n)是n的一個固定的多項式。正如有許多相互競爭的順序模式，有相當數量的并行計算模型被提出。然而，這里有兩個主要的競爭者。第一個競爭者是一類通過本身共同持有的隨機存取內存將大量的處理器連接在一起，以此來分享內存。許多已經發表的并行算法就是這樣的模型，因為真正被建造的并行機器可能就是這樣的。然而，根據數學原理這些模型并不令人滿意，因為他們很多的詳細說明是隨意的：如何解決共享內存中的讀與寫沖突？對于每個處理器的基本操作是什么？一個控制logH(n)時間的單元應該對共同的內存進行存取嗎？因此，我比較喜歡由Borodin提出的比較清晰的模型。該模型的并行計算機是由統一的無環布爾電路

34、的邏輯電路組成。例如Bn有n個輸入，那么H(n)就是Bn的門數。T(n)（并行計算時間）就是電路Bn的深度（例如，最長路徑的長度就是從一個輸入到一個輸出）。這個模型部分證明了用布爾電路建造真正機器（包括共享內存機）的猜想。此外，最小布爾尺寸和深度需要計算一個函數是一個自然數學問題，并且很早就被認為有并行計算理論存在的影子。幸運的是，該理論的硬件H(n)的最小值和并行時間T(n)并沒有廣泛用于各種不同的并行計算機模型的競爭中。特別地，這里有一個一般事實對于所有的模型都成立。該事實是有Pratt和Stockmeyer于1974年提出的，并將其稱之為“并行計算原理”，也就是一個問題可以在T(n)的多

35、項式時間內有一臺并行機（硬件不限）器找到解，當且僅當它可以被一套時序機在T(n)的多項式空間內被解決。并行計算的一個基本問題是：哪些問題在使用多個處理器而不是單個處理器時可以解決的更快？Nicholas Pippenger通過定義可以在并行計算機上得以解決問題的階（現在被稱為NC，即Nick's class）劃分出這些問題。并且這臺并行計算機的硬件的數量在可接受的范圍內。幸運的是NC階任然與特別是并行計算機模型選擇的相同，并且很容易看出NC是FP在多項式時間內計算序列的一個子集。我們上面的問題可以轉變為：哪些問題既屬于FP也屬于NC？可以想象（盡管不可能）NC=FP，因為證明NC!=FP需要在計算復雜性理論上有所突破。由于我們不知道如何去證明函數f在FP中但卻不在NC中，接著最好的事就是證明f在log空間中對于FP是完備的。這個問題的模擬證明是一個NP完全問題，并且具有勸阻為函數f尋找超快速并行算法的實際效果。這是因為如果f在log空間中對FP是完備的并且f也在NC中，那么FP=NC，這將是一個巨大的驚喜。相當一部分進展是在FP問題分類上，這些問題是否在NC中，或者在log空間上對于FP是否是完