理查德·卡普 - 簡(jiǎn)介

理查德·卡普（Richard Karp）1935年1月3日生于波士頓，從小時(shí)起就興趣廣泛，聰明過人。在哈佛大學(xué)時(shí)他文理兼修，1955年先獲得文學(xué)學(xué)士學(xué)位，第二年又獲得理科碩士學(xué)位。之后他進(jìn)入哈佛大學(xué)的計(jì)算實(shí)驗(yàn)室攻讀博士，于1959年取得應(yīng)用數(shù)學(xué)博士學(xué)位。理查德·卡普教授現(xiàn)任美國(guó)加州大學(xué)伯克利分校計(jì)算機(jī)科學(xué)講座教授，美國(guó)科學(xué)院、美國(guó)工程院、美國(guó)藝術(shù)與科學(xué)院、歐洲科學(xué)院院士。因其在計(jì)算機(jī)科學(xué)領(lǐng)域的基礎(chǔ)貢獻(xiàn)曾獲圖靈獎(jiǎng)、馮諾依曼獎(jiǎng)、美國(guó)國(guó)家科學(xué)勛章、哈佛大學(xué)百年獎(jiǎng)?wù)碌泉?jiǎng)項(xiàng)，還擔(dān)任美國(guó)科學(xué)院會(huì)刊（PNAS）等多個(gè)國(guó)際著名刊物編委。

理查德·卡普 - 歷程

簡(jiǎn)歷

卡普1935年1月3日生于波士頓，從小時(shí)起就興趣廣泛，聰明過人。在哈佛大學(xué)時(shí)他文理兼修，1955年先獲得文學(xué)學(xué)士學(xué)位，第二年又獲得理科碩士學(xué)位。之后他進(jìn)入哈佛大學(xué)的計(jì)算實(shí)驗(yàn)室攻讀博士，于1959年取得應(yīng)用數(shù)學(xué)博士學(xué)位。

學(xué)成以后，他進(jìn)入IBM位于Yorktown Heights的沃森研究中心，在那里工作近10年。從20世紀(jì)50年代末至60年代，正是計(jì)算機(jī)科學(xué)的創(chuàng)建時(shí)期，高級(jí)語言剛誕生不久，計(jì)算機(jī)應(yīng)用開始被社會(huì)所重視并逐漸走向普及。在這種情況下，有關(guān)數(shù)據(jù)結(jié)構(gòu)、算法、計(jì)算復(fù)雜性等課題吸引著眾多學(xué)者的注意。IBM作為美國(guó)乃至世界最大的計(jì)算機(jī)廠商，理所當(dāng)然地成為這些研究的中心之一，集中了大批最優(yōu)秀的研究人員。

卡普在IBM期間，主要是深入研究了與實(shí)際應(yīng)用有密切聯(lián)系的一系列數(shù)學(xué)問題，如路徑問題、背包問題、覆蓋問題、匹配問題、分區(qū)問題、調(diào)度問題等，取得了許多出色的成果。這些問題有一個(gè)共同的特點(diǎn)，即如果用圖來表示問題，那末當(dāng)圖中增加一個(gè)結(jié)點(diǎn)時(shí)，需要考察的可能的解的數(shù)目就急劇增加，形成所謂“組合爆炸”（combinatorial explosion），使計(jì)算機(jī)的計(jì)算工作量大大增加，到一定程度就根本無法實(shí)現(xiàn)。以路徑問題中最著名的旅行推銷員問題為例，在卡普以前，最好的結(jié)果是Rand公司的丹齊格（George Benard Dantzig）、福格申（R．Fulkerson）和約翰遜（S．Johnson）用手工和計(jì)算機(jī)相結(jié)合的辦法，求出了包含49個(gè)城市的旅行推銷員的最佳路線�？ㄆ蘸退�的同事海爾特(M．Held)經(jīng)過反復(fù)研究，終于提出了一種稱為“分枝限界法”（branch—and—bound method）的新方法，用這種新方法實(shí)現(xiàn)的算法使旅行推銷員能周游的城市數(shù)達(dá)到65個(gè)，從而打破了由Rand公司保持的記錄。

