,,

觀速訊丨圖靈獎得主、“計算復雜性”理論奠基人Juris Hartmanis逝世享年94歲

2022-07-31 15:42:36 來源：創事記

又一巨星隕落。7月29日，“計算復雜性”理論奠基人、1993年圖靈獎得主Juris Hartmanis去世，享年94歲。1928年，Juris Hartmanis出生在蘇聯拉脫維亞(Latvia)共和國，父親是拉脫維亞軍隊將軍Mārti?? Hartmanis，于1940年被捕入獄去世。二戰結束時，Hartmanis帶著妻子和3個孩子移民到了德國，淪為“流民”。

訪問：

(資料圖)

阿里云服務器精選特惠：1核1G云服務器低至0.9元/月

首創康奈爾計算機科學系

Hartmanis的中學學業就是在德國哈瑙(Hanau)的難民營中完成的。1949年，他取得了馬爾堡大學（University of Marburg）物理學碩士學位。

兩年半后，也就是1950年，Hartmanis獲得資助便移居到了美國，進入堪薩斯大學（University of Kansas）攻讀碩士學位。

Hartmanis介紹自己的人生經歷

但由于該校沒有物理學的研究生課程，他只能改學數學。僅用了一年時間，他便在1951年取得了數學碩士學位。

緊接著，他被加州理工學院（Caltech）接收為博士研究生，從事格論 (latticetheory) 的研究。1955年在美國著名數學家Robert P. Dilworth指導下，取得了數學博士學位。

1955年-1957年，Hartmanis在康奈爾大學擔任數學教師，隨后加入俄亥俄州立大學數學系，擔任了一年的助理教授。

之后，他便加入了通用電氣公司設在紐約州斯克內克塔迪 (Schenectady) 的研究實驗室。

因為那里新建立了一個“信息研究部”開展有關計算機和信息學的研究，這一新的領域激發起了Hartmanis極大的興趣和熱情。

在通用電氣，Hartmanis工作了7年，并發展了許多計算復雜性理論原則。

直到1965年，Hartmanis重返康奈爾大學，擔任教授。

他的這次回歸，不是數學系，而是領導并成立了康奈爾大學計算機科學系——世界最早的計算機科學系之一。

由于他的眼光和魄力，也由于他的民主作風，康乃爾大學的計算機科學系吸引了一批著名學者加盟，成為美國大學中水平最高、影響最大的計算機科學系之一。

這些學者中包括霍普克洛夫特(J．E．Hopcroft，1986年圖靈獎得主)、格利斯(D．Giles，1995年ACM優秀計算機教育獎獲得者)、霍洛維茨(E．Horowitz)、韋格納(P．Wegner)和肖(A．Shaw)等。

Hartmanis曾三次擔任計算機科學系主任(1965-71年、1977-83年和1992-93年) ，并于1980年成為沃爾特?里德(Walter R. Reed) 工程學教授。

從教多年，Hartmanis一共有21個杰出的博士研究生。

可以看到，1986年從康奈爾大學畢業的華裔數學家和計算機科學家Jin-Yi Cai（蔡進一）便是其中一位。

也正是在1965年這段時間里，Hartmanis和Richard Stearns一起創立了計算復雜性理論，憑借這一成就摘取了1993年的圖靈獎。

1996-1998年，他離開康奈爾大學，擔任國家科學基金會助理主任，領導計算機和信息科學與工程理事會。

1989年，Hartmanis被選為美國國家工程院院士，因為他對計算復雜性理論、計算機研究和教育做出了重大貢獻。

另外，他還是美國計算機協會和美國數學協會的會員，也是美國國家科學院院士。

1999年5月，密蘇里大學授予了他人道主義文學榮譽博士的稱號。

1988年，為了紀念Juris Hartmanis 60歲誕辰，由Alan Selman，因對結構復雜性理論的研究而聞名，撰寫的一本紀念文集《復雜性理論回顧》（Complexity Theory Retrospective）一書出版。

其中包括若干對Hartmanis的生平和成就的介紹文章。

“計算復雜性”理論奠基人

1965年，Juris Hartmanis和Richard Stearns合作發表了題為《論算法的計算復雜性》On the Computational Complexity of Algorithms 開創性論文，并因此獲得了1993年的圖靈獎。

這篇論文開辟了計算機科學的一個新的研究領域，即“計算復雜性”（computational complexity），并奠定了它的理論基礎。

Hartmanis介紹了他在通用電氣開始與Richard Stearns合作進行復雜性研究

在此以前，已有拉賓（M．O．Rabin）、庫克（S．A．Cook）、卡普（R．M．Karp）等學者因在計算復雜性理論研究中作出先驅性工作而分別在1976年、1982年和1985年獲得圖靈獎。

Hartmanis和Stearns則在前人工作的基礎上，比較完整地提出了計算復雜性的理論體系，并首次正式命名了“計算復雜性”，因而被公認為計算復雜性理論的主要創始人。

用一句話概括這篇論文的影響，那就是——它使圖靈的tape公式經久耐用。

在論文中，他們為圖靈機引入了時間復雜度類 TIME (f (n))，并證明了這一時間層次定理。

他們證明了特殊情況下的復雜性層次成為一般理論的計算復雜性。盡管主要使用多帶圖靈機，但他們認為，這些概念是普遍的，同樣的結果會出現在任何合理的模型中。

