編輯：Aeneas 桃子
【新智元導讀】
「計算複雜性」理論奠基人、1993年圖靈獎得主Juris Hartmanis去世，享年94歲。
又一巨星隕落。
7月29日，「計算複雜性」理論奠基人、1993年圖靈獎得主Juris Hartmanis去世，享年94歲。
首創康奈爾計算機科學系
1928年，Juris Hartmanis出生在蘇聯拉脫維亞（Latvia）共和國，父親是拉脫維亞軍隊將軍Mārtiņš Hartmanis，於1940年被捕入獄去世。
二戰結束時，Hartmanis帶著妻子和3個孩子移民到了德國，淪為「流民」。
Hartmanis的中學學業就是在德國哈瑙（Hanau）的難民營中完成的。1949年，他取得了馬爾堡大學（University of Marburg）物理學碩士學位。
兩年半後，也就是1950年，Hartmanis獲得資助便移居到了美國，進入堪薩斯大學（University of Kansas）攻讀碩士學位。
但由於該校沒有物理學的研究生課程，他只能改學數學。僅用了一年時間，他便在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），並奠定了它的理論基礎。
在此以前，已有拉賓（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日，這顆計算機領域的巨星隕落了，但我們會永遠記得他為計算機學界留下的寶貴遺產。
參考資料：
https：//rjlipton。wpcomstaging。com/2022/07/29/juris-hartmanis-1928-2022/