圖靈獎介紹與引言

1975年的 ACM Turing Award 聯合授予 Michael A. Rabin 和 Dana S. Scott，並於10月20日在 Houston 舉行的 ACM 年度會議上頒發。 Turing Award 委員會主席 Bernard A. Galler 在介紹獲獎者時，宣讀了以下引文：

"本年度的 Turing Award 授予 Michael Rabin 和 Dana Scott，以表彰他們個人及共同的貢獻，這些貢獻不僅標誌著理論計算機科學的進程，更為整個領域樹立了清晰和優雅的標準。

Rabin 和 Scott 於1959年發表的論文《Finite Automata and Their Decision Problems》已成為形式語言理論中的經典，至今仍是該領域的最佳入門文獻之一。該論文既是一篇綜述，也是一篇研究文章：它技術上簡單，數學上無可挑剔。甚至被推薦給大學部學生閱讀。

隨後的幾年裡，Rabin 和 Scott 繼續各自做出了維持其早期論文水準的貢獻。 Rabin 將自動機理論應用於邏輯學，以及 Scott 為程式語言發展的 continuous semantics，是為該領域提供深度和廣度的兩個例子：前者將計算機科學應用於數學，後者則將數學應用於計算機科學。

Rabin 和 Scott 向我們展示了數學家如何能幫助科學家理解自己的主題。他們的工作為創造性應用數學提供了最佳典範之一。"

這是正式的引文，但這次頒獎也有非正式的一面。我想讓你們了解，這些獎項的獲得者是真實存在的人，他們在做著傑出的工作，但也非常像今天在座的我們。 Michael Rabin 教授出生於德國，1935年幼年隨父母移居 Israel。他在 Hebrew University 獲得數學碩士學位，後來在 Princeton University 獲得數學博士學位。獲得博士學位後，他在 Princeton University 擔任 F.B. Fine 數學講師，並在 Princeton 的 Institute for Advanced Studies 擔任成員。自1958年以來，他一直是 Jerusalem 的 Hebrew University 的教職員工。1972年至1975年，他也擔任 Hebrew University 的 Rector。 Rector 由大學 Senate 選出，是該機構的學術負責人。

Dana S. Scott 教授於1958年在 Princeton University 獲得博士學位。此後，他曾在 University of Chicago、 University of California at Berkeley、 Stanford University、 University of Amsterdam 和 Oxford University 任教。他目前的職稱是 England 的 Oxford University 數學邏輯學教授。

Rabin 教授將就「Computational Complexity」發表演講，而 Scott 教授將就「Logic and Programming Languages」發表演講。

Rabin 的論文從下方開始； Scott 的論文從第644頁開始。

計算複雜性

Michael O. Rabin Hebrew University of Jerusalem

計算複雜性理論的研究框架被描述，強調看似不同的問題和方法之間的相互關聯。提供了具有實踐和理論意義的示例。討論了新的研究方向。

Key Words and Phrases: complexity of computations, algebraic complexity, intractable problems, probabilistic algorithms CR Categories: 5.25

Copyright © 1977, Association for Computing Machinery, Inc.

允許重新出版本文的全部或部分內容，但不得用於商業目的，前提是必須註明 ACM 的版權聲明，並註明出版物、其發布日期以及經 Association for Computing Machinery 許可再版的事實。

Author's address: Department of Mathematics, Hebrew University of Jerusalem, Jerusalem, Israel.

Introduction

計算複雜性理論研究的是計算問題解決方案的定量方面。通常，對於解決諸如評估代數表達式、排序文件或語法分析符號串等問題，有多種可能的演算法。每個演算法都關聯著某些重要的成本函數，例如作為問題規模函數的計算步驟數、計算所需的記憶體空間需求、程式規模，以及在硬體實現的演算法中，電路規模和深度。

關於給定的計算問題 P，可以提出以下問題。什麼是解決問題 P 的良好演算法？能否為與演算法相關的成本函數之一建立並證明下界？這個問題是否難以處理，以至於沒有任何演算法能在實際可行的時間內解決它？這些問題可以針對最壞情況行為提出，也可以針對 P 的演算法的平均行為提出。另一個區別是 P 的循序演算法和平行演算法之間的區別。在過去的一年中，有人提出將演算法擴展到包括計算中的隨機化。上述一些考慮因素可以推廣到這些機率演算法。

在過去的二十年中，計算複雜性問題一直是廣泛研究的主題，無論是在一般理論框架內，還是針對具有數學和實踐重要性的特定問題。在眾多成就中，我們可以提及：

  • Fast Fourier Transform，最近有了顯著改進，並在通訊等領域有廣泛應用；
  • 證明程式正確性證明中出現的一些機械式定理證明問題是難解的；
  • 確定 n 位數加法所需的精確電路複雜性；
  • 用於組合和圖問題的驚人快速演算法及其與語法分析的關係；
  • 透過機率演算法，顯著減少某些重要問題的計算時間。

毫無疑問，所有上述問題的研究將繼續進行。此外，我們預見未來複雜性理論將分支進入重要的新領域。一個是安全通訊問題，這需要一個新的、更強大的複雜性理論作為堅實的基礎。另一個是研究與資料結構相關的成本函數。所設想的資料庫的龐大規模要求對列表構造和搜尋等過程的固有複雜性有更深入的理解。複雜性理論提供了這種發展所需的觀點和工具。

