又一巨星隕落。7月29日，“計算復雜性”理論奠基人、1993年圖靈獎得主JurisHartmanis去世，享年94歲。1928年，JurisHartmanis出生在蘇聯拉脫維亞(Latvia)共和國，父親是拉脫維亞軍隊將軍MārtiņšHartmanis，於1940年被捕入獄去世。二戰結束時，Hartmanis帶著妻子和3個孩子移民到德國，淪為“流民”。
首創康奈爾計算機科學系
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日，這顆計算機領域的巨星隕落，但我們會永遠記得他為計算機學界留下的寶貴遺產。