計算複雜性概覽

Stephen A. Cook University of Toronto

作者目前地址： Stephen A. Cook, Department of Computer Science, University of Toronto, Toronto, Canada M5S 1A7.

允許免費複製本材料的全部或部分內容，前提是複製不得用於直接商業利益，並註明版權聲明、出版物的標題和其日期，並聲明複製已獲得 Association for Computing Machinery 的許可。否則，複製或重新出版需要付費和/或特定許可。 © 1983 ACM 0001-0782/83/0600-0401 $00.75

摘要： 本文概述了計算複雜性的歷史。重點放在定義問題的內在計算複雜性以及證明問題複雜性的上下界等基本議題。本文還討論了機率計算和平行計算。

這是關於計算複雜性的第二次 Turing Award 演講。第一次由 Michael Rabin 在 1976 年發表。回顧 Rabin 那篇出色的文章 [62]，讓我印象深刻的是該領域自那以來已經有多少活動。在這篇簡短的概覽中，我想提及從該學科大約始於 1969 年以來，對我而言最重要和有趣的成果。在這樣一個龐大的領域中，主題的選擇不可避免地帶有個人色彩；然而，我希望納入那些無論按照任何標準都具有基礎性地位的論文。

1. 早期論文

該學科的史前史可以追溯到 Alan Turing。在他 1937 年的論文《論可計算數及其在判定問題上的應用》[85] 中，Turing 介紹了他著名的 Turing 機，它提供了（直到當時）對有效（或演算法上）可計算函數概念最令人信服的形式化。一旦這個概念被精確確定，關於電腦的不可能性證明就成為可能。在同一篇論文中，Turing 證明了沒有任何演算法（即 Turing 機）可以在有限步驟內，對給定的任意謂詞演算公式，判定該公式是否可滿足。

在解釋了哪些問題可以和不可以由電腦解決的理論充分發展之後，自然會問及可計算函數的相對計算難度。這就是計算複雜性的主題。Rabin [59, 60] 是最早明確提出這個普遍問題的人之一（1960 年）：什麼意思說函數 f 比函數 g 更難計算？Rabin 提出了一個公理框架，為 Blum [6] 和其他人發展的抽象複雜性理論提供了基礎。

第二篇早期（1965 年）有影響力的論文是由 J. Hartmanis 和 R. E. Stearns 合著的《論演算法的計算複雜性》[37]。這篇論文被廣泛閱讀並為該領域命名。論文引入了由多帶 Turing 機計算時間定義的重要複雜性度量概念，並證明了層次定理。論文還提出了一個至今未決的有趣問題：任何無理代數數（例如 √2）是否可以在實時計算，也就是說，是否存在一個 Turing 機以每 100 步輸出一個數位元的速度列印出該數字的十進制展開？

第三篇基礎論文（1965 年）是 Alan Cobham 的《函數的內在計算難度》[15]。Cobham 強調了「內在」一詞，他感興趣的是一個獨立於機器的理論。他問乘法是否比加法難，並認為在理論得到妥善發展之前無法回答這個問題。Cobham 還定義並刻畫了重要的函數類別，他稱之為 P，這些函數在自然數上的計算時間受限於輸入十進制長度的多項式。

另外三篇影響上述作者以及其他複雜性研究者（包括我自己）的論文是 Yamada [91]、Bennett [4] 和 Ritchie [66]。值得注意的是，Rabin、Stearns、Bennett 和 Ritchie 大約同時都在 Princeton 讀書。

  • Michael Rabin 和 Dana Scott 在 1976 年共享了 Turing Award。
  • 見 Hartmanis [36] 獲得一些有趣的個人回憶。
  • 見 [56] 和 [74] 獲得稍微改進的下界。

2. 早期議題與概念

一些早期的作者關注的問題是：什麼是正確的複雜性度量？大多數人提到了計算時間或空間作為顯而易見的選擇，但並不確定這些是唯一或正確的選擇。例如，Cobham [15] 建議：「...與物理工作概念相關的某種度量[可能]會導致最令人滿意的分析。」 Rabin [60] 引入了複雜性度量應滿足的公理。憑藉 20 年的經驗，我現在認為很清楚，時間和空間——尤其是時間——確實是最重要的複雜性度量之一。演算法效率的第一個衡量標準似乎就是其運行時間。然而，最近越來越清楚的是，平行時間和硬體大小也是重要的複雜性度量（見第 6 節）。

另一個重要的複雜性度量，某種程度上至少可以追溯到 Shannon [74]（1949 年），是布林電路（或組合電路）複雜性。在這裡，為了方便，假設函數 f 將有限位元串映射到有限位元串，而 f 的複雜性 C(n) 是計算所有長度為 n 的輸入的最小布林電路的大小。這個非常自然的度量與計算時間密切相關（見 [57b]、[68b]），並擁有自己發展完善的理論（見 Savage [68a]）。

Cobham [15] 提出的另一個問題是計算中的「一步」構成什麼。這相當於問什麼是衡量演算法計算時間的正確計算機模型。多帶 Turing 機在文獻中常用，但從演算法有效實現的角度來看，它們具有人為限制。例如，存儲介質沒有令人信服的理由必須是線性磁帶。為什麼不能是平面陣列或樹狀結構？為什麼不允許隨機存取記憶體？

實際上，自 1960 年以來，已經提出了相當多的計算機模型。由於實際計算機具有隨機存取記憶體，將其納入模型中似乎很自然。但如何做到這一點成為一個棘手的問題。如果機器可以在一步中存儲整數，那麼必須對其大小加以限制。（如果數字 2 被平方 1000 次，結果將有 2^1000 位元，這是世界上現有所有存儲介質都無法存儲的）。我在 [19] 中提出了帶費用的 RAM 模型，每次存儲或檢索數字 x 時，成本（步驟數）約為 log |x|。這有效，但不是完全令人信服。一個更受歡迎的隨機存取模型是 Aho, Hopcroft, and Ullman 在 [3] 中使用的模型，其中涉及整數的每個操作都有單位成本，但不允許整數變得過大（例如，它們的大小可以被輸入大小的某個固定多項式限制）。可能數學上最令人滿意的模型是 Schönhage 的存儲修改機 [69]，它可以被看作是構建自己的存儲結構的 Turing 機，或者是一個單位成本的 RAM，它只能在一步中複製、加一或減一，或者存儲或檢索。Schönhage 的機器是 Kolmogorov-Uspenski 在更早之前 [46]（1958 年）提出的機器的輕微推廣，對我而言，它似乎代表了可以在一步內完成有限工作量的最通用機器。問題是它可能有點過於強大。（見第 3 節「大數乘法」）。