本文是作者1976年圖靈演講的擴展版本，旨在讓讀者對這個充滿活力的領域有一個概覽。我們將重點關注要點和方法論問題，而不是試圖進行全面的調查。

Typical Problems

我們首先列出一些代表性的計算問題，這些問題具有理論意義，通常也具有實際重要性，並且一直是深入研究和分析的主題。在隨後的章節中，我們將描述應用於這些問題的方法以及取得的一些重要成果。

Computable Functions from Integers to Integers

讓我們考慮從整數集 N = {0, 1, 2, ...} 到 N 的一個或多個變數的函數。我們直觀地認識到，像 f(x) = x!, g(x, y) = x² + y² 這樣的函數是可計算的。

A.M. Turing，這些演講正是以他命名的，他為自己設定了精確定義哪些函數 f: N → N, g: N × N → N 等是有效可計算的任務。他對理想化電腦的模型以及該電腦可計算的遞歸函數類別已廣為人知，無需贅述。

我們在此關注的是度量計算可計算函數 f: N → N 的值 f(n) 所需的計算工作量。此外，是否有可能展示一些難以被任何程式計算的函數？我們將在4.1節回到這些問題。

Algebraic Expressions and Equations

設 E(x₁, ..., x_n) 是一個由變數 x₁, ..., x_n 透過算術運算 +, -, *, / 構造的代數表達式。例如，E = (x₁ + x₂) * (x₃ + x₄) / x₅ * x₆。我們需要為數值代換 x₁ = c₁, ..., x_n = c_n 來評估 E(x₁, ..., x_n)。更一般地說，任務可能是同時評估 k 個表達式 E₁(x₁, ..., x_n), ..., E_k(x₁, ..., x_n)，對於代換 x₁ = c₁, ..., x_n = c_n。

重要的特殊情況如下。

評估多項式 f(x) = a_n x^n + a_{n-1} x^{n-1} + ... + a₀。(1)

矩陣乘法 A * B，其中 A 和 B 是 n × n 矩陣。在這裡，我們需要找到對於給定的數值 a_{ij}, b_{jk}，表達式 ∑_{k=1}^n a_{ik} b_{kj}, 1 ≤ i, j ≤ n 的值。

我們解決方程組的例子是 n 個線性方程組，包含 n 個未知數 x₁, ..., x_n： a_{11}x₁ + ... + a_{1n}x_n = b₁ ... a_{n1}x₁ + ... + a_{nn}x_n = b_n 1 ≤ i ≤ n (2)

給定係數 a_{ij}, b_i, 1 ≤ i, j ≤ n，我們需要求解（評估）未知數。

我們在這裡不討論代數和超越方程近似解的有趣問題，這個問題也可以用複雜性理論的工具來處理。

Computer Arithmetic

加法。給定兩個 n 位數 a = a_{n-1} ... a₀, b = b_{n-1} ... b₀ (例如，n = 4, a = 1011, b = 1100)，找到和 a + b = c_n c_{n-1} ... c₀ 的 n + 1 位數。

乘法。對於上述 a, b，找到乘積 a * b = d_{2n-1} d_{2n-2} ... d₀ 的 2n 位數。

這些算術任務可以在硬體中實現。在這種情況下，基數是2，並且 a_i, b_i = 0, 1。對於固定的 n，我們希望構造一個具有 2n 輸入和（對於加法）n + 1 輸出的電路。當 a, b 的 2n 位作為輸入進入時，n + 1 輸出將是 c_n, c_{n-1}, ..., c₀。乘法類似。

或者，我們可以考慮透過演算法，即在軟體中實現算術。這可能以多種方式出現。例如，我們的算術單元可能只執行加法，那麼乘法必須透過子程式實現。

透過程式實現算術也出現在多精度算術的背景下。我們的電腦字長是 k，我們希望加法和乘法長度為 nk 的數字（k 字長數字）。我們將基數取為數字 2^k，使得 0 ≤ a_i, b_i < 2^k，並使用演算法來找到 a + b, a * b。

Parsing Expressions in Context-Free Languages

複雜性理論的範圍絕不僅限於代數或算術計算。讓我們考慮無上下文文法，下面是一個例子。 G 的字母表包含符號 t, x, y, z, (, ), +, *。在這些符號中，t 是非終端符號，所有其他符號是終端符號。 G 的產生式（或重寫規則）是：

  1. t -> (t + t)
  2. t -> t * t
  3. t -> x
  4. t -> y
  5. t -> z

從 t 開始，我們可以透過使用產生式逐步重寫詞語。例如： t -(1)-> (t + t) -(3)-> (x + t) -(2)-> (x + t * t) -(4)-> (x + y * t) -(5)-> (x + y * z) (3) 箭頭上方的數字表示使用的產生式，括號 ( ) 表示要重寫的非終端符號。

像 (3) 這樣的序列稱為 derivation，我們說 (x + y * z) 可以從 t derive。從 t derivable 且僅包含終端符號的所有詞語 u 的集合稱為由 G 生成的語言，記為 L(G)。上述 G 僅為示例，推廣到任意無上下文文法是顯而易見的。

無上下文文法和語言常見於程式語言中，當然也常見於自然語言分析中。立即出現兩個計算問題。給定一個文法 G 和一個字母表上的詞語 W（即符號串）， W 是否屬於 L(G)？這是 membership problem。

