1993年ACM圖靈演講:是時候重新思考時間了

當我還是個學生時，根本沒有電腦科學這個東西，我的興趣嚴格來說只有數學。我於1958年從 Carlton College 畢業，獲得數學學士學位，然後去了 Princeton 進行數學研究生工作。在那裡，在 Harold W. Kuhn 的指導和 Robert J. Aumann 的指導下，我撰寫了一篇關於賽局理論的博士論文，題為「Three-Person Cooperative Games without Side Payments」[8]，並於1961年秋季畢業。

1960年，我被 Richard L. Shuey 聘請到 New York Schenectady 的 General Electric 研究實驗室工作了整個夏天。Shuey 是被稱為「資訊研究組」(Information Studies Section) 的經理，這個組包括 Juris Hartmanis 和 Philip M. Lewis II。這個組是更大一個被稱為「電子物理」(Electron Physics) 組的一部分。那個夏天，我與 Hartmanis 合作，繼續他關於序列機分解的一些工作。因此，產生了第一篇 Hartmanis-Stearns 文章 [9]。GE 的人員素質以及他們定義自己研究目標的自由度給我留下了深刻的印象。因此，當 Shuey 邀請我於1961年作為正式員工回歸時，我抓住了這個機會。當時有人拿我的博士論文開了一些玩笑，因為 GE 剛剛因與另外兩家公司合作操縱價格（不涉及附帶支付！）而解決了一起反壟斷訴訟。

當我開始在 GE 工作時，我嚴格來說只是一個數學家。研究實驗室沒有電腦，我也從未使用過電腦。幾年後，實驗室購置了一台 GE300 並安裝了 Dartmouth 開發的分時系統。我的第一次程式設計經歷是通過電傳打字機介面使用 Basic 在這台機器上進行的。這些經歷發生在 Hartmanis 和我已經研究出了我們的計算複雜性理論之後。我轉變為電腦科學家是一個演變過程，而不是一個有意識的決定。我一直在追求我認為最有趣的數學問題，結果發現自己身處於電腦科學的中心。

我繼續對賽局理論和電腦科學同時保持興趣。事實上，我與 Hartmanis 的第一篇文章早於我的博士論文工作。你可能想知道這些領域是否有共同點。我認為它們有。一個共同點是它們都是由 John von Neumann 開創的。賽局理論的開端明確標誌著 von Neumann 和 Morgenstern 的著名著作 [13]，而 von Neumann 憑藉其「von Neumann 儲存程式電腦模型」也被認為是電腦科學的奠基人之一。

它們的第二個共同點是需要理解一些非常無形但又非常真實的東西。在賽局理論中，它是競爭的本質。在電腦科學中，它是計算的本質。這兩個領域都需要一些全新的數學，需要開發新的數學模型。我對賽局理論的吸引力始於大學的一個夏天，當時我為了消遣閱讀了 [13]，並看到了關於模型選擇的討論受到多麼大的關注。

對我來說，最有趣的數學是那些能夠告訴我們一些關於真實世界的東西。因此，作為數學家和電腦科學家，我們首先應該問的問題是：「我們的模型在多大程度上反映了我們希望描述的對象或情境的顯著特徵？」結果的意義更多地取決於它傳達的資訊，而不是其證明的複雜性。「垃圾進，垃圾出」(Garbage-in/garbage-out) 適用於理論，也適用於軟體。

複雜性

與 Hartmanis 合作的複雜性工作發表在會議版本 [5] 和期刊版本 [6] 中。¹ 會議版本發表在第五屆年度交換電路理論與邏輯設計研討會上，這個研討會經過幾次名稱變更，現在被稱為 FOCS (Foundations of Computer Science)。這兩個版本的文章標題中都包含了「計算複雜性」(computational complexity) 這個詞，這是這個詞第一次被使用。因此，我們是第一個將我們所做的事情稱為「計算複雜性」的人。

儘管會議版本比期刊版本先發表，但會議版本的文字寫得更晚，並將自己稱為期刊版本的「更新」。其中一個更新是引用了 Blum 來自 MIT 的博士論文 [1]。這項獨立於我們的工作，提供了複雜性類別更抽象的視角。這是一個非常重要的貢獻，也應該歸功於它激發了複雜性領域的早期興趣和快速發展。