回到 Cobham 的問題「什麼是一步」，我認為在過去 20 年裡已經變得清楚的是，沒有一個單一明確的答案。幸運的是，競爭性的計算機模型在計算時間上差異不大。總的來說，每個模型最多可以通過平方計算時間來模擬另一個（關於這一點的一些早期論證見 [37]）。在領先的隨機存取模型中，只有一個 log 計算時間因子有關。

這引出了 1965 年發展的最後一個重要概念——識別出計算時間受限於輸入長度的多項式的問題類別。多項式時間演算法和指數時間演算法之間的區別早在 1953 年就由 von Neumann [90] 提出。然而，這個類別直到 Cobham [15] 在 1964 年引入類別 P（見第 1 節）才被形式化定義和研究。Cobham 指出，這個類別是明確定義的，獨立於所選的計算機模型，並給出了函數理論風格的特徵。多項式時間可計算性大致對應於易處理性的觀點，最早由 Edmonds [27] 在印刷品中表達，他將多項式時間演算法稱為「好的演算法」。目前標準的符號 P 用於表示可由多項式時間識別的字串集合，這是後來由 Karp [42] 引入的。

自 1970 年代初以來，P 與易處理（或可行）問題的識別已在該領域普遍接受。為什麼會如此並非顯而易見，因為運行時間為 n^100 的演算法顯然不可行，反之，運行時間為 2^0.01n 的演算法在實踐中可能可行。然而，這似乎是一個經驗事實，即自然出現的問題沒有運行時間如此極端的最佳演算法。最值得注意的具有指數最壞情況運行時間的實用演算法是線性規劃的 simplex 演算法。Smale [75, 76] 試圖解釋這一點，他表明在某種意義上，平均運行時間很快，但同樣重要的是要注意 Khachian [43] 表明線性規劃可以使用另一種演算法納入 P 中。因此，我們的普遍論點，即 P 等同於可行問題，並未受到違反。

  • 見 [31]，pp. 184-186，關於這一點的討論。

3. 時間上界

計算機科學研究的很大一部分包括設計和分析大量的有效演算法。從計算複雜性的角度來看，重要的演算法必須以某種方式特別；它們通常提供了一種驚人快速的方法來解決一個簡單或重要的問題。下面我列出了自 1960 年以來發明的一些比較有趣的演算法。（順帶一提，猜測有史以來最重要的演算法是什麼很有趣。當然，十進制數字的算術運算 +、-、× 和 ÷ 是基礎。之後，我建議快速排序和搜索、Gaussian elimination、Euclidean algorithm 和 simplex 演算法作為候選。）

參數 n 指的是輸入的大小，時間界限是最壞情況時間界限，適用於多帶 Turing 機（或任何合理的隨機存取機），除非另有說明。

  1. Fast Fourier Transform [23] 需要 O(n log n) 次算術運算，是科學計算中最常用的演算法之一。
  2. 大數乘法。小學方法需要 O(n^2) 位元運算來乘以兩個 n 位數。1962 年，Karatsuba 和 Ofman [41] 發表了一種只需 O(n^log_2 3) 步的方法，其中 log_2 3 ≈ 1.59。不久之後，Toom [84] 展示了如何構造大小為 O(n^1+ε) 的布林電路，用於任意小的 ε > 0 的乘法。我當時在 Harvard 讀研究生，受到 Cobham 的問題「乘法比加法難嗎？」的啟發，天真地試圖證明乘法在多帶 Turing 機上需要 Ω(n^2) 步。Toom 的論文讓我非常驚訝。在 Stal Aanderaa [22] 的幫助下，我退而求其次，證明了使用「線上」Turing 機進行乘法需要 Ω(n^log_2 3 / (log log n)^c) 步。* 我在我的論文中還指出，Toom 的方法可以應用於多帶 Turing 機，以在 O(n^1+ε) 步內進行乘法，我相信這對 Toom 來說並不意外。目前在多帶 Turing 機上進行數字乘法的最快漸近運行時間是 O(n log n log log n)，由 Schönhage 和 Strassen [70]（1971 年）使用 Fast Fourier Transform 設計。然而，Schönhage [69] 最近通過一個複雜的論證表明，他的存儲修改機（見第 2 節）可以在 O(n) 時間內（線性時間！）進行乘法。我們被迫得出結論，要麼乘法比我們想像的容易，要麼 Schönhage 的機器作弊了。
  3. 矩陣乘法。顯而易見的方法需要 n^3 次算術運算來乘以兩個 n × n 矩陣，在 1950 年代和 1960 年代曾嘗試證明這種方法是最佳的。當 Strassen [81]（1969 年）發表了他的只需 n^log_2 7 ≈ n^2.81 次運算的方法時，令人驚訝。在降低指數方面已經投入了大量工作，目前已知最佳時間是 O(n^2.37) 次運算，由 Coppersmith 和 Winograd [24] 完成。仍有很大的進步空間，因為已知最佳下界是 2n^2 - 1（見 [13]）。
  4. 一般無向圖中的最大匹配。這可能是第一個被明確證明在 P 中，但其在 P 中的成員資格需要一個困難演算法的問題。Edmonds 那篇有影響力的論文 [27] 給出了一個 O(n^3) 時間的演算法，其中 n 是頂點數。* 他還指出，簡單的增廣路徑概念，對於二部圖有效，對於一般無向圖無效。
  5. 質數識別。這裡的主要問題是這個問題是否在 P 中。換句話說，是否存在一個演算法，它總是告訴我們任意 n 位輸入整數是否是質數，並在受輸入 n 的某個固定多項式限制的步驟數內停止？Gary Miller [53]（1976 年）表明存在這樣一個演算法，但其有效性取決於擴展 Riemann 假設。Solovay 和 Strassen [77] 設計了一個快速 Monte Carlo 演算法（見第 5 節）用於質數識別，但如果輸入數是合數，該演算法有很小的機會錯誤地說它是質數。已知最佳可證明確定性演算法是由 Adleman, Pomerance, and Rumely [2] 完成的，運行時間為 n^c/log log n，這比多項式時間稍微差一些。H. Cohen 和 H. W. Lenstra Jr. [17] 的一個變體可以在大約 45 秒內常規處理高達 100 位十進制數字。最近三個重要的問題已被證明屬於 P 類別。第一個是線性規劃，由 Khachian [43] 在 1979 年證明（見 [55] 獲得解釋）。第二個是判斷兩個度數最多為 d 的圖是否同構，由 Luks [50] 在 1980 年證明。（對於固定的 d，演算法在頂點數上是多項式，但在 d 上是指數的。）第三個是分解有理係數多項式。對於單變量多項式，這由 Lenstra, Lenstra, and Lovasz [48] 在 1982 年證明。正如 Kaltofen 的結果 [39]、[40] 所示，它可以推廣到任意固定變數個數的多項式。
  • 這個下界已經被 [56] 和 [74] 輕微改進了。
  • Edmonds 的演算法需要 O(n^4) 時間。Pollock 提出了 O(n^3)。見 [31] pp. 141-142。

