1994年ACM圖靈演講:計算複雜性與電腦科學的本質

引言與個人背景

在科學工作中，同儕的認可是一種最大的獎勵。特別是，像 Richard Stearns 和我榮獲 1993 年 ACM Turing Award 這樣的官方認可，令人非常滿足並深感榮幸。科學是一場偉大的智識冒險，也是人類最偉大的成就之一。此外，研究生涯可以是一項令人興奮、有益且崇高的活動，特別是如果能幸運地參與創造一門全新且非常重要的科學，正如許多科學家所經歷的那樣。我通往電腦科學的道路並非一帆風順。回想起來，它更像是一次隨機漫步，在恰當的智識停留點上，為我進入電腦科學領域的工作做了準備。

通往電腦科學的旅程

我出生於 Latvia，該國在 World War II 期間失去了獨立，而在 World War II 結束時，由於激烈的戰鬥，我們不得不逃離。戰後，作為在 Germany 的 D.P. (displaced person)，我在一個由優秀的難民學者組成的工作人員開設的 D.P. 營地完成了一所卓越的 Latvia 高中，這些學者傳達了他們對知識、學術，特別是科學的熱情。我在 Marburg 的 Philips University 學習物理，並等待有機會移民到 United States。這個機會在我學習了大約兩年半後出現了。在 U.S.，我們的擔保人在 Kansas City，抵達那裡後，我繼續前往 University of Kansas City（現為 University of Missouri 系統的一部分）。我兩年多的學習被認為等同於學士學位，我被接受攻讀研究所，並非常慷慨地獲得獎學金。由於當時沒有物理系的研究所課程，我被建議（或被告知）學習數學，數學系有研究所課程。一年後，我獲得了數學碩士學位，並對數學的力量和美麗有了更好的認識。California Institute of Technology (Cal Tech) 接受了我攻讀研究所，並根據我的記錄判斷我看起來像「應用數學家」（這大概就是將兩年 European 物理與一年 Kansas City 數學混合的結果，儘管我從未上過應用數學課程）。由於當時 Cal Tech 沒有應用數學課程，我被建議學習純數學會非常愉快。這是個很好的建議，四年後，在我一生中最具啟發性的智識時期之一，我獲得了數學博士學位，論文是關於 lattice theory，副修物理。儘管我熱愛純數學，並對數學抽象的美麗和力量印象深刻，我感到一些智識上的不安，並希望能找到與我們周圍世界有更直接聯繫的研究問題。儘管如此，我還是聽從了我的導師的建議，接受了 Cornell University 數學系的一個教職。在 Cornell 的第二年，我獲得並接受了 General Electric Research Laboratory (GE Research Laboratory) 在 N.Y. Schenectady 的暑期工作，該實驗室新的信息研究部門由 Dr. Richard Shuey 領導。那個夏天是我科學興趣的重大轉折點。在 GE Research Laboratory，我被參與創造關於信息和計算的新科學的興奮所吸引。電腦科學為我提供了我所希望的研究領域，具有恰當的動機、範圍和興奮感。一個學年後，我加入了 GE Research Laboratory 成為一名研究科學家。接下來的一年，Richard Stearns，當時是 Princeton 的一名數學研究生，在實驗室度過了一個夏天，我們在那裡開始了我們的合作。在 Princeton 完成關於 game theory 的博士論文後，Dick 加入了實驗室，我們加強了合作。

計算複雜性的誕生

我們對於希望做什麼樣的電腦科學工作的看法，受到我們的背景以及對當時能找到的相關文獻的深入研究的影響。我們非常喜歡 Turing 1936 年的論文 [14]，並對不可判定性結果和基本遞歸函數論的優雅、清晰和簡潔性印象深刻。Turing 的工作為我們後續的工作提供了必要的定義明確的抽象計算機模型。我個人對 Shannon 的通信理論 [12] 印象深刻。Shannon 的理論以 channel capacity 和信息源的 entropy 為依據，對在噪聲信道上能「可靠地」傳輸多少信息給出了精確的定量定律。我熱愛物理學，因為它有如此精確的定律來管理和解釋物理世界的行為。在 Shannon 的工作中，我第一次看到了管理抽象信息實體的精確定量定律。對於一個前物理學家來說，存在管理信息及其傳輸等抽象實體的定量定律的想法是令人驚訝且極其迷人的。Shannon 給出了一個信息定量定律的美麗例子，信息本質上不受物理定律的直接約束。這引發了一個問題：是否存在精確的定量定律來管理抽象的計算過程，這同樣不受物理定律的直接約束。是否能有定量定律來確定對於每個問題，解決它需要多少計算努力（工作），以及如何衡量和確定它？