分枝限界法

分枝限界法是一種構(gòu)造性的探索法，可在整個(gè)允許的解空間中進(jìn)行最優(yōu)搜索。該方法的要點(diǎn)是：對(duì)解集合反復(fù)進(jìn)行分枝，每次分枝時(shí)，都對(duì)所得的子集計(jì)算最優(yōu)解的界。如果對(duì)某個(gè)子集求得的界不優(yōu)于已知的允許解，則拋棄此子集不再進(jìn)行分枝；否則繼續(xù)分枝以探索更好的解，直到所得的子集僅含有一個(gè)解時(shí)為止。分枝限界法就其實(shí)質(zhì)而言是一種求解策略而非算法，具體算法要根據(jù)實(shí)際問題的特點(diǎn)去實(shí)現(xiàn)。但由于這種方法在求解許多問題中都非常實(shí)用，因此常常被直呼為“分枝限界算法”，在幾乎任何一本有關(guān)算法的書中都有介紹。

網(wǎng)絡(luò)流問題

卡普還研究過最大網(wǎng)絡(luò)流問題。這個(gè)問題給定一個(gè)包含起點(diǎn)和終點(diǎn)的有向圖，其中的每條邊都有一定的容量限制。如果把邊想象成管道，在其中流過某種物質(zhì)，需要求出從起點(diǎn)到終點(diǎn)的最大物流量。這個(gè)問題對(duì)于輸油管道、輸氣管道、公路網(wǎng)、通信網(wǎng)的設(shè)計(jì)都有很重要的意義。解決這個(gè)問題的第一個(gè)算法是福特（L．Ford）和福格申（O．R．Fulkerson）在1956年提出的，算法的要點(diǎn)是：從流量0開始，反復(fù)尋找滿足如下條件的所謂增量路徑：既能向該路徑中注入盡可能大的流量，又能保證所有的邊不超出飽和狀態(tài)，直至無法找到新的增量路徑為止。這個(gè)算法在多數(shù)情況下是有效的，但在某些特殊情況下效率很低，甚至無法給出答案。卡普和埃德蒙多（J．Edmonds）合作，在1969年對(duì)這個(gè)算法進(jìn)行了改進(jìn)，每次在尋找增量路徑時(shí)選擇包含的邊數(shù)最少的路徑，從而使算法的效率大大提高。改進(jìn)后的算法的運(yùn)行時(shí)間正比于結(jié)點(diǎn)數(shù)和邊數(shù)平方的乘積。

研究和發(fā)現(xiàn)

