姚期智：開華裔獲圖靈獎的先河
世紀的第一個春天剛剛來臨，從大洋彼岸就傳來一個令人振奮的消息：
美國計算機學會(ACM)決定把2000年度的圖靈獎授予華裔計算機科學家、
現普林斯頓大學教授姚期智。這是有“計算機世界的諾貝爾獎”之稱的
圖靈獎35年來首次授予一位華裔學者，是值得全世界華人為之驕傲的。
姚期智(Yao Chi-chih)的英文名字是安德魯·姚(Andrew C.Yao)。
他祖藉湖北孝感，1946年12月24日出生於上海，幼年隨父母去台灣省。1
967年在台灣大學畢業以後，去美國深造，原先所學專業是物理
。但20世紀60年代以來計算機技術的迅猛發展和計算機在各行各業的廣
泛應用吸引了他的目光，他敏銳地意識到這是一個十分重要並具有巨大發
展空間的新興學科，從而決心放棄原先專業而轉到計算機科學上來。因此，
在1972年取得令人羨慕的哈佛大學物理學博士學位以後，他又來到伊利諾
大學研究生院繼續學習。伊利諾大學在計算機科學技術方面處於美國領先地位。
姚期智於1975年在伊利諾大學取得他的第二個博士學位——計算機科學博士學位。
之後，他曾先後在麻省理工學院(1975～1976)、斯坦福大學(1976～1981，
1983～1986)、加州大學伯克利分校(1981～1983)等美國著名高等學府從事
教學與研究，1986年加盟普林斯頓大學至今。
姚期智對計算機科學技術所作出的貢獻主要在計算理論方面。ACM在授獎
決定中指出，姚期智對計算理論的眾多貢獻是根本性的、意義重大的，
其中包括基於複雜性的偽隨機數生成理論、密碼學和通信複雜性。最近
1/4個世紀中姚期智發表的近百篇學術論文，幾乎覆蓋了計算複雜性的
所有方面。姚期智進入計算機科學領域最早的論文之一《尋找最小生成
樹的O(|E|log log|V|)算法》一文就引起轟動，因為學術界原先認為，
尋找最小生成樹算法的時間複雜度的下界是O(E log V)，而姚期智的論
文證明這個極限是可以打破的。在姚的這一開創性工作的基礎上，經過近
20年的努力，人們終於設計出了尋找最小生成樹的線性時間算法。
在數據組織方面，人們歷來以為排序表(Sorted Table)是一種良好的結
構，在其中檢索信息有最快的響應。姚期智經過深入研究，發現這只在少
數特定條件下才成立，而對於允許有任意信息編碼的表而言，在排序表中
檢索信息的效率遠不是最佳的。他的研究結果在《表應該被排序嗎?》一
文中發表以後，人們對信息應如何有效地存儲在認識上發生了革命性的變
化。該文為後來出現最佳概率化哈希模式和字典實現方式奠定了基礎。姚
在該文中所採用的證明方法則被稱為“Cell Probe”模型而被廣泛應用
，在數據結構和算法的分析與設計的研究中產生了深遠的影響。
姚期智對偽隨機數生成理論的諸多貢獻集中反映在他1982年的論文《活板
門函數的理論和應用》中。在這篇有開創性意義的論文中，姚期智先證明
了著名的BlumMicali發生器所產生的隨機數實際上是偽隨機的，並由此
導出了在隨機數生成技術中一個十分重要的概念，即“隨機性和難度”的
折衷。論文還首次定義了“計算熵”(Computational Entropy)的概念，
對它進行了深入研究，引出了一系列有關定理和推論，推動了密碼學的發
展。而姚期智自己則在1986年的論文《如何產生和交換秘密信息》中進一
步提出了一種稱為“健忘的電路模擬”的密碼技術，利用這種技術能秘密
而可靠地計算出任意函數。
隨着Internet的普及和互聯網的飛速發展，對通信複雜性的研究成為姚關
注的一個重點。他在這方面發表的論文如《電路和通信複雜性的近期進展》
被認為是經典之作，經常被其他論文引用。姚期智為通信建立了基本模型，
提出了分析方法，從而使通信複雜性發展成為一個重要的研究領域，並獲
得了多方面的和意想不到的應用。
姚期智近期的研究集中於量子通信和計算。量子計算是以量子力學理論和
量子器件為基礎、新近發展起來的一種新的計算技術，它不但能降低傳統
計算技術的計算複雜性，還能解決一些傳統計算機根本無法處理的問題。
姚期智在DARPA/ITO的資助下，已經在這方面的研究中取得若干成果，
發表了一些引人注目的論文，如《Quantum Bit Escrow》、
《Quantum Cryptography with Imperfect Apparatus》、
《Security of Quantum Protocol against Coherent Measurements》等。
在此次榮獲圖靈獎之前，姚期智在1996年獲得以算法設計大師
克努特(Donald Ervin Knuth,1994年圖靈獎獲得者)命名的首
屆克努特獎。去年4月，姚期智被選為美國藝術和科學院院士，
他也是我國《軟件學報》(英文版)的副主編，曾到祖國內地參加學術活動。
姚期智的夫人弗朗西絲·姚(Frances F.Yao)也是來自中
國台灣省的華裔科學家，他們是志趣相投的一對伉儷，曾聯名發表許多研究論文。
