![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Karp_mg_7725-b.cr2.jpg/640px-Karp_mg_7725-b.cr2.jpg&w=640&q=50)
理察·卡普
維基百科,自由的 encyclopedia
理察·曼寧·卡普(英語:Richard Manning Karp,1935年1月3日—)是一名美國計算機科學家和計算理論家。他因在計算理論方面的研究而知名,並於1985年獲得圖靈獎,2004年獲得班傑明·富蘭克林計算機和認知科學獎,2008年獲得京都獎[2]。
由於在NP完備性的理論和應用、構建高效組合算法以及在計算機科學中應用概率方法方面的重大貢獻,卡普於1992年獲選為美國國家工程院院士。
生平
卡普於1935年1月3日出生於麻薩諸塞州波士頓的猶太裔家庭[3],父親是亞伯拉罕·卡普(Abraham Karp),母親是蘿絲·卡普(Rose Karp)。他有三個弟妹,分別是羅伯特(Robert)、大衛(英語:David A. Karp)和卡羅琳(Carolyn)。他在當時主要是猶太人的波士頓多爾切斯特(英語:Dorchester, Boston)社區的一個小公寓裡長大。
卡普的父母都是哈佛大學的畢業生(他的母親在參加夜校課程後,最終在57歲時獲得哈佛大學的學位),而他的父親在哈佛大學畢業後曾有過就讀醫學院的野心,但由於無力支付醫學院的學費而成為一名數學教師[3]。卡普就讀於哈佛大學,1955年獲得學士學位,1956年獲得碩士學位,1959年獲得應用數學博士學位。之後他開始在IBM的托馬斯·J·沃森研究中心(英語:Thomas J. Watson Research Center)工作。
1968年,卡普成為加利福尼亞大學柏克萊分校的計算機科學、數學和運籌學教授。他是電子工程和計算機科學系內計算機科學部的首位副主席[4]。除了在華盛頓大學擔任過4年的教授外,他一直居住在柏克萊。1988年至1995年和1999年至今,他還在柏克萊的國際計算機科學研究所(英語:International Computer Science Institute)擔任研究科學家,目前他在那裡領導算法組。
卡普被授予美國國家科學獎章,並因其在計算複雜性方面的見解而獲得以色列理工學院的哈維獎(英語:Harvey Prize)和2004年班傑明·富蘭克林計算機和認知科學獎。1994年,他獲選為計算機協會的會士。2002年,他獲選為運籌學和管理科學研究所(英語:Institute for Operations Research and the Management Sciences)的研究員[5]。他是多個榮譽學位的獲得者,也是美國國家科學院[6]、美國文理科學院[7]和美國哲學會[8]的成員。
2012年,卡普成為加利福尼亞大學柏克萊分校西蒙斯計算理論研究所(英語:Simons Institute for the Theory of Computing)的創始主任[9]。
研究工作
卡普在計算機科學、組合算法和運籌學方面有許多重要發現。他目前的主要研究興趣包括生物資訊學。
1962年,他與邁克爾·赫爾德(Michael Held)共同開發了赫爾德-卡普算法(英語:Held–Karp algorithm),這是一種針對旅行推銷員問題的精確指數時間算法。
1971年,他與傑克·埃德蒙茲(英語:Jack Edmonds)共同開發了埃德蒙茲-卡普演算法,用於解決網路上的最大流問題。1972年,他發表一篇在複雜性理論中具有里程碑意義的論文《組合問題中的可減少性》,其中他證明了21個NP-完全問題[10]。
1973年,他和約翰·霍普克羅夫特發表了霍普克洛夫特-卡普算法,這是已知的在二分圖中尋找最大勢匹配的最快方法。
1980年,卡普與理察·利普頓(英語:Richard Lipton)一起證明了卡普-利普頓定理(英語:Karp–Lipton theorem)。該定理證明,如果布爾可滿足性問題可以由具有多項式邏輯閘數量的布爾電路(英語:Boolean circuit)來解決,那麼多項式譜系就會坍縮到其第二層。
圖靈獎
他對(1985年)圖靈獎的引文[11]如下:
由於他對算法理論的持續貢獻,包括對網路流和其他組合優化問題的高效算法的發展,對多項式時間可計算性與算法效率的直觀概念的識別,以及最引人注目的對NP完備性理論的貢獻。卡普引入了現在證明問題為NP-完備的標準方法,這導致許多理論和實際問題被認定為計算上的困難。
參考資料
- The Power and Limits of Algorithms (頁面存檔備份,存於網際網路檔案館) Richard Manning Karp, Kyoto Prize Address, 2008
- Karp, Richard. A Personal View of Computer Science at Berkeley. www2.eecs.berkeley.edu. [1 December 2021]. (原始內容存檔於2016-03-04).
- Fellows: Alphabetical List, Institute for Operations Research and the Management Sciences, [2019-10-09], (原始內容存檔於2019-05-10)
- Richard M. Karp. www.nasonline.org. [2022-02-22]. (原始內容存檔於2023-06-07).
- Richard M. Karp. American Academy of Arts & Sciences. [2022-02-22]. (原始內容存檔於2023-06-07) (英語).
- APS Member History. search.amphilsoc.org. [2022-02-22]. (原始內容存檔於2023-06-07).
- California Chosen as Home for Computing Institute. The New York Times. 30 April 2012 [23 October 2016]. (原始內容存檔於2023-06-07).
- Richard M. Karp. Reducibility Among Combinatorial Problems (PDF). R. E. Miller; J. W. Thatcher (編). Complexity of Computer Computations. New York: Plenum. 1972: 85–103 [2023-06-07]. (原始內容 (PDF)存檔於2011-06-29).
- Association for Computing Machinery. ACM Award Citation/Richard M. Karp. [2010-01-17]. (原始內容存檔於2012-07-03).
外部連結
- ACM Crossroads magazine interview/bio of Richard Karp
- Karp's Home Page at Berkeley (頁面存檔備份,存於網際網路檔案館)
- Biography of Richard Karp (頁面存檔備份,存於網際網路檔案館) from the Institute for Operations Research and the Management Sciences