parsing problem 如下。給定一個詞語 W ∈ L(G)，找到透過 G 的產生式從 G 的初始符號 derive W 的 derivation 序列，類似於 (3)。或者，我們需要 W 的 parse tree。例如，找到代數表達式的 parse tree 是編譯過程中必不可少的一步。

Storing of Files

文件 R₁, R₂, ..., R_n 的記錄儲存在輔助記憶體或主記憶體中。記錄 R_i 的索引 i 指示其在記憶體中的位置。每個記錄 R 都有一個 key（例如，所得稅檔案中的社會安全號碼）k(R)。計算任務是將記憶體中的文件重新排列為序列 R_{i₁}, ..., R_{i_n}，使得 keys 按升序排列： k(R_{i₁}) < k(R_{i₂}) < ... < k(R_{i_n})。

我們強調 key 和記錄之間的區別，記錄可能比 key 大得多，並且要求實際重新排列記錄。這些特點使問題比僅僅排序數字更現實且稍微困難。

Theorem Proving by Machine

自從電腦問世以來，賦予它們一些真正的推理能力一直是一個可以理解的抱負，並為此投入了相當大的努力。特別是，人們試圖讓電腦能夠進行邏輯和數學推理，方法是證明純邏輯的定理或推導數學理論的定理。我們考慮自然數加法理論的重要例子。

考慮系統 𝒩 = (N, +)，它由自然數 N = {0, 1, ...} 和加法運算 + 組成。用於討論 𝒩 屬性的形式語言 L 是一種所謂的一階謂詞語言。它具有變數 x, y, z, ...，範圍覆蓋自然數，運算符號 +，等號 =，常用的命題連接詞，以及量詞 ∀（"對於所有"）和 ∃（"存在"）。

像 ∃x∀y[x + y = y] 這樣的句子是 "存在一個數字 x，使得對於所有數字 y，x + y = y" 的形式化轉錄。這個句子在 𝒩 中實際上是真的。

L 中在 𝒩 中為真的所有句子的集合將稱為 𝒩 的理論 (Th(𝒩))，並記為 PA = Th(𝒩)。例如， ∀x∀y∃z[x + z = y ∨ y + z = x] ∈ PA。

我們也將使用 "Presburger's arithmetic" 的名稱，以紀念 Presburger，他在 Th(𝒩) 上證明了重要的結果。

PA 的 decision problem 是找到一個演算法（如果確實存在這樣的演算法）來確定語言 L 的每個給定句子 F 是否屬於 PA。

Presburger [12] 構建了這樣一個用於 PA 的演算法。自他的工作以來，幾位研究人員試圖設計用於解決此問題的有效演算法，並透過程式實現它們。這些努力通常處於自動化程式設計和程式驗證領域專案的框架內。這是因為人們試圖建立的程式屬性有時可以歸約為關於自然數加法的陳述。

Central Issues and Methodology of Computational Complexity

在前一節中，我們列出了一些典型的計算任務。稍後我們將介紹在這些問題上取得的成果。現在我們將一般性地描述提出的主要問題以及在複雜性理論中發揮作用的核心概念。

Basic Concepts

一類相似的計算任務稱為一個問題。問題 P 的個別情況稱為 P 的 instances。問題的界定當然只是一個約定俗成的問題。例如，我們可以談論矩陣乘法問題。這個問題的 instances 對於任意整數 n 來說，是 n × n 矩陣對 A, B，它們需要被乘法。

對於問題 P 的每個 instance I ∈ P，我們關聯一個 size，通常是一個整數 |I|。 size 函數 |·| 並非唯一，其選擇由與討論相關的理論和實際考量因素決定。

回到矩陣乘法的例子，對於一個 n × n 矩陣對 I = (A, B) 需要進行乘法，一個合理的度量是 |I| = n。如果我們研究用於矩陣乘法的演算法的記憶體空間需求，那麼度量 |I| = 2n² 可能更適合。相比之下， size 函數 |I| = n⁶ 似乎在任何情況下都不會自然地出現。

設 P 是一個問題，AL 是解決它的一個演算法。演算法 AL 在解決 instance I ∈ P 時執行某個計算序列 S_I。我們為 S_I 關聯某些度量。一些重要的度量如下：（1）S_I 的長度，指示計算時間。（2）S_I 的深度，即 S_I 可以分解為的並行步驟的層數。深度對應於 S_I 在並行計算下所需的時間。（3）計算 S_I 所需的記憶體空間。（4）除了 S_I 中的總步驟數，我們還可以計算特定類型步驟的數量，例如代數計算中的算術運算、排序中的比較次數或從記憶體中取得的次數。

對於演算法的硬體實現，我們通常將 size |I| 定義為使得相同 size n 的所有 instances I 都由一個電路 C_n 解決。電路 C 的複雜性有各種定義方式，主要有閘數；深度，這又與計算時間相關；或與用於實現電路的技術相關的其他度量，例如模組數量。

在確定計算 S 的度量 μ(S) 後，計算複雜性函數 C_{AL}(n) 可以以多種方式定義，主要的兩種是最壞情況複雜性 (worst-case complexity) 和平均行為複雜性 (average-behavior complexity)。第一個概念定義為： C_{AL}(n) = max {μ(S_I) | I ∈ P, |I| = n}。 (4)