在對(duì)旅行推銷員問題進(jìn)行研究的過程中，卡普發(fā)現(xiàn)，無論對(duì)算法作何種重大的改進(jìn)，也無論用何種更高效的新算法使旅行推銷員能周游的城市數(shù)進(jìn)一步增加（包括后來采用一種稱為“多面體組合學(xué)”的方法把它轉(zhuǎn)變?yōu)榫�性規(guī)劃問題，從而使周游城市數(shù)超過300），解題所需的時(shí)間總是問題規(guī)模（在這里是城市數(shù)）的函數(shù)，且以指數(shù)方式增長(zhǎng)。這引起卡普的深思，并促使他進(jìn)入計(jì)算復(fù)雜性領(lǐng)域進(jìn)行更深層次的研究。1967年，正好以色列學(xué)者、計(jì)算復(fù)雜性理論研究的先驅(qū)拉賓（M．Rabin，1976年圖靈獎(jiǎng)獲得者）從希伯萊大學(xué)來到IBM公司的沃森研究中心作客座研究員，并且和卡普住在同一公寓大樓(卡普長(zhǎng)期單身，直到1979年44歲才結(jié)婚成家），他們成了朋友，經(jīng)常一起上下班，一起散步，拉賓在計(jì)算復(fù)雜性理論方面的深刻見解給了卡普很多啟發(fā)。

1968年，卡普離開IBM到加州大學(xué)伯克利分校工作。這里是計(jì)算機(jī)科學(xué)理論的又一個(gè)研究中心，庫(kù)克(S．Cook，1982年圖靈獎(jiǎng)獲得者)、布盧姆(M．Blum，1995年圖靈獎(jiǎng)獲得者)等一批知名學(xué)者當(dāng)時(shí)都在那里，學(xué)術(shù)氣氛十分濃厚。布盧姆是計(jì)算復(fù)雜性理論的主要奠基人之一，庫(kù)克則于1971年最早提出“NP完全性”問題。在這樣的環(huán)境下，卡普對(duì)計(jì)算復(fù)雜性問題的研究日益深入。

發(fā)表重要論文

1972年，卡普發(fā)表了他的那篇著名的論文：“組合問題中的可歸約性”(Reducibility among Combinatorial Problems，見由R．E．Miller和J．W．Thatcher所編纂，由Plenum出版社出版的Complexity Of Computer Computations一書)�？ㄆ盏恼撐陌l(fā)展和加強(qiáng)了由庫(kù)克提出的“NP完全性”理論，尤其是，庫(kù)克僅證明了命題演算的可滿足問題是NP完全的，而卡普則證明了從組合優(yōu)化中引出的大多數(shù)經(jīng)典問題，包括背包問題、覆蓋問題、匹配問題、分區(qū)問題、路徑問題、調(diào)度問題等，都是NP完全問題。只要證明其中任一個(gè)問題是屬于P類的，就可解決計(jì)算復(fù)雜性理論中最大的一個(gè)難題，即P=?NP。這就是卡普論文的主要貢獻(xiàn)和主要意義。

這篇論文還有另外一些貢獻(xiàn)。其一就是對(duì)計(jì)算復(fù)雜性理論中的術(shù)語進(jìn)行了規(guī)范和統(tǒng)一。把有多項(xiàng)式時(shí)間算法的問題命名為P類問題，就是卡普在這篇論文中首次采用的，現(xiàn)在已為學(xué)術(shù)界所接受并普遍采用，這為學(xué)術(shù)交流帶來了很大的好處。其二是卡普在刻畫NP類中的“最困難”問題類時(shí)，提出了與庫(kù)克歸約不同的另一種歸約方法，稱作“多項(xiàng)式時(shí)間多一歸約”，有時(shí)直接把它叫做“卡普歸約”�？ㄆ諝w約的要點(diǎn)如下：對(duì)于∑上的兩個(gè)語言L1、L2，在多項(xiàng)式時(shí)間可計(jì)算函數(shù)f:∑*→∑*，使得對(duì)任何x∈∑*，x∈L1當(dāng)且僅當(dāng)f(x)∈L2，則稱L1多項(xiàng)式時(shí)間多一歸約到L2，記為L(zhǎng)1≤pmL2。這時(shí)，x∈Ll的判別可以通過計(jì)算f(x)，轉(zhuǎn)化成f(x)∈L2的判別。因此，Ll≤pmL2：更直觀地理解為11的計(jì)算難度不比上2大。同庫(kù)克歸約中的≤pt類似，≤pm也可定義在任何語言類D上，若存在L∈D，使對(duì)于任何L’∈D，都有L’，≤pmL，則稱乙為D—m完全的。其三，卡普的論文給出了“多項(xiàng)式譜系”或叫“多項(xiàng)式層次”(polynomial hierarchy)的基本思想。

多項(xiàng)式譜系

所謂多項(xiàng)式譜系，就是從庫(kù)克歸約和卡普歸約出發(fā)，可建立P和NP類關(guān)于任何語言L的相對(duì)化定義，再自然推廣到任何語言類D上，得：
P(D)=∪P（L），NP（D）=∪NP（L）
L∈D
基于此，可將P和NP視為語言類上的一種算子，且有
D P（D） NP（D），P（P）=，NP（P）=NP
從語言類p開始，將算子NP重復(fù)地作用在其上，便產(chǎn)生一個(gè)語言類的無窮遞增序列：
P，NP，NP(NP)，NP(NP(NP))…
把它們依次記為∑p0,∑p1,∑p2,∑p3…
也即：
∑p0=P，∑Pk+1=NP（∑Pk），K≥0
這就形成了一個(gè)基本的復(fù)雜性類。此外可以定義與它相關(guān)的其他兩個(gè)復(fù)雜性類ⅡPK和Δpk 如下：
ⅡPK=Co-∑Pk={L ∑*|L∈∑Pk }
Richard Karp ΔpO= P，∑Pk+1=p（∑Pk），K≥0
這三種復(fù)雜性類有下述基本關(guān)系：
ΔpK ∑Pk∩ⅡPK，∑Pk∪ⅡPK ΔPk+1
由此可見，
∪∑Pk ∑Pk∪ⅡPK=∪ΔpK
K≥0 K≥0 K≥0
由∑Pk，ⅡPK及ΔPk (k≥0)所描述的層次結(jié)構(gòu)記為PH，即多項(xiàng)式譜系。
卡普給出了多項(xiàng)式譜系的基本思想后，由邁耶（A．Meyer）和斯托克邁耶（L．Stockmeyer）在1973年給出了嚴(yán)格形式化定義，拉特霍爾(C．Wrathall)又給出了有關(guān)定理，成為研究計(jì)算復(fù)雜性的一個(gè)重要工具。

其它貢獻(xiàn)

除了以上貢獻(xiàn)外，卡普在組合優(yōu)化算法的概率分析、隨機(jī)化算法等方面也有不少研究成果。近年來，卡普還致力于并行算法的研究，并有所創(chuàng)造。1996年11月，卡普和他在伯克利時(shí)的同事庫(kù)勒（D．Culler）等人在Communications of ACM上發(fā)表論文，提出了名為1ogP的一種并行算法的實(shí)用模型。這種模型的優(yōu)點(diǎn)是對(duì)分布存儲(chǔ)器并行機(jī)系統(tǒng)的通信開銷作了比較客觀和科學(xué)的概括，因而引起學(xué)術(shù)界的重視。我國(guó)中科院計(jì)算所的學(xué)者已經(jīng)基于LogP模型設(shè)計(jì)與實(shí)現(xiàn)了一種并行計(jì)算模擬器，取得了良好結(jié)果，詳情請(qǐng)參閱《計(jì)算機(jī)研究與發(fā)展》，1997年9月。

卡普由于其多方面的貢獻(xiàn)，獲得許多榮譽(yù)與獎(jiǎng)勵(lì)。除圖靈獎(jiǎng)以外，1978年他獲得美國(guó)運(yùn)籌學(xué)與工業(yè)管理學(xué)會(huì)頒發(fā)的Lanchster獎(jiǎng)，1979年美國(guó)數(shù)學(xué)會(huì)授予他Fulkerson獎(jiǎng)，1990年美國(guó)運(yùn)籌學(xué)會(huì)授予他馮·諾伊曼理論獎(jiǎng)，1995年他獲得Babbage獎(jiǎng)，1996年美國(guó)科學(xué)院授予他全國(guó)科學(xué)獎(jiǎng)?wù)拢∟ational Medal of Science）。早在1980年，卡普就已當(dāng)選為美國(guó)科學(xué)院院士。