這些以及其他方面的考慮，促使我們堅信，必然存在管理信息和計算行為的定量定律。這項研究努力的成果總結在我們關於這個主題的第一篇論文中，該論文也命名了這個新的研究領域，「On the computational complexity of algorithms」[5]。為了捕捉計算努力的定量行為並通過其內在計算複雜性來分類計算，我們需要一個穩健的計算模型和一個直觀上令人滿意的問題複雜性分類。Turing machine 非常適合作為計算機模型，我們將其修改為 multi-tape 版本。為了對計算（或問題）進行分類，我們根據具有 bounded computational resources 的 Turing machine 引入了 complexity class 的關鍵概念。例如，在我們原始表示法中的 complexity class C_n^2，包含所有長度為 n 的實例可以在 multi-tape Turing machine 上以 n^2 步解決的問題。在當代表示法中，C_n^2 = TIME[n^2]。

如今，complexity classes 是核心的研究對象，複雜性理論中的許多結果和問題都以 complexity classes 的形式表達。

早期成果與關鍵概念

我們早期關於 complexity theory 的很大一部分工作致力於證明我們定義了根據計算困難度對問題進行有意義的分類，並推導出相關結果。我們證明了我們的分類是穩健的，並且不會因模型的微小改變而實質性改變；複雜性分類確實捕捉了關於數字和函數複雜性的直觀想法。我們探索了從 one-tape machine 到 multi-tape machine 甚至 multi-dimensional tape 時計算速度如何變化，並推導出了這些「speed-ups」的界限。稍後，Manuel Blum 在他 MIT 的博士論文 [1] 中，發展了一個 computational complexity 的公理化理論，並在許多其他結果中證明了所有 complexity measures 都通過遞歸關係聯繫在一起。我們的 speed-up 結果是這種關係的特殊情況。與 Manuel 在他撰寫博士論文期間相遇，並就 computational complexity 交換想法，這對我們來說是一種樂趣。同樣，我們也對 H. Yamada 在 University of Pennsylvania 在 Robert McNaughton 的指導下，在其關於 real-time computations 的論文 [15] 中的工作印象深刻並受到影響。我們還證明了 Hierarchy Theorelns，斷言計算時間（界限）的輕微增加可以解決新的問題。更明確地說：如果 T(n) 和 U(n) 是「好的」函數，並且 lim_{n->\infty} T(n) / U(n) = 0，那麼 complexity class TIME[T(n)] 被 TIME[U(n)] 嚴格包含。這些結果表明存在具有非常明確、內在計算複雜性界限的問題。無論使用何種方法和計算算法，問題的解決都需要，比如說 n^2 次操作，對於大小為 n 的問題實例。Blum 在他的論文中表明，這並非所有問題都如此，並且可能存在界限不那麼明確的奇異問題。

為了將我們對實數按其計算複雜性進行的分類與經典概念聯繫起來，我們證明了所有 algebraic numbers 都屬於低 complexity class TIME[n^c]，並且令我們驚訝地發現一些 transcendental numbers 是 real-time computable 的（即，它們在 TIME[n] 中）。由於我們無法證明任何 irrational algebraic numbers 在 TIME[n] 中，我們猜測所有 real-time computable numbers 要麼是 rational，要麼是 transcendental。這在 30 年後仍然是一個 open problem，我們只是逐漸意識到其數學深度以及其證明在數學中將產生的深遠影響。

在我們關於 complexity theory 的第一篇論文 [5] 的引言末尾，我們寫道：「最後一節致力於 open questions 和問題領域。我們堅信，數字和函數具有內在的計算本質，可以根據此分類，正如本論文所示，並且這是一個進行進一步研究的良好機會。」確實如此！我們開創了一個新的電腦科學研究領域，並給予了它一個名稱。

計算空間與其他進展