為了定義平均行為，我們必須假設在每個集合 P_n = {I | I ∈ P, |I| = n} 上存在一個機率分佈 p。因此，對於 I ∈ P，|I| = n，p(I) 是 I 在所有 size 為 n 的其他 instances 中出現的機率。AL 的平均行為定義為： μ_{AL}^{avg}(n) = Σ_{I∈P_n} p(I) μ(S_I)。 (5)

我們將在4.7節討論機率分佈假設的適用性。

演算法分析處理以下問題。給定一個 size 函數 |·| 和計算 S 的度量 μ(S)，對於解決問題 P 的給定演算法 AL，精確確定其最壞情況複雜性 C_{AL}(n)，或在適當假設下，確定其平均行為 μ_{AL}^{avg}(n)。在本文中，我們不討論分析問題，而是假設複雜性函數是已知的或至少足夠確定以滿足我們的目的。

The Questions

現在我們具備了提出複雜性理論核心問題所需的概念：給定一個計算問題 P，它能以多好的性能或以什麼成本解決？我們不提及解決 P 的任何特定演算法。我們旨在檢視所有可能的解決 P 的演算法，並試圖對 P 的固有計算複雜性做出陳述。

應當牢記，研究問題 P 的複雜性的初步步驟是選擇要使用的度量 μ(S_I)。換句話說，我們必須從數學或實際角度決定我們要研究哪種複雜性。我們的研究一旦做出此選擇即可進行。

從廣泛的角度來看，稍後會有更詳細的例子和圖解，以下是我們將關注的主要問題。除最後一項外，它們似乎可以分為幾對。

  1. 尋找問題 P 的高效演算法。
  2. 建立 P 固有複雜性的下界。
  3. 尋找 P 的精確解。
  4. 尋找近似（接近）解的演算法。
  5. 研究最壞情況下的固有複雜性。
  6. 研究 P 的平均複雜性。
  7. 用於 P 的循序演算法。
  8. 用於 P 的平行處理演算法。
  9. 軟體演算法。
  10. 硬體實現的演算法。
  11. 透過機率演算法解決。

在 (1) 下，我們指的是為給定問題尋找良好的實際演算法。挑戰源於一個事實，即顯而易見的演算法常常可以被更優越的演算法取代。提高100倍的性能並非聞所未聞。但即使節省一半的成本，有時也可能意味著可行與不可行之間的區別。

雖然任何一個解決 P 的演算法 AL 都為 P 的複雜性提供了上限 C_{AL}(n)，但我們也對下界感興趣。典型的結果表明，對於每個解決 P 的 AL，g(n) ≤ C_{AL}(n)，至少對於 n > n₀，其中 n₀ = n₀(AL)。在某些幸運的情況下，上界與下界相符。此時，該問題的複雜性就完全已知了。無論如何，除了對下界的數學興趣外，一旦找到下界，它便透過指出哪些效率不應嘗試來指導我們尋找良好演算法。

針對問題的近似解 (4) 思想很重要，因為有時一個實際滿意的近似解比精確解更容易計算。

主要問題 (1) 和 (2) 可以與選項 (3)-(11) 中的一個或多個結合研究。例如，我們可以研究 k 個處理器並行工作的排序所需平均時間的上限。或者我們可以研究排序 n 個輸入位所需的邏輯閘數。

看起來，隨著選擇複雜性度量的多種可能性以及可能提出的問題的多樣性，計算複雜性理論將成為一系列分散的結果和不相關方法的集合。我們在呈現的例子中試圖強調的一個主題是該領域內部的很大程度的連貫性以及普遍存在於其中的思想和方法的共性。

我們將看到，用於並行評估多項式的有效演算法可以轉化為用於 n 位數快速加法的電路。 Fast Fourier Transform 的思想為多精度數字乘法提供了良好的演算法。在更高的層面上，軟體和硬體演算法之間的關係反映了循序和並行計算之間的關係。現今的程式設計旨在在單個處理器上運行，因此是循序的，而一個硬體元件包含許多可以視為並行運行的原始處理器。 preprocessing 方法在我們的例子中一次又一次出現，這也是共性的一個例子。

Results

Complexity of General Recursive Functions

在 [13, 14] 中，本文作者發起了透過計算複雜性對從整數到整數的可計算函數進行分類的研究。框架是公理化的，因此概念和結果適用於每一類合理的演算法和每一種計算度量。

設 K 是一類演算法，可能基於某種數學機器模型，使得對於每個可計算函數 f: N → N，存在一個 AL ∈ K 計算它。我們不指定計算 S 的度量 μ(S)，而是假設 μ 滿足某些自然的公理。這些公理滿足3.1節中列出的所有具體度量例子：整數 n 的 size 取為 |n| = n。計算 f 是一個問題，對於每個 instance n，我們必須找到 f(n)。根據3.1節 (4) 的方式，對於 f 的每個演算法 AL，都有計算複雜性函數 C_{AL}(n)，衡量 AL 計算 f(n) 所涉及的工作量。

定理 [13, 14]。對於每個可計算函數 g: N → N，存在一個可計算函數 f: N → {0, 1}，使得對於每個計算 f 的演算法 AL ∈ K，存在一個數字 n₀，並且對於 n > n₀，有 g(n) < C_{AL}(n)。 (6)

我們要求 f 是一個取值為 0-1 的函數，因為否則我們可以透過簡單地讓 f(n) 增長得非常快來構建一個複雜的函數，這樣寫下結果就會變得困難。