4. 下界

複雜性理論中真正的挑戰，以及將該理論與演算法分析區分開來的問題，是證明特定問題複雜性的下界。證明一個是非問題無論使用何種演算法都無法在 n、n^2 或 2^n 步內解決，這非常令人滿意。在證明下界方面取得了一些重要成功，但未決問題甚至更重要，也有些令人沮喪。

所有關於計算時間或空間的重要下界都基於「對角線論證」。Turing 和他的同時代人使用對角線論證來證明某些問題是不可演算法解決的。它們在 1960 年之前也被用於定義可計算的 0-1 函數的層次結構。1960 年，Rabin [60] 證明，對於任何合理的複雜性度量，如計算時間或空間（記憶體），充分增加允許的時間或空間總能計算更多 0-1 函數。大約同一時間，Ritchie 在他的論文 [65] 中根據允許的空間量定義了一個特定的函數層次結構（他證明了對於 0-1 函數這不是平凡的）。稍後，Rabin 的結果由 Hartmanis 和 Stearns [37] 詳細闡述了多帶 Turing 機的時間，並由 Stearns, Hartmanis, and Lewis [78] 闡述了空間。

4.1 證明不可行的自然可判定問題

上述層次結果給出了計算特定函數所需時間和空間的下界，但所有這些函數似乎都是「人為構造」的。例如，很容易看出，函數 f(x,y) 給出機器 x 在輸入 y 上運行 ( |x| + |y| )^2 步後的輸出第一個數位元，無法在時間 (|x|+|y|)^2 內計算。直到 1972 年，Albert Meyer 和 Larry Stockmeyer [52] 證明了帶有平方的正規表達式的等價問題需要指數空間，因此需要指數時間，才找到一個針對通用計算模型在「自然」問題上的非平凡下界（自然問題，例如，Grzegorczyk [35] 的意思是，它們是令人感興趣的，而非為證理論而構造的）。* 在此之後不久，Meyer [51] 發現了一個非常強的下界，關於判定一個名為 WSIS（successor 的弱單元二階理論）的可判定形式理論中公式真值所需的時間。他證明任何運行時間受限於固定數量的指數（2^n、2^2^n、2^2^2^n 等）的計算機都無法正確判定 WSIS。Meyer 的博士生 Stockmeyer 繼續計算 [79]，他證明任何正確判定長度為 616 的任意 WSIS 公式真值的布林電路或計算機必須擁有超過 10^125000 個閘。選擇 10^125000 這個數字是為了表示已知宇宙中可以容納的質子數。這是非常令人印象深刻的下界證明！

自 Meyer 和 Stockmeyer 以來，關於可判定形式理論計算複雜性的下界已經有了大量成果（見 [29]、[30] 和 [54] 的總結）。其中一個最有趣的結果是 Fischer 和 Rabin [30] 證明了判定 Presburger 算術（涉及加法的自然數理論）所需時間的雙指數下界。這並非巧合，因為該理論的已知最佳時間上界是三指數的 [54]。已知最佳空間上界是雙指數的 [29]。

儘管取得了上述成功，但在證明對小複雜性問題的下界方面，記錄令人沮喪。事實上，對於任何自然問題在通用計算模型上，目前沒有已知任何非線性時間下界在 P 中（見第 4.4 節），特別是對於 [31] 中列出的 300 個問題中的任何一個。當然，通過對角線論證，可以證明對於任何固定的 k，存在需要時間 n^k 的 NP 中的問題。然而，就空間下界而言，我們甚至不知道如何證明存在不能由離線 Turing 機在 O(log n) 空間內解決的 NP 問題（見第 4.3 節）。儘管事實是，在許多自然類別中，已知最佳空間上界基本上是關於 n 的線性。

  • 見 [35]。

4.2 結構化下界

雖然我們在證明針對通用計算模型的具體問題的有趣下界方面取得的成功很少，但我們確實對「結構化」模型獲得了一些有趣的結果。術語「結構化」由 Borodin [9] 引入，指的是計算機僅限於與手頭問題相關的某些操作。一個簡單的例子是排序 n 個數字的問題。可以毫不費力地證明（見 [44]），如果計算機只允許比較輸入，這至少需要 n log n 次比較。這個下界沒有說明 Turing 機或布林電路，但它已被推廣到單位成本隨機存取機，前提是不允許除法。

第二個非常優雅的結構化下界，由 Strassen [82]（1973 年）提出，指出多項式內插（即找到通過 n 個給定點的 n-1 次多項式的係數）需要 Ω(n log n) 次乘法，前提是只允許算術運算。這裡有趣的一部分是 Strassen 的原始證明依賴於 Bezout 定理，這是代數幾何中的一個深奧結果。最近，Baur 和 Strassen [83] 推廣了這個下界，證明即使是通過 n 個點的內插多項式的中間係數也需要 Ω(n log n) 次乘法來計算。

所有這些結構化結果的吸引力在於，下界與已知最佳上界（因此與已知最佳演算法）是接近的，並且已知最佳演算法可以在適用下界的結構化模型上實現。證明排序確實需要至少 n log n 步的下界在實踐中經常被引用。

4.3 時間-空間權衡下界

計算複雜性中的一個令人興奮的新方向是試圖在空間受限的假設下證明時間下界。Cobham [16] 在 1966 年證明了第一個這樣的結果，他證明了在「離線」機器上識別 N 位平方數所需的時間-空間乘積必須是 Ω(n^2)。* （對於線上機器也是如此）。在這裡，輸入寫在一個雙向讀取輸入磁帶上，使用的空間是工作帶上使用的單元數。因此，例如，如果空間限制在 O(log n)（這足以識別平方數），那麼時間必須是 Ω(n^2/log n)。