在 GE Research Laboratory，Phil Louis 加入了我們，一起探索 tape- (或 memory-) bounded computations，這產生了許多有趣的結果，並將 computational space established 為另一項主要的 computational resource measure [7, 13]。我們證明了所有 context-free languages 都可以在 (log n)^2-tape 上被識別。這個結果引導 Savitch [10] 得到了他關於 deterministic 和 nondeterministic tape-bounded computations 之間關係的優雅結果：對於「好的」函數 F(n)，NTAPE[F(n)] 包含在 TAPE[F(n)^2] 中。我們在實驗室的同事 Daniel Younger [16] 證明了 context-free languages 包含在 TIME[n^3] 中。很快，許多其他人也加入了計算複雜性的探索，computational complexity theory 發展成為一個主要的研究領域，取得了深刻而有趣的成果，以及一些電腦科學中最臭名昭著的 open problems。

電腦科學本質的反思

回顧整個電腦科學及其歷史，我對其科學和技術成就印象深刻，這些成就遠遠超出了我的預期。電腦科學已經發展成為一門重要的科學，擁有豐富的智識成就、令人印象深刻的實用成果以及令人興奮的未來挑戰。同樣令人印象深刻的是計算能力和通信能力上前所未有的技術發展，這放大了科學成就，並賦予計算和電腦科學在我們的科學、智識和商業活動中核心地位。

我個人認為電腦科學不僅僅是一門快速成熟的科學，它還有更多。電腦科學與其他科學有如此根本的不同，必須將其視為科學中的一個新品種，並且必須如此理解。電腦科學處理信息，其創造和處理，以及執行這些的系統，其中很大一部分不受物理定律的直接約束和控制。因此，電腦科學正在為探索不受物理定律直接支配的信息世界和智識過程奠定基礎並發展研究範式和科學方法。這就是它與其他科學不同的地方，也是我們在早期探索 computational complexity 時模糊感知並感到著迷的地方。

電腦科學的定義性特徵之一是其處理現象在尺度上的巨大差異。從電腦中程序和數據的個別 bit，到高度複雜的機器、其操作系統以及描述問題的各種語言對這些信息每秒數十億次的操作，尺度跨越了許多數量級。Donald Knuth [2] 對此有很好的描述：

電腦科學與工程是一個吸引不同類型思想者的領域。我相信一個天生的電腦科學家是算法思維的。這類人在處理不同規則適用於不同情況的情況下尤其擅長；他們是能夠快速改變抽象層次，同時「宏觀」和「微觀」地看待事物的人。

電腦科學家必須創造許多抽象層次來處理這些問題。人們必須創造智識工具來構思、設計、控制、編程和推理關於人類最複雜的創造物。此外，這必須以前所未有的精確度來完成。執行計算的底層硬件是 universal machines，因此它們是 chaotic systems：指令或數據的微小改變可能導致結果出現任意大的差異。眾所周知，這是 universal computing devices 的固有屬性（理論明確表明放棄普遍性會付出非常高的代價）。因此，電腦科學家擁有一個 universal device，它可以被指示執行任何計算並原則上模擬任何物理過程（根據我們當前的物理定律所描述的），但它因此是混亂的，必須以前所未有的精確度加以控制。這是通過圍繞混亂的 universal machines 構建的 successive layers of implemented abstraction 來實現的，這些抽象層幫助彌合事物尺度上的許多數量級差異。

計算設備的這種普遍性也賦予計算範式巨大的力量和範圍。在不同的時期，人們使用他們最新設備的概念化來試圖理解和解釋自然和人類如何運作。因此，我們目前對電腦概念和電腦模擬各種現象的重度依賴，可以與過去對 steam-driven devices、gears 和 latches 或 clocks 作為解釋模型的應用相提並論。

數字計算機的普遍性以及不斷增長的計算能力，賦予計算範式在我們所有智識活動中一個不同且非常核心的角色。數字計算機是一種 universal device，原則上可以執行任何計算（假設 Church-Turing thesis 成立，它涵蓋了所有計算），特別是任何公理化形式系統中的任何數學過程。因此，原則上，作為文明主要科學工具的數學推理的全部力量可以體現在我們的計算機中，從數值計算和物理過程模擬到符號計算和邏輯推理，再到定理證明。這種普遍性以及現代計算機的力量，確實非常涵蓋了我們的智識活動，並且其範圍和力量正在不斷增長。

電腦科學與物理科學的比較