卡普是在1985年10月于科羅拉多州的丹佛召開的ACM年會(huì)上接受圖靈獎(jiǎng)的。他的圖靈獎(jiǎng)演說題為“組合論、復(fù)雜性和隨機(jī)性”(Combinatorics，Complexity and Randomness)，是對(duì)上述課題的一個(gè)精彩綜述，并且給出了一張有關(guān)組合優(yōu)化和計(jì)算復(fù)雜性理論發(fā)展過程的年表，從1900年德國(guó)數(shù)學(xué)家希爾伯特提出“23個(gè)數(shù)學(xué)難題”開始，到20世紀(jì)80年代中期他演說時(shí)為止的進(jìn)展和成果，很有參考價(jià)值。頒獎(jiǎng)以后卡普還接受了記者卡倫·弗蘭克爾(Kren A．Frenkel)的采訪，演說全文和采訪時(shí)的對(duì)話刊載于Communications ofACM，1986年2月，98—117頁，或可見《前20年的圖靈獎(jiǎng)演說集》(ACM Turing Award Lectures ’The First Twenty Years：1966—1985，ACM pr．)，433-466頁。

卡普除了在IBM、伯克利工作過以外，還曾在密執(zhí)安大學(xué)、哥倫比亞大學(xué)、紐約大學(xué)和布魯克林(Brooklyn)理工學(xué)院任教。目前則在華盛頓大學(xué)計(jì)算機(jī)科學(xué)系，其電子信箱為: karp@cs.washington.edu 。