Cobham 結果的弱點在於，雖然對於單獨考慮計算時間或空間，多帶 Turing 機模型是可接受的，但當時間和空間一起考慮時，它過於受限。例如，如果允許兩個磁頭同時掃描輸入，顯然可以在 2n 步和恆定空間內識別回文。Borodin 和我 [10] 在我們證明了對 n 個整數進行排序需要時間-空間乘積 Ω(n^2) 時，部分彌補了這個弱點。這個證明適用於任何「通用順序機器」，包括許多輸入磁帶的離線 Turing 機，甚至對輸入磁帶的隨機存取。不幸的是，我們證明中的關鍵點是排序需要許多輸出，並且證明一個下界可以應用於集合識別問題（例如，識別所有輸入數字是否不同）仍然是一個有趣的未決問題。（我們對排序的下界最近在 [64] 中稍微改進了）。

  • 見 [35]。

4.4 NP 完全問題

NP 完全性理論無疑是計算複雜性中最重要的發展。我將在這裡簡單討論它，因為它現在已廣為人知，並且是教科書的主題。特別是，Garey 和 Johnson 的書 [31] 是一本 excellent 的入門讀物。

NP 類別包含所有可由非確定性 Turing 機在多項式時間內識別的集合。就我所知，第一個數學上等價的類別是由 James Bennett 在他 1962 年的博士論文 [4] 中定義的。Bennett 使用了「擴展的正遞歸關係」這個名稱，他的定義使用了受限量詞而非計算機器。我閱讀了他論文的這一部分，並向他指出他的類別可以描述為現在熟悉的 NP 定義。我使用術語 L/+（繼承 Cobham 的類別 L）[18]，與 Edmonds 在 1965 年的獨立發展平行。Edmonds 非正式地談論具有「好特徵」的問題，這個概念與 NP 基本上等價。

1971 年，我 [18] 引入了 NP 完全的概念，並證明了可滿足性問題和子圖同構問題是 NP 完全的。一年後，Karp [42] 證明了 21 個問題是 NP 完全的，從而有力地證明了這個主題的重要性。獨立於此，稍後 L. A. Levin [49] 在蘇聯（現就職於 Boston University）定義了一個類似的（但更強的）概念，並證明了六個問題在他的意義上是完全的。非正式概念「搜索問題」在蘇聯文獻中是標準的，Levin 將他的問題稱為「通用搜索問題」。

NP 類別包含了大量在商業和工業中出現的實際問題（見 [31]）。證明一個 NP 問題是 NP 完全問題，就是證明這個問題不在 P 中（不具備確定性多項式時間演算法），除非每個 NP 問題都在 P 中。由於後者情況將徹底改變計算機科學，證明 NP 完全問題的實際效果是提供一個下界。這就是為什麼我將這個主題納入下界一節。

  • 見 [31]。

4.5 #P 完全性

NP 完全性的概念適用於集合，通常將集合是 NP 完全性的證明解釋為該集合難以處理的證明。然而，有大量看似難以處理的函數，但 NP 完全性證明似乎與之不相關。Leslie Valiant [86, 87] 定義了 #P 完全性的概念來幫助解決這種情況。證明一個函數是 #P 完全性，表明它在計算上顯然是難以處理的，其方式類似於證明一個集合是 NP 完全性，表明它在識別上顯然是難以處理的：如果一個 #P 完全性函數可以在多項式時間內計算，那麼 P = NP。

Valiant 給出了許多 #P 完全性函數的例子，但可能最有趣的是整數矩陣的永久式。永久式有一個定義形式上與行列式相似，但行列式很容易通過 Gaussian elimination 計算，過去一二百年來尋找可行方法計算永久式的許多嘗試都失敗了。Valiant [87] 在他證明永久式是 #P 完全性時，為這次失敗提供了第一個令人信服的理由。

  • 見 [31]。

5. 機率演算法

使用隨機數來模擬或近似隨機過程是非常自然的，並且在計算實踐中已經很成熟。然而，隨機輸入在解決確定性組合問題中可能非常有用的想法，在計算機科學界滲透得較慢。在這裡，我將重點關注機率（拋硬幣）多項式時間演算法，這些演算法「解決」（在合理的意義上）一個尚未知是否存在確定性多項式時間演算法的問題。

第一個這樣的演算法似乎是 Berlekamp [5] 在 1970 年提出的，用於分解有限域 GF(p) 上的一個多項式 f。Berlekamp 的演算法運行時間是 f 的度數和 log p 的多項式，並且以至少二分之一的機率找到 f 的正確質因數分解，否則會失敗。由於演算法可以重複任意次，且失敗事件都是獨立的，實際上該演算法總能在可行的時間內進行因數分解。

一個更戲劇性的例子是 Solovay 和 Strassen [77]（1974 年提交）提出的質數識別演算法。該演算法運行時間是輸入 m 的長度的多項式，並輸出「質數」或「合數」。如果 m 確實是質數，則輸出一定是「質數」，但如果 m 是合數，則以至多二分之一的機率答案也可能是「質數」。該演算法可以在輸入 m 上重複任意次，結果獨立。因此，如果答案曾經是「合數」，用戶就知道 m 是合數；如果經過，比如 100 次運行，答案始終是「質數」，那麼用戶有很好的證據表明 m 是質數，因為任何固定的合數 m 出現這種結果的機率非常小（小於 2^-100）。

Rabin [61] 開發了一種具有類似性質的不同機率演算法，並發現在計算機試驗中運行速度非常快。數字 2^201 - 1 在幾分鐘內被確定為（可能是）質數。* 機率質數測試器的一個有趣應用是 Rivest, Shamir, and Adleman [67a] 在他們 1978 年關於公開金鑰密碼系統的里程碑式論文中提出的。他們的系統需要生成大（100 位數字）隨機質數。他們建議使用 Solovay-Strassen 方法測試隨機的 100 位數字，直到找到一個在上述意義上可能是質數的數字。實際上，使用 Cohen 和 Lenstra [17] 在第 3 節中提到的新的高效確定性質數測試器，一旦找到一個隨機的 100 位「可能是質數」的數字，可以在大約 45 秒內確定測試其是否為質數，如果確定性很重要。