顯然，電腦科學不是一門物理科學；然而，人們經常認為它與物理科學會表現出很強的相似性，並且在理論和實驗方面可能具有相似的研究範式。電腦科學未能符合物理科學範式，往往被解釋為其不成熟。事實並非如此，因為電腦科學中的理論和實驗所扮演的角色與物理科學不同。要更詳細地對比物理學和電腦科學的研究範式，請參見 [4]。

即使簡單地看一眼電腦科學的研究主題，也會發現理論和實驗之間的新關係。例如，算法的設計和分析是理論電腦科學的核心主題。為其設計開發方法，定義各種 computational resources 的測量標準，探索不同 resources 之間的權衡，並為各種問題的解決方案證明 upper 和 lower resource bounds。同樣，理論創造了方法論、邏輯和各種 semantic models 來幫助設計程序、推理程序、證明其正確性，以及指導新程序語言的設計。理論發展模型、測量標準和方法來探索和優化 VLSI 設計，並試圖概念化設計高效計算機和通信系統的技術。

考慮到前面提到的（以及其他的）電腦科學理論工作，人們會得出非常明確的結論：理論之間並非相互競爭，以更好地解釋信息的根本本質。新的理論也並非為了調和理論與實驗結果，因為實驗結果揭示了無法解釋的異常或新的、意想不到的現象，如在物理學中那樣。在電腦科學中，沒有像物理科學那樣，存在決定各種理論有效性的關鍵實驗的歷史。

數字計算的基本、底層數學模型沒有受到理論或實驗的嚴重挑戰。計算理論對有效計算施加的最終限制，已被充分理解和接受。人們正大力努力定義和證明可行計算的限制，但即使在這裡，基本的計算模型也沒有受到質疑。核心努力是證明某些計算不能在給定的 resource bounds 內完成，這在 P = NP? 問題中得到了很好的體現。應當注意，這個問題的解決可能會有廣泛的影響。例如，它可以證明哪些加密程序在什麼樣的攻擊下以及能持續多久是安全的。它還可以導致對人類-計算機推理能力的極限有更深入的理解。總體而言，「分離」問題，即 P # NP，PSPACE # EXPTIME # NEXPTIME # EXPSPACE? 的問題，是理論電腦科學中最重要的 open problems 之一。但沒有實驗，無論是物理的還是計算的，能夠解決這些問題，這再次強調了電腦科學不同的科學本質。

在電腦科學中，理論的結果是通過它們揭示的關於各種計算模型的數學本質的洞見來評判的，或者通過它們對計算實踐的實用性和易用性來評判。模型是否概念化和捕捉了電腦科學家感興趣的方面，它們是否為設計問題提供了洞見，它們是否有助於對相關問題進行推理和交流？在算法的設計和分析中，這是理論電腦科學的核心主題，性能的測量標準是明確定義的，並且在某些測量標準下（這可能無法完全反映它們在典型問題上的性能）結果可以很容易地進行比較。算法的實驗用於測試實現，並比較它們在被認為重要的問題子集上的「實際」性能。

同樣，檢查電腦科學中的實驗工作和系統構建，會發現與物理科學不同的模式。這類工作涉及性能測量、設計方法評估、新體系結構測試，最重要的是，通過構建前所未有的系統來測試可行性。

系統構建，包括硬件和軟件，是電腦科學應用和/或實驗工作（儘管實驗在這裡不是指舊的意義）的定義性特徵。這導致電腦科學的進步往往通過戲劇性的演示來展示和記錄，而不是像物理科學那樣通過戲劇性的實驗。演示的作用是展示做以前被認為不可能或不可行的事情的可能性或可行性。通常情況下，（在戲劇性演示中測試的想法和概念）會影響電腦科學的研究議程。

這反映在年輕電腦科學家的戰鬥口號「demo or die」（演示或死亡）中，這個口號正開始與舊的「publish or perish」（發表或滅亡）相抗衡，後者仍然是有效的建議，但應該被「publish in refereed journals or perish」（在同行評議期刊上發表或滅亡）取代。

電腦科學中的科學與工程

從上述觀察中，我們可以得出結論，電腦科學中的理論和實驗正在為算法和執行算法的計算系統的設計做出貢獻；電腦科學更專注於「how」（如何），而不是「what」（是什麼），後者更多是物理科學的重點。通常，「how」與工程學聯繫在一起，但電腦科學並非工程學的子領域。電腦科學確實是一門獨立的新科學，但它與工程方面的問題和考慮緊密相連並相互滲透。在許多方面，電腦科學中的科學和工程方面比許多其他學科更為接近。引用 Fred Brooks [2] 對於編程的說法：