他們還證明了一些關于模型更改（1-tape、2-tape、1-dim、2-dim ）如何改變 DTIME(T(n)) 概念的定理。

現在，人們已經習慣于這樣的概念：我們可以測量在圖靈機上計算步數需要的時間。不過，在 Hartmanis-Stearns論文發表之前，人們并不是這么想的。正是他們開啟了所謂的復雜性理論。

如果 Hartmanis-Stearns沒有開啟這一將復雜性置于嚴格的數學基礎上的過程，那么復雜性理論會如何發展？我們可能就無法得出Cook-Levin定理或NP的概念了。

說起讓他得到圖靈獎的這篇論文，背后還有這樣一段有趣的故事。

在1955年，Hartmanis取得了博士學位，進入康乃爾大學數學系任教。

但他在那里只工作了一年多，就轉入了通用電氣公司。

這一新的領域激發起了Hartmanis極大的興趣和熱情。此時他還沒意識到，圖靈獎在日后即將向它招手。

當時，香農（Claude Elwood Shanon）的信息論問世不久，香農總結出了一個公式，可以計算在一定的信號和噪聲平均功率之下，給定帶寬的信道在單位時間內的最大信息傳輸量（這個公式被叫做“香農公式”）。

念過物理的Hartmanis受此啟發，敏銳地想到，抽象的計算過程也應該有精確的定量法則，以確定為了對每一個問題求得解答，需要多少計算工作量。

圍繞這一設想，Hartmanis和同事Stearns合作，開展了深入的研究，其結果就是那篇著名的論文《論算法的計算復雜性》。

說起Hartmanis的好搭檔Stearns，他會跨進計算機科學的大門并成為一名出色的計算機科學家，還是一件十分偶然的事。

1960年暑假他到通用電氣公司打工，被分配到研究實驗室新成立的信息研究部，這使他有緣與已成為通用正式職工的Hartmanis一起工作。學過物理而后改行數學的Hartmanis和專攻數學的Stearns開始合作后，雙方取長補短，相得益彰，這使他們的合作成果頗豐。

他們的第一個合作課題是關于時序機的狀態分派問題。暑假結束時，他們已經完成了一篇合作論文，這就是第二年發表于IRE Trans．on EC的On the state assignment problem for sequential machines。

這次暑期臨時工的經歷，讓Stearns在拿到博士學位后毫不猶豫地應聘到通用電氣公司工作，與Hartmanis再度攜手，終于再創輝煌，很快完成了奠定計算復雜性理論基礎的上述著名論文。不可思議的是，Hartmanis和Stearns在通用電氣公司研究計算復雜性的最初幾年，實驗室里并無計算機可用。這在今天的人們看來簡直是不可想象的。

他們當時完全是依靠嚴密的理論分析才能提出有關計算復雜性的一系列問題，并給出了科學的解釋。直到1964年，實驗室才配了一臺GE 300，他們這才開始用BASIC編程，通過電傳打字機接口使用計算機。

在科學技術的發展史上，開創復雜而重要的學科領域并取得巨大成功的學者，最初往往在十分困難的條件下工作，這種情況屢見不鮮。在Hartmanis和Stearns在研究“計算復雜性”理論的過程中，還有一個細節值得一提。

據Stearns本人回憶，他們首次明確提出“計算復雜性”這一名詞的論文有過三個版本：最早是1963年4月實驗室內部的一個研究報告，沒有公開發表；然后是在1964年于普林斯頓舉行的IEEE第五屆開關電路理論和邏輯設計學術年會上提交的論文，題為“遞歸序列的計算復雜性”(Computational Complexity of Recursive Sequences)；第三個版本是發表于美國數學會匯刊1965年5月上的“論算法的計算復雜性”（On the Computational Complexity of Algorithms）。

這三個版本中，會議版本雖然早于雜志版本發表，但實際上卻是最后一個版本。因為在此之前，他們并不知道Manuel Blum（1995年圖靈獎得主）在MIT的博士論文研究的是同一問題；會議之前他們偶然獲知這一情況，便立即去MIT拜訪了Blum。

當時，Hartmanis和Stearns已是國際知名大公司的研究人員，而Blum則不過是來自南美小國委內瑞拉的青年學子。

曼紐爾·布盧姆（Manuel Blum），1995年圖靈獎得主

但Hartmanis和Stearns并不因此而對Blum有任何輕視，并且發現Blum在對“復雜性類”等方面的研究比他們還深入一些，因此對Blum十分推崇，并把他的博士論文列入了他們自己的會議論文的參考文獻之中，雖然該博士論文當時尚未公開。

他們這種在學術上平等待人、互相尊重、善于交流的作風，十分令人敬重。

1993年，Hartmanis在接受圖靈獎時發了表題為“論計算復雜性及計算機科學的性質”（On Computational Complexity and the Nature of Computer Science）的演說。

1997年，Hartmanis和Leonard Berman在合作的一篇論文中提出了Berman-Hartmanis猜想: 所有 NP 完備語言都是多項式時間同構的。

2022年7月29日，這顆計算機領域的巨星隕落了，但我們會永遠記得他為計算機學界留下的寶貴遺產。

關鍵詞：圖靈獎得主、計算復雜性理論奠基人Juris Hartm