文獻中，類別 BPP（或有時簡稱 B）是指在 Solovay 和 Strassen 意義上具有多項式時間機率識別演算法的集合。因此，一個集合在 BPP 中當且僅當它具有一個機率識別演算法，該演算法始終在多項式時間內停止，對於不在集合中的輸入從不錯誤，對於集合中的每個輸入，它以至少二分之一的機率輸出正確答案。因此，合數集合在 BPP 中，並且通常 P ⊆ BPP ⊆ NP。還有其他有趣的例子，這些集合已知在 BPP 中，但未知是否在 P 中。例如，Schwartz [71] 表明，其條目是多變量多項式的非奇異矩陣集合在 BPP 中。演算法在隨機的小整數值處評估多項式，並計算結果矩陣的行列式。（由於計算出的多項式通常會有指數級項數，直接計算行列式顯然不可行）。

BPP = P 是一個有趣且未決的問題。基於哲學觀點，即當尋求的答案是一個明確的「是」或「否」時，隨機拋硬幣不應該有太大用處，這很具誘惑力去猜測答案是「是」。一個相關的問題是，機率演算法（證明一個問題在 BPP 中）是否對於所有實際目的都像確定性演算法一樣好。畢竟，機率演算法可以使用大多數計算機上提供的偽隨機數產生器來運行，而且錯誤率為 2^-100 是微不足道的。問題在於偽隨機數產生器不產生真正的隨機數，並且沒有人知道它們對於一個給定的機率演算法會有多好。事實上，經驗表明它們似乎運行良好。但是，如果它們總是運行良好，那麼就可以推斷出 BPP = P，因為偽隨機數是確定性生成的，所以真正的隨機性畢竟沒有幫助。另一種可能性是使用物理過程（例如熱噪聲）來生成隨機數。但在科學哲學中，自然如何做到真正的隨機性是一個未決問題。

讓我以 Adleman [1] 關於 BPP 類別的一個有趣的定理來結束本節。很容易看出 [57b]，如果一個集合在 P 中，那麼對於每個 n，存在一個大小受限於 n 的固定多項式的布林電路，它可以確定任意長度為 n 的字串是否在該集合中。Adleman 證明的是，對於 BPP 類別來說也是如此。因此，例如，對於每個 n，存在一個小的「計算機電路」，可以正確且快速地測試 n 位數字是否為質數。「問題」在於這些電路對於不同的 n 不是統一的，實際上對於 100 位數字的情況，要弄清楚如何構建這個電路可能並不可行。

  • 見 [61]。

6. 同步平行計算

隨著 VLSI 技術的出現，可以在四分之一英寸的晶片上放置一個或多個處理器，自然會想到一個由數千個此類處理器組成並行協作解決單一問題的未來計算機。儘管尚未構建這種非常大型的通用機器，但有一些這樣的項目正在進行中（見 Schwartz [72]）。這促使最近發展了一個非常令人愉快的計算複雜性分支：大規模同步平行計算理論，其中處理器數量是受參數 H(n)（H 指硬體）約束的資源，其方式類似於空間在順序複雜性理論中受參數 S(n) 約束。通常 H(n) 是 n 的一個固定多項式。

正如存在許多相互競爭的順序模型（見第 2 節）一樣，已經提出了相當多的平行計算模型（見 [21] 進行回顧）。然而，有兩個主要的競爭者。第一個是共享記憶體模型類別，其中大量處理器通過它們共享的隨機存取記憶體進行通信。已經為這類模型發表了許多平行演算法，因為實際的平行機器在建成後很可能就是這樣。然而，對於數學理論來說，這些模型並不是很令人滿意，因為它們的詳細規範中有太多是任意的：共享記憶體中的讀寫衝突如何解決？每個處理器允許哪些基本操作？訪問共享記憶體是否應該收取 log n 個時間單位？

因此，我更喜歡 Borodin [8]（1977 年）討論的更簡潔的模型，其中平行計算機是一組統一的非循環布林電路 Bn，使得 Bn 有 n 個輸入（因此處理長度為 n 的輸入字串）。然後 H(n)（硬體量）簡單地是 Bn 中閘的數量，而 T(n)（平行計算時間）是電路 Bn 的深度（即從輸入到輸出的最長路徑的長度）。這個模型具有實用基礎，即所有實際機器（包括共享記憶體機器） presumably 都是由布林電路構建的。此外，計算一個函數所需的最小布林大小和深度是一個自然的數學問題，並且在平行計算理論出現之前就已經考慮過。

幸運的是，對於該理論來說，各種競爭性平行計算模型所需的硬體 H(n) 和平行時間 T(n) 的最小值差異不大。特別是，對於所有模型來說，存在一個有趣的普遍定理，Pratt 和 Stockmeyer [58] 在 1974 年首次證明了對於特定模型，並在 [33] 中稱為「平行計算論證」：即，一個問題可以由平行機器（硬體無限）在時間為 T(n) 的多項式內解決，當且僅當它可以由順序機器（時間無限）在空間為 T(n) 的多項式內解決。

平行計算中的一個基本問題是：哪些問題可以使用許多處理器比使用一個處理器解決得更快？Nicholas Pippenger [57a] 將這個問題形式化，他定義了類別 NC（現在稱為「Nick 的類別」），指那些可以在具有可行硬體量（H(n) = n^c）的平行計算機上超快速（時間 T(n) = (log n)^c）解決的問題。幸運的是，類別 NC 保持不變，獨立於所選的特定平行計算機模型，並且很容易看出 NC 是 FP 類別的一個子集，FP 是指可以在多項式時間內順序計算的函數。我們的非正式問題可以形式化為：FP 中的哪些問題也屬於 NC？

有可能（雖然不太可能）NC = FP，因為證明 NC ≠ FP 將需要在複雜性理論上取得突破（見第 4.1 節結尾）。由於我們不知道如何證明 FP 中的函數 f 不在 NC 中，次佳選擇是證明 f 對於 FP 是 log 空間完全的。這類似於證明一個問題是 NP 完全問題，其實際效果是阻礙人們為該問題尋找超快速平行演算法。這是因為如果 f 對於 FP 是 log 空間完全的，並且 f 在 NC 中，那麼 FP = NC，這將是一個很大的驚喜。