(6) 中的限制 n > n₀ 是必要的。對於每個 f 和 k，我們可以構造一個演算法，其中包含一個表，儲存 n ≤ k 時 f(n) 的值，這使得 n ≤ k 的計算變得微不足道。

上述定理的主要要點是 (6) 對於計算 f 的每個演算法都成立，並具有適當的 n₀ = n₀(AL)。因此，計算 f 的固有複雜性大於 g。

從 [14] 開始，E. Blum [1] 引入了不同但本質上等價的複雜性函數公理。 Blum 取得了許多有趣的結果，包括加速定理 (speed-up theorem)。這個定理表明存在一些可計算函數，對於它們沒有最佳演算法。相反，對於計算這類函數的每個演算法，存在另一個計算它快得多的演算法。

在過去的十年中，這個抽象複雜性理論領域的研究取得了長足的進展。它作為計算複雜性理論的基礎，首先提出了計算成本的問題，並強調需要考慮和比較解決給定問題的所有可能演算法。

另一方面，抽象複雜性理論並未解決具體的計算任務及其用具有實際意義的標準進行度量。這是在以下例子中完成的。

Algebraic Calculations

讓我們從評估多項式的例子開始。我們以算術運算次數作為度量，並使用記號 (hA, kM) 表示 h 次加法/減法和 k 次乘法/除法的成本。透過將多項式 (1) 重寫為 f(x) = (... ((a_n x + a_{n-1}) x + a_{n-2})) x + ... + a₀， 我們看到一般的 n 次多項式可以用 (nA, nM) 評估。根據3.2節中的問題1和2的精神，我們問是否有一個聰明的演算法可以使用更少的運算。相當精巧的數學論證表明，上述次數是最佳的，因此這個問題已完全解決。

T. Motzkin 在 [9] 中引入了 computation 的重要 preprocessing 思想。在許多重要的應用中，我們需要在許多不同的參數值 x = c₁, x = c₂, ... 下評估同一個多項式 f(x)。他建議對多項式 (1) 的係數採用以下 preprocessing 策略。一次性計算並儲存由給定係數 a₀, ..., a_n 得出的數字 α₀, ..., α_n。在評估 f(c) 時使用 α₀, ..., α_n。當 preprocessing 的成本與計算 f(c₁), f(c₂), ... 的總節省相比很小，即當預期的需要評估 f(x) 的參數數量很大時，這種方法具有計算意義。 Horowitz [?] 獲得了以下結果。

定理。使用 preprocessing，n 次多項式可以用 (n A, ⌈n/2⌉ + 2) M 評估。

同樣可以證明，這個結果本質上是最佳的。那麼並行評估呢？如果我們使用 k 個處理器，並且必須評估一個至少需要 m 次運算的表達式，那麼我們能期望的最佳計算時間是 (m/k) + log₂k。具體來說，假設所有處理器持續忙碌，那麼 m - k 次運算在時間 (m/k) - 1 內完成。剩餘的 k 次運算必須透過二元運算將 k 個輸入組合成一個輸出，這至少需要時間 log₂k。鑑於上述情況， Munro 和 Paterson [10] 的以下結果幾乎是最佳的。

定理。多項式 (1) 可以由 k 個處理器並行計算，時間為 (2n/k) + log k + O(1)。

隨著硬體的進步，我們有可能在同一任務上使用大量處理器。 Brent [3] 等人研究了無限並行的含義，並證明了以下定理。

定理。設 E(x₁, ..., x_n) 是一個算術表達式，其中每個變數 x_i 只出現一次。在無限並行下，表達式 E 可以在時間 O(log n) 內評估。

另一個重要主題是 Fast Fourier Transform (FFT)。 convolution 運算在信號處理等領域有很多應用，它是透過 FFT 極大便利的計算範例。設 a₀, ..., a_{n-1} 是一個 n 個數字的序列，b₀, b₁, ... 是一個傳入數字流。定義對所有 l 來說 c_l = a₀b_l + a₁b_{l+1} + ... + a_{n-1}b_{l+n-1}。(7)

我們需要計算 c₀, c₁, ... 的值。從 (7) 看來，每個 c_l 值的成本是 2n 次運算。如果我們以 n 為單位計算 c_l 的塊，即 c₀, ..., c_{n-1}，然後 c_n, ..., c_{2n-1} 等，使用 FFT，那麼每個塊的成本約為 4n log n，因此單個 c_l 的成本為 4 log n。

透過巧妙地結合代數和數論思想，S. Winograd [20] 最近改進了小 n 值的 convolution 計算時間，以及中小 n 值的離散傅立葉變換計算時間。例如，對於 n ≈ 1000，他的方法比傳統的 FFT 演算法快約兩倍。

對於 n × n 矩陣乘法和 n 個未知數的 n 個線性方程組 (2) 的求解，顯而易見的方法需要約 n³ 次運算。 Strassen [17] 發現了以下驚人的結果。

定理。兩個 n × n 矩陣可以使用最多 O(n^{log₂7}) 次運算進行乘法。 n 個未知數的 n 個線性方程組可以透過 O(n^{log₂7}) 次運算求解。

log₂7 ≈ 2.81 這個指數不太可能是真正最佳的，但在撰寫本文時，所有改進這個結果的嘗試都失敗了。

How Fast Can We Add or Multiply?

這個顯然重要的問題經過了透徹的分析。一個簡單的 fan-in 論證表明，如果使用 r 個輸入的閘，則 n 位數加法的電路至少需要時間 log_r n。實際上可以達到這個下界。