在 [6] 中，我們在沒有輸入的多帶 Turing machine 上發展了我們的理論，這些機器產生無限長的零和一序列。這基本上與 Yamada 在其關於「實時可計數函數」(real-time countable functions) 的工作 [14] 中使用的模型相同。然而，現在熟悉的語言識別模型正迅速上升到其在自動機理論中如今的顯著地位。辨識器是一個有價值的模型，因為儘管它們的輸出只有簡單的是/否，但它們已經足夠討論大多數計算問題。此外，它們非常適合研究非確定性 (nondeterminism)。在更新版本中，我們討論了將我們的方法應用於這個模型。

第三個更新是討論使用 Hennie-Stearns 的雙帶 n log n 模擬 [7] 代替 Hartmanis-Stearns 的單帶 n² 模擬的含義。(Fred Hennie 不時地作為訪客在 GE 工作。) 其含義是區分複雜性類別的一個更清晰、更充分的條件。

我們工作的主要貢獻是使用確定性時間來定義複雜性類別。使用現代記號和語言識別模型，我們的定義是這樣的：

定義 1. DTIME(T(n)) 是所有語言 L 的集合，對於這些語言 L，存在一個多帶 Turing machine，使得該機器

回答問題「輸入 w 是否屬於語言 L ?」，以及
在最多 T(|w|) 步驟內回答問題，其中 |w| 是輸入 w 的長度。

換句話說，通過提供一個程式，該程式在 n 為輸入大小時，在 T(n) 步驟內回答相應的成員資格問題，就可以將一個問題放入 DTIME(T(n)) 類別中。演算法分析中最常見的目標是為演算法的執行時間設定一個上限。就時間複雜性模型而言，這對應於將演算法解決的問題放入一個複雜性類別中。

從某種意義上說，這些複雜性類別應該被稱為「容易性類別」(easiness classes)，因為表達一個問題本質上是困難的（即建立下限）是通過證明該問題不屬於某個時間類別來實現的。

我們證明的第一件事是一個「加速定理」(speed-up theorem)：

定理 1. DT1ME(T(n)) = DTIME(c * T(n)) 對於所有 c > 0。²

換句話說，重要的是 O(T(n)) 而不是 T(n)。這是一個我們應該從一個合適的模型中期望的性質，因為自動機轉換次數與以秒為單位測量的實際時間之間沒有有意義的關係，並且演算法執行所需的時間（以秒為單位）會隨著電腦技術而變化。看到這個性質是我們定義的結果真是太好了。當然，在實踐中常數因子很重要，並非所有 O(T(n)) 的程式都同樣好，但我們不期望在自動機理論層面上區分這樣的程式。

我們工作的核心結果是：

定理 2. 如果 T(n) * log(T(n)) -------------- --> 0 U(n) 則 DTIME(U(n)) 包含一個不在 DTIME(T(n)) 中的語言。³

這個結果意味著確實存在時間層級結構，並且時間函數的微小變化會產生不同的類別。例如，有些問題可以在 O(n²) 時間內解決，而對於任何 ε > 0，都不能在 O(n²⁻ε) 時間內解決。因此，某些問題具有固有的複雜性，無法通過巧妙的程式設計來規避。

我們的模型沒有的一個性質是「機器獨立性」(machine independence)。也就是說，如果複雜性類別是相對於某些增強的 Turing machine（例如帶有二維帶的機器）定義的，那麼類別會有所不同。我們的文章研究了幾種這樣的增強，發現時間差異通過低次多項式相關聯。如果一個複雜性概念在時間上與 Turing machine 多項式相關的模型不變，則現在認為它是「機器獨立的」。

不久之後，Hartmanis 和我與 Phil Lewis [10] 一起研究了「帶」(tape) 複雜性（現在稱為空間複雜性，space complexity）。這在模型層面上包含了一個創新。我們相對於使用的臨時帶（scratch tape）（即只讀輸入帶不計入測量）來定義我們的空間複雜性。這使得存在次線性複雜性類別，一直到 log n 空間，在某些情況下甚至到 log log n 空間。