在將 FP 中的問題歸類為屬於 NC 或對於 FP 是 log 空間完全（當然，它們可能都不是）方面，已經取得了相當大的進展。第一個對於 FP 是 log 空間完全的問題例子是由我在 [20] 中於 1973 年提出的，儘管我當時沒有將結果表述為完全性結果。此後不久，Jones 和 Laaser [38] 定義了這種完全性概念，並給出了大約五個例子，包括上下文無關文法的空集問題。可能被證明對於 FP 是最簡單的完全問題是所謂的電路值問題 [47]：給定一個布林電路及其輸入值，找到輸出的值。對我來說最有趣的例子，由 Goldschlager, Shaw, and Staples [34] 提出，是找到具有（大）正整數容量邊的給定網絡的最大流的（奇偶性）。有趣之處在於完全性證明中的巧妙之處。最後，我應該提及線性規劃對於 FP 是完全的。在這種情況下，困難的部分是證明問題在 P 中（見 [43]），此後完全性證明 [26] 是直截了當的。

已知在 NC 中的問題包括二進制數的四種算術運算（+、-、、÷）、排序、圖連通性、矩陣運算（乘法、逆、行列式、秩）、多項式最大公因數、上下文無關語言，以及在圖中尋找最小生成森林（見 [11]、[21]、[63]、[67b]）。已知給定圖的最大匹配的大小 [11] 在「隨機」NC 中（NC 中允許拋硬幣），儘管找出實際的最大匹配是否也在隨機 NC 中是一個有趣的未決問題。 [89] 和 [67b] 中的結果提供了證明問題在 NC 中的通用方法。

FP 中最有趣的問題之一，既不知道它對於 FP 是完全的，也不知道它在（隨機）NC 中，是找到兩個整數的最大公因數。還有許多其他有趣的問題尚未分類，包括在圖中找到最大匹配或最大團（見 [88]）。

  • 結果在 [89] 中已得到輕微改進。

7. 未來

請允許我再次強調，計算複雜性領域非常龐大，而這篇概覽非常簡短。該學科中有很多部分我完全遺漏或只是稍微提及。對於這些部分的研究者，我表示歉意。

一個相對較新且令人興奮的部分，由 Yao [92] 稱為「計算資訊理論」，它建立在 Shannon 的經典資訊理論之上，並考慮可以通過可行計算訪問的資訊。這個主題主要由 Diffie 和 Hellman [25] 以及 Rivest, Shamir, and Adleman [67a] 關於公開金鑰密碼系統的論文引發，儘管其計算根源可以追溯到 Kolmogorov [45] 和 Chaitin [14a]、[14b]，他們最早使用計算理論賦予「單個有限序列是隨機的」概念意義。在這個理論中一個有趣的想法，由 Shamir [73] 以及 Blum 和 Micali [7] 考慮，關於生成計算上強的偽隨機序列，其中未來的位元被證明很難根據先前的位元進行預測。Yao [92] 證明，如果存在這樣的偽隨機序列生成器，那麼機率類別 BPP 就等於 P（見第 5 節）。事實上，計算資訊理論有望闡明隨機性在計算中的作用。

除了計算資訊理論，我們可以預期在機率演算法、平行計算以及（如果運氣好）下界方面取得有趣的新成果。關於下界，我在不久的將來看到一些希望的突破是證明並非每個 P 中的問題都可以在 O(log n) 空間內解決，也許還有 P ≠ NP。* 無論如何，計算複雜性領域仍然非常活躍，我期待著未來會帶來什麼。

致謝。我非常感謝我在 Toronto 的複雜性同事們提供的許多有益評論和建議，特別是 Allan Borodin、Joachim von zur Gathen、Silvio Micali 和 Charles Rackoff。

  • 見 [31]。

參考文獻

  1. Adleman, L. Two theorems on random polynomial time. Proc. 19th IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1978). 75-83.
  2. Adleman, L., Pomerance, C. and Rumely, R. S. On distinguishing prime numbers from composite numbers. Annals of Math. 117, (January 1983), 173-206.
  3. Aho, A. V., Hopcroft, J. E. and Ullman, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974.
  4. Bennett, J. H. On Spectra. Doctoral dissertation, Department of Mathematics, Princeton University, 1962.
  5. Berlekamp, E. R. Factoring polynomials over large finite fields. Math. Comp. 24 (1970), 713-735.
  6. Blum, M. A machine-independent theory of the complexity of recursive functions. JACM 14, 2 (April, 1967), 322-336.
  7. Blum, M., and Micali, S. How to generate cryptographically strong sequences of pseudo random bits. Proc. 23rd IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1982), 112-117.
  8. Borodin, A. On relating time and space to size and depth. SIAM J. Comput. 6 (1977), 733-744.
  9. Borodin, A. Structured vs. general models in computational complexity. In Logic and Algorithmic, Monographie no 30 de l'Enseignement Mathematique, Universite de Geneve, 1982.
  10. Borodin, A. and Cook, S. A. A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Comput. 11 (1982), 287-297.
  11. Borodin, A., von zur Gathen, J. and Hopcroft, J. Fast parallel matrix and GCD computations. 23rd IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1982), 65-71.
  12. Borodin, A. and Munro, I. The Computational Complexity of Algebraic and Numeric Problems. Elsevier, New York, 1975.
  13. Bshoute, R. W. and Dobkin, D. On the optimal evaluation of a set of bilinear forms. Linear Algebra and its Applications 19 (1978), 207-235.