值得注意的是，根據3.2節關於並行演算法和硬體演算法類比的評論精神，加法電路的一個最佳結果 (Brent [2]) 使用了布林恆等式，這些恆等式可以直接轉換為多項式的有效並行評估演算法。

上述結果與要相加的數字的二進位表示有關。在對數字 0 ≤ a < 2^n 進行適當巧妙的編碼下，模 2^n 加法是否可以在時間少於 log n 內執行？ Winograd [19] 回答了這個問題。在非常一般的編碼假設下，下界仍為 log_r n。

轉向多精度算術，有趣的問​​題出現在乘法方面。乘法長度為 n 的數字的顯而易見的方法涉及 n² 位運算。早期的改進嘗試使用了簡單的代數恆等式，將運算次數減少到 O(n^{log₂3})。

Schönhage 和 Strassen [16] 利用自然數乘法與多項式乘法的聯繫，並採用 FFT 獲得了以下定理。

定理。兩個 n 位數可以透過 O(n log n log log n) 位運算進行乘法。

對整數乘法複雜性下界的嘗試必須參考特定的計算模型。在非常合理的假設下，Paterson Fischer and Meyer [11] 透過展示以下定理，顯著縮小了上界和下界之間的差距。

定理。乘法 n 位數至少需要 O(n log n / log log n) 次運算。

Speed of Parsing

無上下文文法中表達式的語法分析乍看起來似乎需要昂貴的回溯計算。一種同時尋找待分析字符串所有子字符串前驅的動態計算方法，導致了一個對於長度為 n 的詞語，需要 O(n³) 步驟的演算法。 n³ 的係數取決於文法。這個結果在很長一段時間內是最佳的，儘管對於特殊類型的無上下文文法取得了更好的上界。

Fischer 和 Meyer 觀察到， Strassen 的矩陣乘法演算法可以改編，用於兩個 n × n 布林矩陣的乘法，所需位運算為 O(n^{log₂7} c(n))。其中 c(n) = log n log log n log log log n，因此對於所有 ε > 0 來說是 O(n^ε)。

Valiant [18] 發現語法分析的複雜性最多與布林矩陣乘法相同。因此，由於實際上 log₂7 < 2.81，以下定理成立：

定理。在無上下文語言 L(G) 中，長度為 n 的表達式可以在 d(G) n^{log₂7} 時間內進行語法分析。

我們再次看到代數複雜性的結果如何在組合計算複雜性領域結出碩果。

Data Processing

在複雜性理論對資料處理的應用中，我們討論最著名的例子，即排序。我們遵循2.5節給出的 формуulation。

眾所周知，在隨機存取記憶體中排序 n 個數字需要約 n log n 次比較。這既是某些演算法的最壞情況行為，也是在所有排列具有同等可能性的假設下，其他演算法的平均行為。

記錄 R₁, R₂, ..., R_n 的重新排列提出了額外的問題，因為檔案通常 reside 在某些順序或近順序記憶體中，例如磁帶或磁碟。大小限制使得我們只能一次將少量記錄傳輸到快速記憶體進行重新排列。儘管如此，仍有可能開發出演算法，用於在 cn log n 時間內對檔案進行實際重新排序，其中 c 取決於所討論系統的特性。

這方面的一個有啟發性的結果是 Floyd [6] 所提出的。在他的模型中，檔案分佈在 m 個頁面 P₁, ..., P_m 上，每個頁面包含 k 個記錄，使得 P_i 包含記錄 R_{i1}, ..., R_{ik}。為了我們的目的，我們可以假設 m = k 不失一般性。任務是重新分發記錄，使得 R_{ij} 傳輸到頁面 P_j，對於所有 1 ≤ i, j ≤ k。快速記憶體足夠大，可以讀取兩個頁面 P_i, P_j，重新分發它們的記錄，然後將頁面寫出。利用類似於 FFT 中使用的遞歸，Floyd 證明了以下定理。

定理。上述記錄重新分發可以透過 k log₂k 次傳輸到快速記憶體實現。這個結果是最佳的。

下界是透過考慮一個適當的 entropy 函數建立的。它在假設在快速記憶體中記錄只是 shuffling 的情況下適用。目前尚不清楚，如果允許對記錄進行計算（將記錄視為位串），是否可以產生使用較少頁面 fetches 的演算法。

Intractable Problems

透過機器進行定理證明領域是計算問題的來源，這些問題需要極大量的計算步驟，因此難以處理 (intractable)。在試圖在電腦上運行用於 Presburger's arithmetic (PA) 的 decision problem 的程式時，計算僅在嘗試的最簡單的 instances 上終止。 Fischer 和 Rabin [5] 的以下結果為這個實用事實提供了理論基礎。

定理。存在一個常數 c > 0，使得對於每個用於 PA 的 decision algorithm AL，存在一個數字 n₀，使得對於每個 n > n₀，存在一個語言 L (用於數字加法的語言) 的句子 H，滿足 (1) |H| = n，(2) AL 需要超過 2^{c n} 步才能確定 H 是否屬於 PA，即確定 H 在 (N, +) 中是否為真。

常數 c 取決於用於陳述 {N, +} 屬性的記號。無論如何，它並非非常小。固有下界 2^{c n} 的快速增長表明，即使試圖解決這個非常簡單和基本的數學理論的 decision problem，我們也會遇到實際不可能的計算。 Meyer [8] 提出了具有更具破壞性複雜性 decision problem 的理論範例。