程序员就像诗人一样，只稍微远离纯粹的思想材料。他在空中用空气建造他的城堡，通过想像力的努力来创造。很少有创造媒介如此灵活，如此易于打磨和重塑，如此容易实现宏大的概念结构。（……后来，这种易處理性本身也带来了问题。）然而，程序结构，不像诗人的文字，是真实的，因为它能运行和工作，产生独立于结构本身的可见输出。它打印结果，绘制图片，发出声音，移动手臂。神话和传说中的魔力在我们的时代变成了现实。在键盘上输入正确的咒语，显示屏就会活起来，显示出从未存在过也无法存在的事物。

Webster's dictionary 將 engineering 定義為「將科學原理應用於實際目的，如設計、建造和操作高效且經濟的結構、設備和系統」。根據這個定義，電腦科學的許多活動可以被視為 engineering，或者至少是尋找那些可以應用於「實際目的、設計、建造...」的科學原理。但再次，記住 Brooks 的引文，並反思電腦科學與工程活動的範圍，我們會發現我們領域的 engineering 具有與更經典的 engineering 實踐不同的特點。電腦科學中的許多 engineering 問題不受物理定律的約束，它們需要創造新的 engineering paradigms 和方法論。

正如之前觀察到的，電腦科學工作滲透著 efficiency 和 search for optimality 的概念。電腦科學的「how」動機將 engineering 概念引入科學，我們應該為我們的科學如此接近應用性而感到自豪。有點開玩笑，但也帶有一點真實性，我們可以說電腦科學是數學（或數學過程）的 engineering。從這個角度看，我們強烈地看到這是一種新的 engineering 形式。

我深信我們不應試圖在電腦科學和 engineering 之間劃清界線，任何分離它們的嘗試都是適得其反的。同時，我也相信電腦科學已經並具有巨大的潛力為理解我們的物理和智識世界做出貢獻。計算範式，在日益強大的 universal computing devices 支持下，激勵並允許探索和模擬物理和智識過程，甚至評估它們的能力和局限性。

未來潛力與開放問題

早在 1964 年，Warren McCullach [8] 就提出了一個關於「Experimental epistemology」的願景，即研究知識如何體現在大腦中，以及如何體現在機器中。John McCarthy [9] 更不謙虛地說：「AI 的研究可能導致一個類似於 metamathematics 的數學 metaepistemology——研究一個知識接受證據的規則與他所處的世界之間的關係。這項研究可能會產生關於某些智識策略是否能導致發現世界上的某些事實的數學定理。我認為這種可能性最終將徹底改變哲學。」

計算範式使得通過有限和無限序列的 Kolmogorov complexity [6] 來澄清 randomness 的概念成為可能。同樣，計算模型的普遍性對於證明這些概念的有效性至關重要。

Computational complexity 的考量已經根據預期應用細化了 randomness 的概念。已經表明，什麼是（可接受或被視為）random 取決於應用中的計算能力。然而，在這個領域關於物理過程和計算仍然存在深刻的 open problems。Kolmogorov random strings 在非常強烈的意義上是不可計算的；沒有 Turing machine 可以打印比其大小（描述）更長的 Kolmogorov random string。對於所有物理系統來說，是否存在一個相應的定律（定理）？小的物理系統能否產生長的 Kolmogorov random strings，或者更好的是，一個有限的物理系統（在不增加 randomness 的情況下，適當地加入所需的能量流入）能否產生 unbounded Kolmogorov random sequence？如果是這樣，那麼物理過程確實不能被計算機模擬完全捕捉。

最近，電腦科學的動機促使人們研究 interactive proofs 和 proof checking，揭示了 randomization 和 prover 與 verifier 之間的 interaction 意想不到的力量 [11]。這些結果表明，對於一個很長的證明，verifier 只需提出很少的問題，就可以以任意高的概率確信存在一個正確的證明，而無需看到整個證明。這些以及相關的結果為數學證明本質提供了根本性的新見解，確實是 metamathematical results。

