視頻加載中，請稍候...

自動播放

play

向前 向后

　　歡迎關(guān)注“新浪科技”的微信訂閱號：techsina 

　　來源：新智元　　

　　又一巨星隕落。

　　7月29日，“計算復(fù)雜性”理論奠基人、1993年圖靈獎得主Juris Hartmanis去世，享年94歲。

　　首創(chuàng)康奈爾計算機科學(xué)系

　　1928年，Juris Hartmanis出生在蘇聯(lián)拉脫維亞(Latvia)共和國，父親是拉脫維亞軍隊將軍Mārti?? Hartmanis，于1940年被捕入獄去世。

　　二戰(zhàn)結(jié)束時，Hartmanis帶著妻子和3個孩子移民到了德國，淪為“流民”。

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

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

　　Hartmanis介紹自己的人生經(jīng)歷

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

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

　　1955年-1957年，Hartmanis在康奈爾大學(xué)擔(dān)任數(shù)學(xué)教師，隨后加入俄亥俄州立大學(xué)數(shù)學(xué)系，擔(dān)任了一年的助理教授。

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

　　因為那里新建立了一個“信息研究部”開展有關(guān)計算機和信息學(xué)的研究，這一新的領(lǐng)域激發(fā)起了Hartmanis極大的興趣和熱情。

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

　　直到1965年，Hartmanis重返康奈爾大學(xué)，擔(dān)任教授。

　　他的這次回歸，不是數(shù)學(xué)系，而是領(lǐng)導(dǎo)并成立了康奈爾大學(xué)計算機科學(xué)系——世界最早的計算機科學(xué)系之一。

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

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

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

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

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

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

　　1996-1998年，他離開康奈爾大學(xué)，擔(dān)任國家科學(xué)基金會助理主任，領(lǐng)導(dǎo)計算機和信息科學(xué)與工程理事會。

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

　　另外，他還是美國計算機協(xié)會和美國數(shù)學(xué)協(xié)會的會員，也是美國國家科學(xué)院院士。

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

　　1988年，為了紀念Juris Hartmanis 60歲誕辰，由Alan Selman，因?qū)Y(jié)構(gòu)復(fù)雜性理論的研究而聞名，撰寫的一本紀念文集《復(fù)雜性理論回顧》（Complexity Theory Retrospective）一書出版。

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

　　“計算復(fù)雜性”理論奠基人

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

　　這篇論文開辟了計算機科學(xué)的一個新的研究領(lǐng)域，即“計算復(fù)雜性”（computational complexity），并奠定了它的理論基礎(chǔ)。

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

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

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

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

　　在論文中，他們?yōu)閳D靈機引入了時間復(fù)雜度類 TIME (f (n))，并證明了這一時間層次定理。

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

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

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

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

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

　　在1955年，Hartmanis取得了博士學(xué)位，進入康乃爾大學(xué)數(shù)學(xué)系任教。

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

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

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

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

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

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

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

　　他們的第一個合作課題是關(guān)于時序機的狀態(tài)分派問題。暑假結(jié)束時，他們已經(jīng)完成了一篇合作論文，這就是第二年發(fā)表于IRE Trans．on EC的On the state assignment problem for sequential machines。

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

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

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

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

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

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

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

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

　　他們這種在學(xué)術(shù)上平等待人、互相尊重、善于交流的作風(fēng)，十分令人敬重。

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

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

　　2022年7月29日，這顆計算機領(lǐng)域的巨星隕落了，但我們會永遠記得他為計算機學(xué)界留下的寶貴遺產(chǎn)。

（聲明：本文僅代表作者觀點，不代表新浪網(wǎng)立場。）