邏輯推理的最簡單層次是命題演算。從命題變數 p₁, p₂, ...，我們可以透過命題連接詞構造像 [p₁ ∧ ¬p₂] ∨ [p₃ ∧ ¬p₁] 這樣的公式。 satisfiability problem 是確定對於命題公式 G(p₁, ..., p_n)，是否存在一個給變數 p₁, ..., p_n 賦予真值的方式，使得 G 為真。例如，賦值 p₁ = F (假), p₂ = T (真) 滿足上述公式。

satisfiability problem 的直接演算法對於包含 n 個變數的公式需要約 2^n 步驟。目前尚不清楚是否存在非指數演算法來解決 satisfiability problem。

這個問題的重要性因 Cook [4] 而被凸顯出來。我們可以定義一個所謂的多項式歸約過程，將一個計算問題 P 歸約到另一個問題 Q。如果 P 可以多項式歸約到 Q，並且 Q 可以在多項式時間內解決，那麼 P 也可以。兩個相互可歸約的問題稱為 polynomially equivalent。 Cook 已經證明 satisfiability problem 與圖中的 cliques 問題是等價的。 Karp [7] 列舉了大量與 satisfiability 等價的問題。其中包括 0-1 integer programming 問題、圖中 Hamiltonian circuits 的存在問題，以及整數值 traveling-salesman problem，僅舉幾個例子。

鑑於這些等價關係，如果這些重要問題中的任何一個可以在多項式時間內解決，那麼所有其他問題也都可以。 satisfiability 是否具有多項式複雜性的問題稱為 P = NP 問題，並且理所當然地是計算複雜性理論中最著名的問題。

Probabilistic Algorithms

正如3.1節所述，對演算法平均行為或期望時間的研究是基於對問題 instance 空間中機率分佈的假設。這個假設涉及某些方法論上的困難。我們可以假設一個特定的分佈，例如所有 instance 具有同等可能性，但在實際情況下，需要解決的問題的 instance 來源可能以完全不同的方式存在偏差。分佈可能隨時間變化，並且我們常常不知道。在極端情況下，實際出現的大多數 instance 恰恰是演算法表現最差的 instance。

我們能否以不同的方式在計算中使用機率，一種我們可以完全控制的方式？問題 P 的 probabilistic algorithm AL 使用一個隨機數源。在解決 instance I ∈ P 時，會產生一個短序列 r = (b₁, ..., b_k) 的隨機數，並將這些隨機數用於 AL 以精確解決 P。除了隨機選擇 r 外，演算法完全以確定性方式進行。

我們說這樣一個 AL 以期望時間 f(n) 解決 P，如果對於每個 I ∈ P，|I| = n，AL 以期望時間小於或等於 f(n) 解決 I。期望時間是指 AL 解決 I 的所有可能選擇序列 r（我們假設它們具有同等可能性）的平均解決時間。

讓我們注意這個概念與眾所周知的 Monte-Carlo 方法之間的區別。在後者方法中，我們為一個問題構建一個模擬它的隨機過程，然後度量該隨機過程以獲得問題的近似解。因此，Monte-Carlo 方法本質上是一種類比解決方法。相比之下，我們的 probabilistic algorithms 使用隨機數 b₁, ..., b_k 來確定其他方面確定性演算法中的分支，並產生精確解而非近似解。

這樣的「擲骰子」諮詢似乎不可能加速計算。本文作者 [15] 系統地研究了 probabilistic algorithms。結果表明，在某些情況下，這種方法能帶來巨大的改進。

n 個點 x₁, ..., x_n ∈ R^k (k 維空間) 集合中最接近的一對點是距離 d(x_i, x_j) 最小的點對 x_i, x_j (i ≠ j)。一個 probabilistic algorithm 在 O(n) 期望時間內找到最接近的一對點，這比任何傳統演算法都快。

確定自然數 n 是否為質數的問題對於大型 n 來說變得難以處理。目前的傳統方法在應用於非特殊形式的數字時，在 n ≈ 10¹⁵ 附近失效。作者設計的一個 probabilistic algorithm 在時間 O((log n)³) 內工作。在一台中型電腦上，在幾分鐘內就識別出 2⁴⁰⁰ - 593 是質數。該方法對於任何其他大小差不多的數字也同樣有效。

這些想法的全部潛力尚不清楚，值得進一步研究。

New Directions

在可能進一步研究的途徑中，讓我們只提及兩個。

Large Data Structures

商業需求要求創建越來越大的資料庫。同時，現今乃至更迫近的未來技術使得創建具有不同程度存取自由度的巨大儲存設施成為可能。

目前關於資料庫的大部分研究都集中在使用者和系統之間的介面語言上。但是，所考慮的列表和其他結構的巨大規模可能會使得對這些結構所需的操作成本非常高昂，除非對執行這些操作的演算法有更深入的理解。

我們可以從尋找一個理論上但同時具有實際意義的列表模型開始。這個模型應該足夠通用，能夠專門化為目前使用的各種列表結構類型。

對列表的操作是什麼？我們可以列舉一些。搜尋列表、垃圾回收、存取列表中的各個點、插入、刪除、合併列表。能否將這些以及其他重要操作的研究系統化？可以與這些操作關聯哪些合理的成本函數？