理查德·卡普 - 榮譽(yù)

獲得1985年度的圖靈獎(jiǎng)：有“三棲學(xué)者”美稱的理查德·卡普（Richard Manning Karp）獲得1985年度的圖靈獎(jiǎng)是眾望所歸的�？ㄆ罩�所以被稱為“三棲學(xué)者”是因?yàn)樗�知識(shí)淵博，貫通多個(gè)學(xué)科專業(yè)，因而同時(shí)被加州大學(xué)伯克利分校的電氣工程和計(jì)算機(jī)系、數(shù)學(xué)系以及工業(yè)工程和運(yùn)籌學(xué)系三個(gè)系聘為教授。這種情形在美國(guó)大學(xué)中都是不多見的。而卡普之所以被授予圖靈獎(jiǎng)，也是因?yàn)樗�在算法的設(shè)計(jì)與分析、計(jì)算復(fù)雜性理論、隨機(jī)化算法等諸多方面作出了創(chuàng)造性貢獻(xiàn)。

2008年第24屆京都獎(jiǎng)：

2008年6月20日，日本稻盛財(cái)團(tuán)在其官方網(wǎng)站上宣布，將2008年第24屆京都獎(jiǎng)（Kyoto Prize）授予美國(guó)和加拿大的三位科學(xué)家，以表彰他們對(duì)科學(xué)發(fā)展、文明進(jìn)步以及人類精神充實(shí)和提升的巨大貢獻(xiàn)。

京都獎(jiǎng)是國(guó)際科學(xué)大獎(jiǎng)，它每年頒發(fā)一次，分為先進(jìn)技術(shù)、基礎(chǔ)科學(xué)以及思想和藝術(shù)三大分支獎(jiǎng)項(xiàng)。每項(xiàng)獲獎(jiǎng)?wù)邔�獲得證書、20k金質(zhì)獎(jiǎng)?wù)潞?000萬日元的獎(jiǎng)金。

公告表示，2008年京都獎(jiǎng)先進(jìn)技術(shù)獎(jiǎng)授予美國(guó)加州大學(xué)伯克利分校的計(jì)算機(jī)理論學(xué)家Richard Manning Karp，以表彰他對(duì)“計(jì)算的復(fù)雜性理論（theory of computational complexity）發(fā)展的基礎(chǔ)性貢獻(xiàn)”。20世紀(jì)70年代，Karp確立了NP完全性理論（NP-completeness），這對(duì)算法分析和設(shè)計(jì)的指導(dǎo)方針具有深遠(yuǎn)的影響。此外，他還發(fā)展了許多實(shí)踐相關(guān)的計(jì)算機(jī)算法。

京都獎(jiǎng)基礎(chǔ)科學(xué)獎(jiǎng)獲得者是加拿大多倫多大學(xué)教授、西奈山醫(yī)院Samuel Lunenfeld研究所的Anthony James Pawson，他獲獎(jiǎng)的原因是“提出并證實(shí)了信號(hào)傳導(dǎo)中的轉(zhuǎn)接分子（Adapter Molecules）概念”。Pawson認(rèn)為，在信號(hào)蛋白中存在特殊的轉(zhuǎn)接器結(jié)構(gòu)SH2，它與特定磷酸化結(jié)構(gòu)域的“綁定”引導(dǎo)了細(xì)胞內(nèi)信號(hào)傳遞路徑，這些重要的信號(hào)控制著細(xì)胞生長(zhǎng)和分化。這一認(rèn)識(shí)確立了信號(hào)傳導(dǎo)的一種基本模式，對(duì)隨后生命科學(xué)的發(fā)展做出了重要貢獻(xiàn)。