硬度概念

儘管時間和空間複雜性類別形成了層級結構並提供了討論難度的概念，但沒有明顯的技術可以針對一個特定的問題並證明它不容易。換句話說，證明對於解決一個特定問題根本不存在好方法是很困難的（並且仍然是）。僅僅因為我有一個巧妙的方法可以在例如 O(T(n)) 時間內解決一個問題，我怎麼知道是否存在一個 O(T'(n)) 演算法，其中 T'(n) 比 T(n) 小得多？

當 Cook 引入我們現在稱為 NP-硬度 (NP-hardness) 和 NP-完備性 (NP-completeness) 的概念時 [2]，情況有了顯著改善。總體思想是將一個特定問題的難度與一組看似困難的問題的難度聯繫起來。這將通過證明，如果對於給定問題存在一個好演算法，那麼對於該集合中的每個問題都將存在一個好演算法來實現。在 Cook 的情況下，那組看似困難的問題是現在稱為 NP-complete 的問題集，並且如果一個演算法只需要多項式時間，則被認為是「好」的。硬度概念本身現在被稱為 NP-完備性。

NP-complete 問題似乎非常困難，因為根據定義，如果其中任何一個可以在多項式時間內解決，那麼任何具有非確定性多項式演算法的問題也可以。事實上，這些問題似乎需要指數時間。證明問題 X 是 NP-complete 的標準方法是取一個已知為 NP-complete 的問題 Y，並證明可以使用某種多項式時間歸約 (reduction) 將 Y 的任何實例轉換為具有相同答案的 X 的實例。實際上，歸約意味著任何解決 X 的方法都可以用於同樣有效地解決 Y，因此 X 不可能比 Y 容易。由於我們相信 Y 是困難的，我們也相信 X 是困難的。因此，NP-硬度被接受為問題需要指數時間的有力證據。

為了讓這個計畫奏效，需要有一些已知為 NP-complete 的問題。Cook 的文章通過證明稱為 SAT 的問題（即 CNF 布林公式的可滿足性問題）是 NP-complete 而開啟了局面。Karp [4] 的工作很快跟進，表明許多實際應用中感興趣的組合問題也是 NP-complete。很快，數百個實際問題被證明是 NP-complete，其中許多可以在 [3] 中找到。

另一種硬度概念很快出現了，即 PSPACE-硬度 (PSPACE-hardness)，基於 PSPACE-完備性 (PSPACE-completeness) 的概念。PSPACE-hard 問題似乎非常困難，因為如果其中任何一個可以在多項式時間內解決，那麼所有在多項式空間內解決的問題都可以在多項式時間內解決。PSPACE-complete 問題似乎也需要指數時間。與 NP-完備性一樣，證明 PSPACE-完備性的標準方法涉及多項式時間歸約，這次是從 PSPACE-complete 問題進行。PSPACE-硬度比 NP-硬度是更強的硬度證據，因為即使出乎意料地證明 NP-complete 問題可以在多項式時間內解決，PSPACE-hard 問題仍然可能需要指數時間。第一個被證明為 PSPACE-complete 的問題是 QSAT，即判斷量化 CNF 公式是否為真的問題 [12]。

硬度概念已被證明在分類各種實際應用中感興趣的問題方面非常有用，並且極大地促進了我們對計算現實世界的理解。這些思想的應用如此成功，以至於我們有時會忽視它們的局限性或忘記它們真正的含義。這裡將指出其中一些局限性，然後我們將看到，從確定性時間的角度來看，關於這些問題的時間複雜性還有很多需要學習。

儘管 PSPACE-完備性是比 NP-完備性更強的硬度證據，但沒有理由相信 PSPACE-complete 問題在需要更多時間的意義上是更困難的。例如，考慮 NP-complete 的 SAT 和 PSPACE-complete 的 QSAT。對於這些問題，已知最好的演算法實際上是相同的。兩者都涉及考慮所有 O(2^n) 的變數賦值，並且都使用 O(n) 空間。我們傾向於相信 SAT 不能更快地解決，因此傾向於相信 SAT 和 QSAT 具有相同的複雜性。

當我們說 NP-complete 問題似乎需要「指數時間」時，我們並不是指 2^n。「指數」在這種情況下是指 2^(n^α) 對於某個 α > 0。因此 2^(n²)，2^(n¹/²)，2^(n^(log n))，甚至 2^(n^(sqrt(log n))) 都是指數的。事實上，對於所有 ε > 0，類別 DTIME(2^(n^ε)) 包含 PSPACE-complete 和 NP-complete 問題。當 ε 很小時，時間 O(2^(n^ε)) 可能不是大到無法實現。例如，當 n = 31,991 時，在一台 1 mips 的電腦上，可以在一個小時內執行 2^(n⁰.³⁷) 操作，而 2^(n⁰.¹⁴⁷) 大約只有 10⁶¹⁵。

因此，可以想像，這些「困難」問題中的一些對於所有顯著大小的輸入都可以很容易地解決。

基於時間的視角

為了方便進一步討論，考慮 Harry B. Hunt III 和我開發的以下基於時間的功率指數 (power index) 概念 [11]：

定義 2. 問題 L 的功率指數是集合 {r | L ∈ DTIME(2^(n^r))} 的最大下界 (greatest lower bound)，如果集合非空則為該值，如果集合為空則為 ∞。

這個概念有幾個吸引人的性質：

每個問題都有一個功率指數，因為每個非負實數的非空集合都有一個最大下界。
對於每個有理數 r，都存在一個功率指數為 r 的問題。（這由定理 2 得出。）
功率指數概念是「機器獨立的」。
具有多項式演算法的問題（即 P 中的問題）的功率指數都是零。具有指數時間界限的問題（即 EXPTIME 中的問題）都具有有限的功率指數。

如果任何 NP-complete 問題的功率指數大於零，那麼所有 NP-complete 問題的功率指數都大於零，並且 P ≠ NP。PSPACE-complete 問題也是如此。因此，證明一個 NP-complete 問題的功率指數非零將證明 P ≠ NP，而證明一個 PSPACE-complete 問題的功率指數非零將證明 P ≠ PSPACE。因此，我們預計在確定這些問題的功率指數時會遇到困難。然而，就像「硬度證據」一樣，我們可以通過使用歸約來研究「功率指數證據」。為此，我們必須注意歸約大小，定義如下：

定義 3. 歸約 R 的大小為 s(n) 當且僅當輸出 R(w) 的長度是 O(s(n))。

功率指數之間的關係可以通過以下定理建立：

定理 3. 如果 L₁ 的功率指數為 r，且 L₁ 可以通過大小為 n^s 的多項式時間歸約歸約到 L₂，則 L₂ 的功率指數至少為 r/s。

請注意，歸約的大小越大（即度數 s 越大），下限 r/s 就越弱。僅僅知道一個歸約是多項式的，並不能提供關於功率指數的任何資訊。

為了更清楚地理解定理 3，考慮 SAT 和 CLIQUE。從 SAT 到 CLIQUE 的標準歸約 [3, 4] 的大小是 n²，並且沒有更好的歸約已知。因此，從定理得出的最強結論是，CLIQUE 的功率指數至少是 SAT 的一半。這實際上與已知事實相當吻合，因為已知最好的 SAT 演算法需要 2^(O(n)) 時間，而最好的 CLIQUE 演算法僅使用 2^(O(n¹/²)) 時間。⁴ 如果我們能找到從 SAT 到 CLIQUE 的線性大小歸約，那麼我們就會有一個 2^(O(n¹/²)) 時間的 SAT 演算法！

從確定性時間的角度來看，並非所有 NP-complete 問題都同樣困難。通過密切關注歸約的大小，可以對各種 NP-complete 問題的複雜性進行更精細的比較。評估我們理解的一種方法是問以下問題：假設 SAT 確實需要 2^(O(n)) 時間（即假設 SAT 的功率指數為一），那麼可以推斷出其他 NP-complete 問題的功率指數是多少？

在許多情況下，我們有從 SAT 到其他可以在 2^(O(n)) 時間內解決的問題的線性歸約，而這個問題的答案是這些問題的功率指數也必須為一。然而，也有許多問題，已知最好的歸約不是線性的，這些問題潛在地更容易得多。在大多數情況下，這是一個開放的問題，即這種潛在性是否能夠實現，或者是否存在更小的歸約。

在更理論的層面，功率指數提醒我們，據我們所知，時間層級結構在很大程度上與硬度證據相關的類別是正交的。我們最好的猜測是，世界看起來類似於圖 1 所示的樣子。這張圖顯示了 EXPTIME 被劃分為具有相同功率指數的類別。這些類別也劃分了 PSPACE 和 NP 集合。SAT 和 QSAT 如猜測所示，功率指數為一。在其下方，CLIQUE 如猜測所示，功率指數為一半，並且 P 包含在功率指數為零的問題中。

我們關於確定性時間與硬度證據之間關係的觀察可以總結如下： • 所有 NP-complete 問題並非同樣困難。 • 所有 PSPACE-complete 問題並非同樣困難。 • 一個 PSPACE-complete 問題可能比一個 NP-complete 問題更容易。 • 即使 SAT 確實需要 2^(O(n)) 時間，許多實際應用中感興趣的 NP-complete 問題仍然可能需要少得多時間。

參考文獻

Blum, M. A machine-independent theory of the complexity of recursive functions. J. ACM 14, 4 (Apr. 1967), 322-336.
Cook, S.A. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, Shaker Heights, Ohio, 1971, pp. 151-158.
Garey, M.R. and Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979.
Karp, R.M. Reducibility among combinatorial problems. In R.E. Miller and J.W. Thatcher, eds., Complexity of Computer Computations, Plenum, N.Y. 1972, pp. 85-103.
Hartmanis, J. and Stearns, R.E. Computational complexity of recursive sequences. In Proceedings of the Fifth Annual IEEE Symposium on Switching Circuit Theory and Logical Design, Princeton, N.J., 1964, pp. 82-90.
Hartmanis, J. and Stearns, R.E. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, (May 1965), 285-305.
Hennie, F.C. and Stearns, R.E. Two-tape simulation of multi-tape Turing machines. J. of ACM, 13, 10 (Oct. 1966), pp. 533-546.
Stearns, R.E. Three-person cooperative games without side payments. In M. Dresher, L.S. Shapley, and A.W. Tucker, eds., Advances in Game Theory, Annals of Mathematics Studies #52, Princeton University Press 1964, pp. 307-406.
Stearns, R.E. and Hartmanis, J. On the state assignment problem for sequential machines II. IRE Trans. Electr. Comput., EC-10, (Dec. 1961), 593-603.
Stearns, R.E., Hartmanis, J., and Lewis II, P.M. Hierarchies of memory limited computations. In Proceedings of the Sixth Annual IEEE Symposium on Switching Circuit Theory and Logical Design, Ann Arbor, Mich. 1965, pp. 179-190.
Stearns, R.E. and Hunt III, H.B. Power indices and easier hard problems. Math. Syst. Theory 23 (1990), 209-225.
Stockmeyer, L.J. and Meyer, A.R. Word problems requiring exponential time. In Proceedings of Fifth Annual ACM Symposium on the Theory of Computing, Austin, Tex., 1973, pp. 1-9.
von Neumann, J. and Morgenstern, O. Theory of Games and Economic Behavior. Princeton, N.J., 1944.
Yamada, H. Real-time computation and recursive functions not real-time computable. IRE Trans. Electr. Comput., EC-11, (1962), 753-760.

圖 1. EXPSPACE 按功率指數細分

⁴對於 CLIQUE 而言，更簡單的演算法是由於這樣一個事實：大小為 k 的集團 (clique) 有 O(k²) 條邊，而長度為 n 的問題實例的邊數不超過 n。因此，最大集團中的節點數最多為 O(sqrt(n))，並且可以相應地限制窮舉搜索。

關於作者

RICHARD EDWIN STEARNS 是 University at Albany, State University of New York 的電腦科學教授。他目前的研究興趣包括問題實例的結構及其對複雜性的影響。作者目前地址：University at Albany—SUNY, Computer Science Dept., Albany, NY 12222; email: res@cs.albany.edu