14a. Chaitin, G. J. On the length of programs for computing finite binary sequences. JACM 13, 4 (October 1966), 547-569; JACM 16, 1 (January 1969), 145-159. 14b. Chaitin, G. J. A theory of program size formally identical to information theory. JACM 22, 3 (July 1975), 329-340. 15. Cobham, A. The intrinsic computational difficulty of functions. Proc. 1964 International Congress for Logic, Methodology, and Philosophy of Sciences. Y. Bar-Hillel, Ed. North Holland, Amsterdam, 1965. 24-30. 16. Cobham, A. The recognition problem for the set of perfect squares. IEEE Conference Record Seventh SWAT. (1966), 78-87. 17. Cohen, H. and Lenstra, H. W. Jr. Primality testing and Jacobi sums. Report 82-18, University of Amsterdam, Dept. of Math., 1982. 18. Cook, S. A. The complexity of theorem proving procedures. Proc. 3rd ACM Symp. on Theory of Computing. Shaker Heights, Ohio, (May 3-5, 1971), 151-158. 19. Cook, S. A. Linear time simulation of deterministic two-way pushdown automata. Proc. IFIP Congress 71 (Theoretical Foundations). North Holland, Amsterdam, 1972, 75-80. 20. Cook, S. A. An observation on time-storage tradeoff. JCSS 9 (1974), 308-316. Originally in Proc. 5th ACM Symp. on Theory of Computing, Austin, TX, (April 30-May 2, 1973), 29-33. 21. Cook, S. A. Towards a complexity theory of synchronous parallel computation. L'Enseignement Mathematique XXVII (1981), 99-124. 22. Cook, S. A. and Aanderaa, S. O. On the minimum computation time of functions. Trans. AMS 142 (1969), 291-314. 23. Cooley, J. W. and Tukey, J. W. An algorithm for the machine calculation of Complex Fourier series. Math. Comput. 19 (1965), 297-301. 24. Coppersmith, D. and Winograd, S. On the asymptomatic complexity of matrix multiplication. SIAM J. Comp. 11 (1982), 472-492. 25. Diffie, W. and Hellman, M. E. New directions in cryptography. IEEE Trans. on Inform. Theory IT-22 6 (1976), 644-654. 26. Dobkin, D., Lipton, R. J. and Reiss, S. Linear programming is log-space hard for P. Information Processing Letters 8 (1979), 96-97. 27. Edmonds, J. Paths, trees, flowers. Canad. J. Math. 17 (1965), 449-67. 28. Edmonds, J. Minimum partition of a matroid into independent subsets. J. Res. Nat. Bur. Standards Sect. B, 69 (1965), 67-72. 29. Ferrante, J. and Rackoff, C. W. The Computational Complexity of Logical Theories. Lecture Notes in Mathematics, #718, Springer Verlag, New York, 1979. 30. Fischer, M. J. and Rabin, M. O. Super-exponential complexity of Presburger arithmetic. In Complexity of Computation. SIAM-AMS Proc. 7, R. Karp, Ed., 1974, 27-42. 31. Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979. 32. Gill, J. Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6 (1977), 675-695. 33. Goldschlager, L. M. Synchronous Parallel Computation. Doctoral dissertation, Dept. of Computer Science, Univ. of Toronto, 1977. See also JACM 29, 4, (October 1982), 1073-1080. 34. Goldschlager, L. M., Shaw, R. A. and Staples, J. The maximum flow problem is log space complete for P. Theoretical Computer Science 21 (1982), 105-111. 35. Grzegorczyk, A. Some classes of recursive functions. Rozprawy Matematyczna, 1953. 36. Hartmanis, J. Observations about the development of theoretical computer science. Annals Hist. Comput. 3, 1 (Jan. 1981), 42-51. 37. Hartmanis, J. and Stearns, R. E. On the computational complexity of algorithms. Trans. AMS 117 (1965), 285-306. 38. Jones, N. D. and Laaser, W. T. Complete problems for deterministic polynomial time. Theoretical Computer Science 3 (1977), 105-117. 39. Kaltofen, E. A polynomial reduction from multivariate to bivariate integer polynomial factorization. Proc. 14th ACM Symp. in Theory Comp. San Francisco, CA, (May 5-7, 1982), 261-266. 40. Kaltofen, E. A polynomial-time reduction from bivariate to univariate integral polynomial factorization. Proc. 23rd IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles, 1982, 57-64. 41. Karatsuba, A. and Ofman, Yu. Multiplication of multidigit numbers on automata. Doklady Akad. Nauk. 145, 2 (1962), 293-294. Translated in Soviet Phys. Doklady. 7, 7 (1963), 595-596. 42. Karp, R. M. Reducibility among combinatorial problems. In: Complexity of Computer Computations. R. E. Miller and J. W. Thatcher, Eds., Plenum Press, New York, 1972. 85-104. 43. Khachian, L. G. A polynomial time algorithm for linear programming. Doklady Akad. Nauk. SSSR 244, 5 (1979), 1093-1096. Translated in Soviet Math. Doklady 20, 191-194. 44. Knuth, D. E. The Art of Computer Programming, vol. 3 Sorting and Searching, Addison-Wesley, Reading, MA, 1973. 45. Kolmogorov, A. N. Three approaches to the concept of the amount of information. Probl. Pered. Inf. (Probl. of Inf. Transm.) 1 (1965). 46. Kolmogorov, A. N. and Uspenski, V. A. On the definition of an algorithm. Uspekhi Mat. Nauk. 13 (1958), 3-28; AMS Transl. 2nd set. 29 (1963), 217-245. 47. Ladner, R. E. The circuit value problem is log space complete for P. SIGACT News 7, 1, (1975), 18-20. 48. Lenstra, A. K., Lenstra, H. W. and Lovasz, L. Factoring polynomials with rational coefficients. Report 82-05, University of Amsterdam, Dept. of Math., 1982. 49. Levin, L. A. Universal search problems. Problemy Peredaci Informacii 9 (1973), 115-116. Translated in Problems of Information Transmission 9, 265-266. 50. Luks, E. M. Isomorphism of graphs of bounded valence can be tested in polynomial time. Proc. 21st IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1980), 42-49. 51. Meyer, A. R. Weak monadic second-order theory of successor is not elementary-recursive. Lecture Notes in Mathematics, #453, Springer Verlag, New York, 1975, 132-154. 52. Meyer, A. R. and Stockmeyer, L. J. The equivalence problem for regular expressions with squaring requires exponential space. Proc. 13th IEEE Symp. on Switching and Automata Theory. (1972), 125-129. 53. Miller, G. L. Riemann's hypothesis and tests for primality. J. Comput. System Sci. 13 (1976), 300-317. 54. Oppen, D. C. A 2^2^...^2n upper bound on the complexity of Presburger arithmetic. J. Comput. Syst. Sci. 16 (1978), 323-332. 55. Papadimitriou, C. H. and Steiglitz, K. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ, 1982. 56. Paterson, M. S., Fischer, M. J. and Meyer, A. R. An improved overlap argument for on-line multiplication. SIAM-AMS Proc. 7. Amer. Math. Soc., Providence, 1974, 97-111. 57a. Pippenger, N. On simultaneous resource bounds (preliminary version). Proc. 20th IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1979), 307-311. 57b. Pippenger, N. J., and Fischer, M. J. Relations among complexity measures. JACM 26, 2 (April 1979), 361-381. 58. Pratt, V. R. and Stockmeyer, L. J. A characterization of the power of vector machines. J. Comput. System Sci. 12 (1976), 198-221. Originally in Proc. 6th ACM Symp. on Theory of Computing, Seattle, WA, (April 30-May 2, 1974), 122-134. 59. Rabin, M. O. Speed of computation and classification of recursive sets. Third Convention Sci. Soc. Israel, 1959. 1-2. 60. Rabin, M. O. Degree of difficulty of computing a function and a partial ordering of recursive sets. Tech. Rep. No. 1, O.N.R., Jerusalem, 1960. 61. Rabin, M. O. Probabilistic algorithms. In Algorithms and Complexity, New Directions and Recent Trends, J. F. Traub, Ed., Academic Press, New York, 1976. 21-39. 62. Rabin, M. O. Complexity of Computations. Comm. ACM 20, 9 (September 1977), 625-633. 63. Reif, J. H. Symmetric Complementation. Proc. 14th ACM Symp. on Theory of Computing, San Francisco, CA, (May 5-7, 1982), 201-214. 64. Reisch, S. and Schnitger, G. Three applications of Kolmogorov complexity. Proc. 23rd IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles, 1982. 45-52. 65. Ritchie, R. W. Classes of Recursive Functions of Predictable Complexity. Doctoral Dissertation, Princeton University, 1960. 66. Ritchie, R. W. Classes of predictably computable functions. Trans. AMS 106 (1963), 139-173. 67a. Rivest, R. L., Shamir, A. and Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM 21, 2 (February 1978), 120-126. 67b. Ruzzo, W. L. On uniform circuit complexity. J. Comput. System Sci. 22 (1981), 365-383. 68a. Savage, J. E. The Complexity of Computing. Wiley, New York, 1976. 68b. Schnorr, C. P. The network complexity and the Turing machine complexity of finite functions. Acta Informatica 7 (1976), 95-107. 69. Schönhage, A. Storage modification machines. SIAM J. Comp. 9 (1980), 490-508. 70. Schönhage, A. and Strassen, V. Schnelle Multiplication grosser Zahlen. Computing 7 (1971), 281-292. 71. Schwartz, J. T. Probabilistic algorithms for verification of polynomial identities. JACM 27, 4 (October 1980), 701-717. 72. Schwartz, J. T. Ultracomputers. ACM Trans. on Prog. Languages and Systems 2, 4 (October 1980), 484-521. 73. Shamir, A. On the generation of cryptographically strong pseudo random sequences. 8th Int. Colloquium on Automata, Languages, and Programming (July 1981), Lecture Notes in Computer Science No. 115, Springer Verlag, New York, 544-550. 74. Shannon, C. E. The synthesis of two-terminal switching circuits. BSTJ 28 (1949), 59-98. 75. Smale, S. On the average speed of the simplex method of linear programming. Preprint, 1982. 76. Smale, S. The problem of the average speed of the simplex method. Preprint, 1982. 77. Solovay, R. and Strassen, V. A fast monte-carlo test for primality. SIAM J. Comput. 6 (1977), 84-85. 78. Stearns, R. E., Hartmanis, J. and Lewis, P. M. II. Hierarchies of memory limited computations. 5th IEEE Symp. on Switching Circuit Theory and Logical Design. (1964), 179-190. 79. Stockmeyer, L. J. The complexity of decision problems in automata theory and logic. Doctoral Thesis, Dept. of Electrical Eng., MIT, Cambridge, 1974; Report TR-133, MIT Laboratory for Computer Science. 80. Stockmeyer, L. J. Classifying the computational complexity of problems. Research Report RC 7600 (1979), Math. Sciences Dept., IBM T. J. Watson Research Center, Yorktown Heights, N.Y. 81. Strassen, V. Gaussian elimination is not optimal. Num. Math. 13 (1969), 354. 82. Strassen, V. Die Berechnungskomplexitat von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten. Numer. Math. 20 (1973), 238-251. 83. Baur, W. and Strassen, V. The complexity of partial derivatives. Preprint, 1982. 84. Toom, A. L. The complexity of a scheme of functional elements realizing the multiplication of integers. Doklady Akad. Nauk. SSSR 150, 3, (1963), 496-498. Translated in Soviet Math. Doklady 3 (1963), 714-716. 85. Turing, A. M. On computable numbers with an application to the Entscheidungs problem. Proc. London Math. Soc. ser. 2, 42 (1936-7), 230-265; correction, ibid. 43 (1937), 544-546. 86. Valiant, L. G. The complexity of enumeration and reliability problems. SIAM J. Comput. 8 (1979), 410-421. 87. Valiant, L. G. The complexity of computing the permanent. Theoretical Computer Science 8 (1979), 189-202. 88. Valiant, L. G. Parallel Computation. Proc. 7th IBM Japan Symp. on Applied Scientific Programs, IBM Japan, Tokyo (1982). 89. Valiant, L. G., Skyum, S., Berkowitz, S. and Rackoff, C. Fast parallel computation on polynomials using few processors. Preprint (Preliminary version in Springer Lecture Notes in Computer Science. 118 (1981), 132-139. 90. von Neumann, J. A certain zero-sum two-person game equivalent to the optimal assignment problem. Contributions to the Theory of Games II, H. W. Kuhn and A. W. Tucker, Eds. Princeton Univ. Press, Princeton, NJ, 1953. 91. Yamada, H. Real time computation and recursive functions not real-time computable. IRE Transactions on Electronic Computers. EC-11 (1962), 757-760. 92. Yao, A. C. Theory and applications of trapdoor functions (Extended abstract). Proc. 23rd IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles (1982), 80-91.

CR 分類與主題描述詞：D.0 [通用] 通用術語：理論 附加關鍵字詞：computational complexity ACM 演算法 ACM 收集演算法 (CALGO) 現在作為常規 CALGO 補充服務的一部分，包含微縮膠片形式的完整演算法列表季度期刊。ACM 演算法發布服務現在提供包含 ACM 演算法完整列表的微縮膠片，並提供磁帶上的演算法彙編作為包含單個演算法的磁帶的替代品。微縮膠片和磁帶彙編按季度和年份提供。包含五年的磁帶彙編也將提供。現可從位於 11 W. 42nd St., New York, NY 10036 的 ACM 訂閱部門獲取 ACM 出版物目錄。要從 ACM 演算法發布服務訂購，請參閱 ACM Transactions on Mathematical Software 每期中的訂購表格。