最後，對資料結構的深入定量理解可以作為建議應遵循的技術方向的基礎。並行處理是否顯著加快了資料結構上的各種操作？在 associative memories 中，列表可以賦予哪些有用的屬性？當然，這些只是例子。

Secure Communications

安全通訊使用某種編碼裝置，我們可以提出與這些系統相關的計算複雜性的基本問題。讓我們透過 block-encoding 系統來說明這一點。

在 block-encoding 中，使用一個數字裝置，它以長度為 n 的詞語作為輸入，並使用 key 將它們編碼。如果 x 是長度為 n 的詞語，z 是一個 key（我們假設 keys 的長度也為 n），那麼讓 E_z(x) = y, |y| = n，表示使用 key z 編碼 x 的結果。長度為 kn 的訊息 w = x₁, x₂, ..., x_k 被編碼為 E_z(x₁) E_z(x₂) ... E_z(x_k)。

如果敵手能夠獲取當前的 key z，那麼他就可以解碼各方之間的通訊，因為我們假設他擁有編碼和解碼設備。他也可以在線路中插入假訊息，這些訊息會被正確解碼。在商業通訊中，這種可能性可能比安全漏洞更危險。

在考慮安全性時，應該考慮敵手獲取了一些明文訊息 w₁, w₂, ... 以及編碼形式 E_z(w₁), E_z(w₂), ... 的可能性。能否從這些資料計算出 key z？

證明這種計算是難以處理的是不夠的。因為目前的複雜性理論結果給出的是最壞情況資訊。因此，即使（例如）對於大多數 key-retrieval 計算，如果能確立計算複雜性的下界為 2^n，則該問題將被視為難以處理。但是，如果一個演算法在實際時間內在千分之一的情況下發現 key，那麼欺詐的可能性將是無法接受的大。

因此，我們需要一個複雜性理論，能夠讓我們陳述並證明某個計算實際上在幾乎所有情況下都是難以處理的。例如，如果任何用於 key 確定的演算法僅在 O(2⁻ⁿ) 的情況下能在實際時間內終止，那麼 block-encoding 系統就是安全的。我們離創建這樣一個理論還很遙遠，尤其是在 P = NP 尚未解決的現階段。

References

  1. Blum, M. A machine independent theory of the complexity of recursive functions. J. ACM 14 (1967), 322-336.
  2. Brent, R.P. On the addition of binary numbers. IEEE Trans. Computers C-19 (1970), 758-759.
  3. Brent, R.P. The parallel evaluation of algebraic expressions in logarithmic time. Complexity of Sequential and Parallel Numerical Algorithms, J.F. Traub, Ed., Academic Press, New York, 1973, pp. 83-102.
  4. Cook, S.A. The complexity of theorem proving procedures. Proc. Third Annual ACM Symp. on Theory of Comptng., 1971, pp. 151-158.
  5. Fischer, M.J., and Rabin, M.O. Super-exponential complexity of Presburger arithmetic. In Complexity of Computations (SIAM-AMS Proc., Vol. 7), R.M. Karp Ed., 1974, pp. 27-41.
  6. Floyd, R.W. Permuting information in idealized two-level storage. In Complexity of Computer Computations, R. Miller and J. Thatcher Eds., Plenum Press, New York, 1972, pp. 105-109.
  7. Karp, R.M. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. Miller and J. Thatcher Eds., Plenum Press, New York, 1972, pp. 85-103.
  8. Meyer, A.R. The inherent computational complexity of theories of order. Proc. Int. Cong. Math., Vol. 2. Vancouver, 1974, pp. 477-482.
  9. Motzkin, T.S. Evaluation of polynomials and evaluation of rational functions. Bull. Amer. Math. Soc. 61 (1955), 163.
  10. Munro, I., and Paterson, M. Optimal algorithms for parallel polynomial evaluation. J. Comptr. Syst. Sci., 7 (1973), 189-198.
  11. Paterson, M., Fischer, M.J., and Meyer, A.R. An improved overlap argument for on-line multiplication. Proj. MAC Tech. Report 40, M.I.T, (1974).
  12. Presburger, M. Uber die Vollstandigkeit eines gewissen Systems Arithmetic ganzer Zahlen in welchem die Addition als einzige Operation hervortritt. Comptes-rendus du I Congres de Mathematiciens de Pays Slaves, Warsaw, 1930, pp. 92-101, 395.
  13. Rabin, M.O. Speed of computation and classification of recursive sets. Third Convention Sci. Soc., Israel. 1959, pp. 1-2.
  14. 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.
  15. Rabin, M.O. Probabilistic algorithms. In Algorithms and Complexity, New Directions and Recent Trends, J.F. Traub Ed., Academic Press, New York, 1976, pp. 21-39.
  16. Schönhage, A., and Strassen, V. Schnelle Multiplication grosser Zahlen. Computing 7 (1971), 281-292.
  17. Strassen, V. Gaussian elimination is not optimal. Num. Math. 13 (1969), 354-356.
  18. Valiant, L.G. General context-free recognition in less than cubic time. Rep., Dept. Comptr. Sci., Carnegie-Mellon U., Pittsburgh, Pa., 1974.
  19. Winograd, S. On the time required to perform addition. J. ACM 12 (1965), 277-285.
  20. Winograd, S. On computing the discrete Fourier transform. Proc. Natl. Acad. Sci. USA 73 (1976), 1005-1006.