理察·卡普（Richard Karp）1935年1月3日生於波士頓，從小時起就興趣廣泛，聰明過人。在哈佛大學時他文理兼修，1955年先獲得文學學士學位，第二年又獲得理科碩士學位。之後他進入哈佛大學的計算實驗室攻讀博士，於1959年取得套用數學博士學位。理察·卡普教授現任美國加州大學伯克利分校計算機科學講座教授，美國科學院、美國工程院、美國藝術與科學院、歐洲科學院院士。因其在計算機科學領域的基礎貢獻曾獲圖靈獎、馮諾依曼獎、美國國家科學勳章、哈佛大學百年獎章等獎項，還擔任美國科學院會刊（PNAS）等多個國際著名刊物編委。
基本介紹
- 中文名：理察·卡普
- 外文名：Richard Karp
- 國籍：美國
- 出生地：美國波士頓
- 出生日期：1935年1月3日
- 職業：教授
- 畢業院校：哈佛大學
- 主要成就：美國加州大學計算機科學講座教授
美國科學院、工程院院士
歐洲科學院院士
簡歷,分枝限界法,網路流問題,研究和發現,發表重要論文,
簡歷
卡普1935年1月3日生於波士頓，從小時起就興趣廣泛，聰明過人。在哈佛大學時他文理兼修，1955年先獲得文學學士學位，第二年又獲得理科碩士學位。之後他進入哈佛大學的計算實驗室攻讀博士，於1959年取得套用數學博士學位。
學成以後，他進入IBM位於Yorktown Heights的沃森研究中心，在那裡工作近10年。從20世紀50年代末至60年代，正是計算機科學的創建時期，高級語言剛誕生不久，計算機套用開始被社會所重視並逐漸走向普及。在這種情況下，有關數據結構、算法、計算複雜性等課題吸引著眾多學者的注意。IBM作為美國乃至世界最大的計算機廠商，理所當然地成為這些研究的中心之一，集中了大批最優秀的研究人員。
卡普在IBM期間，主要是深入研究了與實際套用有密切聯繫的一系列數學問題，如路徑問題、背包問題、覆蓋問題、匹配問題、分區問題、調度問題等，取得了許多出色的成果。這些問題有一個共同的特點，即如果用圖來表示問題，那么當圖中增加一個結點時，需要考察的可能的解的數目就急劇增加，形成所謂“組合爆炸”（combinatorial explosion），使計算機的計算工作量大大增加，到一定程度就根本無法實現。以路徑問題中最著名的旅行推銷員問題為例，在卡普以前，最好的結果是Rand公司的丹齊格（George Benard Dantzig）、福格申（R．Fulkerson）和詹森（S．Johnson）用手工和計算機相結合的辦法，求出了包含49個城市的旅行推銷員的最佳路線。卡普和他的同事海爾特(M．Held)經過反覆研究，終於提出了一種稱為“分枝限界法”（branch—and—bound method）的新方法，用這種新方法實現的算法使旅行推銷員能週遊的城市數達到65個，從而打破了由Rand公司保持的記錄。
分枝限界法
分枝限界法是一種構造性的探索法，可在整個允許的解空間中進行最優搜尋。該方法的要點是：對解集合反覆進行分枝，每次分枝時，都對所得的子集計算最優解的界。如果對某個子集求得的界不優於已知的允許解，則拋棄此子集不再進行分枝；否則繼續分枝以探索更好的解，直到所得的子集僅含有一個解時為止。分枝限界法就其實質而言是一種求解策略而非算法，具體算法要根據實際問題的特點去實現。但由於這種方法在求解許多問題中都非常實用，因此常常被直呼為“分枝限界算法”，在幾乎任何一本有關算法的書中都有介紹。
網路流問題
卡普還研究過最大網路流問題。這個問題給定一個包含起點和終點的有向圖，其中的每條邊都有一定的容量限制。如果把邊想像成管道，在其中流過某種物質，需要求出從起點到終點的最大物流量。這個問題對於輸油管道、輸氣管道、公路網、通信網的設計都有很重要的意義。解決這個問題的第一個算法是福特（L．Ford）和福格申（O．R．Fulkerson）在1956年提出的，算法的要點是：從流量0開始，反覆尋找滿足如下條件的所謂增量路徑：既能向該路徑中注入儘可能大的流量，又能保證所有的邊不超出飽和狀態，直至無法找到新的增量路徑為止。這個算法在多數情況下是有效的，但在某些特殊情況下效率很低，甚至無法給出答案。卡普和埃德蒙多（J．Edmonds）合作，在1969年對這個算法進行了改進，每次在尋找增量路徑時選擇包含的邊數最少的路徑，從而使算法的效率大大提高。改進後的算法的運行時間正比於結點數和邊數平方的乘積。
研究和發現
在對旅行推銷員問題進行研究的過程中，卡普發現，無論對算法作何種重大的改進，也無論用何種更高效的新算法使旅行推銷員能週遊的城市數進一步增加（包括後來採用一種稱為“多面體組合學”的方法把它轉變為線性規劃問題，從而使週遊城市數超過300），解題所需的時間總是問題規模（在這裡是城市數）的函式，且以指數方式增長。這引起卡普的深思，並促使他進入計算複雜性領域進行更深層次的研究。1967年，正好以色列學者、計算複雜性理論研究的先驅拉賓（M．Rabin，1976年圖靈獎獲得者）從希伯萊大學來到IBM公司的沃森研究中心作客座研究員，並且和卡普住在同一公寓大樓(卡普長期單身，直到1979年44歲才結婚成家），他們成了朋友，經常一起上下班，一起散步，拉賓在計算複雜性理論方面的深刻見解給了卡普很多啟發。
1968年，卡普離開IBM到加州大學伯克利分校工作。這裡是計算機科學理論的又一個研究中心，庫克(S．Cook，1982年圖靈獎獲得者)、布盧姆(M．Blum，1995年圖靈獎獲得者)等一批知名學者當時都在那裡，學術氣氛十分濃厚。布盧姆是計算複雜性理論的主要奠基人之一，庫克則於1971年最早提出“NP完全性”問題。在這樣的環境下，卡普對計算複雜性問題的研究日益深入。
發表重要論文
1972年，卡普發表了他的那篇著名的論文：“組合問題中的可歸約性”(Reducibility among Combinatorial Problems，見由R．E．Miller和J．W．Thatcher所編纂，由Plenum出版社出版的Complexity Of Computer Computations一書)。卡普的論文發展和加強了由庫克提出的“NP完全性”理論，尤其是，庫克僅證明了命題演算的可滿足問題是NP完全的，而卡普則證明了從組合最佳化中引出的大多數經典問題，包括背包問題、覆蓋問題、匹配問題、分區問題、路徑問題、調度問題等，都是NP完全問題。只要證明其中任一個問題是屬於P類的，就可解決計算複雜性理論中最大的一個難題，即P=?NP。這就是卡普論文的主要貢獻和主要意義。
這篇論文還有另外一些貢獻。其一就是對計算複雜性理論中的術語進行了規範和統一。把有多項式時間算法的問題命名為P類問題，就是卡普在這篇論文中首次採用的，現在已為學術界所接受並普遍採用，這為學術交流帶來了很大的好處。其二是卡普在刻畫NP類中的“最困難”問題類時，提出了與庫克歸約不同的另一種歸約方法，稱作“多項式時間多一歸約”，有時直接把它叫做“卡普歸約”。卡普歸約的要點如下：對於∑上的兩個語言L1、L2，在多項式時間可計算函式f:∑*→∑*，使得對任何x∈∑*，x∈L1若且唯若f(x)∈L2，則稱L1多項式時間多一歸約到L2，記為L1≤pmL2。這時，x∈Ll的判別可以通過計算f(x)，轉化成f(x)∈L2的判別。因此，Ll≤pmL2：更直觀地理解為11的計算難度不比上2大。同庫克歸約中的≤pt類似，≤pm也可定義在任何語言類D上，若存在L∈D，使對於任何L'∈D，都有L'，≤pmL，則稱乙為D—m完全的。其三，卡普的論文給出了“多項式譜系”或叫“多項式層次”(polynomial hierarchy)的基本思想。