京都獎(jiǎng)思想和藝術(shù)獎(jiǎng)由加拿大麥吉爾大學(xué)的退休教授、哲學(xué)家Charles Margrave Taylor獲得。他“構(gòu)建了一種追求多元文化共存的社會(huì)哲學(xué)體系”。

據(jù)悉，2008年京都獎(jiǎng)?lì)C獎(jiǎng)典禮將于11月10日在日本京都國(guó)際會(huì)議中心舉行。 

理查德·卡普 - 受聘

2008年6月18日下午，中關(guān)村教學(xué)園區(qū)S106教室內(nèi)座無虛席，來自美國(guó)加州大學(xué)Richard Karp教授受聘擔(dān)任中科院 “愛因斯坦講席教授”，研究生院教務(wù)長(zhǎng)蘇剛教授為Karp教授頒發(fā)了中科院“愛因斯坦講席教授”榮譽(yù)證書。隨后，Karp教授做了題為 “計(jì)算機(jī)科學(xué)是科學(xué)的透鏡” 的學(xué)術(shù)報(bào)告。

理查德·卡普教授現(xiàn)任美國(guó)加州大學(xué)伯克利分校計(jì)算機(jī)科學(xué)講座教授，美國(guó)科學(xué)院、美國(guó)工程院、美國(guó)藝術(shù)與科學(xué)院、歐洲科學(xué)院院士，因其在計(jì)算機(jī)科學(xué)領(lǐng)域的基礎(chǔ)貢獻(xiàn)曾獲圖靈獎(jiǎng)、馮諾依曼獎(jiǎng)、美國(guó)國(guó)家科學(xué)勛章、哈佛大學(xué)百年獎(jiǎng)?wù)碌泉?jiǎng)項(xiàng)，還擔(dān)任美國(guó)科學(xué)院會(huì)刊（PNAS）等多個(gè)國(guó)際著名刊物編委。

計(jì)算在各個(gè)科學(xué)領(lǐng)域日益成為不可或缺的工具，就像望遠(yuǎn)鏡和顯微鏡一樣。Karp教授的報(bào)告闡述了這種“計(jì)算透鏡”的基本科學(xué)問題，回顧“計(jì)算透鏡”如何推動(dòng)生物學(xué)、物理學(xué)、經(jīng)濟(jì)學(xué)、網(wǎng)絡(luò)科學(xué)的進(jìn)步。在生物學(xué)方面，無論是生物分子信息的獲取、分類和分析，還是基因的表達(dá)與翻譯，計(jì)算機(jī)科學(xué)發(fā)揮著不可替代的作用。而網(wǎng)絡(luò)計(jì)算的發(fā)展必將帶來更多的好處，并進(jìn)一步推動(dòng)網(wǎng)絡(luò)科學(xué)的發(fā)展。Karp教授還介紹加州大學(xué)伯克利分校的工作，包括因特網(wǎng)與Web、社會(huì)計(jì)算、量子計(jì)算、統(tǒng)計(jì)物理；討論生物學(xué)的計(jì)算過程，涉及蟻群行為、代謝通路、分子級(jí)進(jìn)化、蛋白質(zhì)網(wǎng)絡(luò)等應(yīng)用實(shí)例。

Karp教授的學(xué)術(shù)報(bào)告結(jié)束后，贏得了大家熱烈的掌聲。同學(xué)們的提問十分踴躍。Karp教授親切地與大家進(jìn)行了交流，對(duì)同學(xué)們的提問，Karp教授都一一給出了耐心細(xì)致的回答，現(xiàn)場(chǎng)不時(shí)發(fā)出陣陣笑聲。同學(xué)們感到與學(xué)術(shù)大師的直接交流能給大家今后的學(xué)術(shù)研究帶來啟發(fā)，對(duì)今后的學(xué)習(xí)、工作會(huì)產(chǎn)生深刻的影響。

中科院計(jì)算所副所長(zhǎng)徐志偉研究員、信息學(xué)院常務(wù)副院長(zhǎng)黃慶明教授等出席了學(xué)術(shù)報(bào)告會(huì)。