Recursive function theory，最初由 Goedel's incompleteness results 激發，分類了什麼是以及什麼不是 effectively computable，從而清楚地展示了形式數學推理的力量和局限性。Complexity theory 目前正在努力確定什麼是以及什麼不是 feasibly computable。在這個努力中，P = NP? 問題是這個鬥爭中最著名的 open problem，但遠非唯一的 open separation problem。當 P = NP? 和其他 separation problems 得到解決，並對 feasibly computable 的限制獲得更深入的洞察時，計算範式和 complexity theory 可能使我們更好地理解 human-computer reasoning 的力量和局限性。我相信電腦科學有潛力對計算範式和我們的智識過程提供深刻的新見解和定量理解，因此，或許，有可能掌握可知事物的極限。

致謝

本文所表達的觀點深受作者參與 National Research Council 的一項研究的影響，該研究產生了報告 Computing the Future: A Broader Agenda for Computer Science and Engineering [3]，以及與 Cornell University 和位於 Germany Saarbruecken 的 Max Planck Institut fur Informatik 同事的討論。特別具影響力的是 Robert Constable、Fred Schneider 和 Richard Zippel。電腦科學中 demos 的重要性由 Constable 強調，而電腦科學中現象尺度巨大差異的重要性由 Zippel 雄辯地解釋，並與流體動力學中至今仍 poorly understood 的 turbulence 現象進行比較，其中尺度的廣泛範圍是導致問題困難的原因。

參考文獻

Blum, M. A machine independent theory of the complexity of recursive functions. J. ACM 14 (1967), 322-336.
Brooks, F.P. Jr. The Mythical Man-Month: Essays on Software Engineering. Addison-Wesley, Reading, Mass., 1975.
Hartmanis, J. and Lin, H., Eds. Computing the Future: A Broader Agenda for Computer Science and Engineering. National Academy Press, Washington, D.C., 1992.
Hartmanis, J. Some observations about the nature of computer science. In Foundations of Software Technology and Theo- retical Computer Science. Lecture Notes in Computer Science, Vol. 761. Springer-Verlag, 1993, 1-12.
Hartmanis, J. and Stearns, R.E. On the computational com- plexity of algorithms. Trans. Amer. Math. Soc., 177 (1965), 285-306.
Li, M. and Vitanyi, P.I.M.B. An Introduction to Kolmogorov Com- plexity and Its Applications. Springer-Verlag, Heidelberg, Ger- many, 1993.
Lewis, P.M., Stearns, R.E., and Hartmanis, J. Memory bounds for the recognition for context-free and context- sensitive languages. In Proceedings of IEEE Sixth Annual Sym- posium on Switching Circuit Theory and Logical Design. (1965), pp. 191-202.
McCullach, W.S. A historical introduction to the postula- tional foundations of experimental epistemology. In Cross- Cultural Understanding: Epistemology in Anthropology. F.C.S. Northrop, and H.H. Livingston, Eds., Harper and Row, New York, 1964.
McCarthy, J. Mathematical logic and artificial intelligence. In The Artificial Intelligence Debate. S.R. Grattbard, Ed., MIT Press, Cambridge, Mass., 1988.
Savitch, W.J. Relationship between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., 4 (1970), 177-192.
Shamir, A. IP = PSPACE. J. ACM 39 (1992), 869-877.
Shannon, C. The mathematical theory communication. Bell System Tech. J. 27 (1948), 379-656.
Stearns, R.E., Hartmanis, J., and Lewis, P.M. Hierarchies of memory limited computations. In Proceedings of IEEE Sixth Annual Symposium on Switching Circuit Theory and Logical De- sign. (1965), pp. 179-190.
Turing, A.M. On computable numbers with an application to the Entscheidungsproblem. In Proceedings of the London Mathematical Society, series 2, 42 (1936), 230-265.
Yamada, H. Real-time computation and recursive functions not real-time computable. IEEE Trans. Elec. Comput. 11, 6 (1962), 753-760.
Younger, D.H. Recognition and parsing of context-free lan- guages in time n^3. Information and Control 10, 2 (1967), 189- 208.

作者簡介

作者簡介：JURIS HARTMANIS 是 Cornell University 電腦科學系的 Walter R. Read 工程學教授。目前的研究興趣包括 theory of computing、computational complexity 和 structural complexity。作者目前地址：Department of Computer Science, Cornell University, 5149 Upson Hall, Ithaca, NY 14853; email: jh@cs.cornell.edu

這項研究部分由 National Science Foundation 補助 #CCR-9123730 以及 Alexander von Humboldt Foundation 和位於 Germany Saarbruecken 的 Max Planck Institut fur Informatik 資助。