リチャード＝カープの情報 （RichardManningKarp）
芸能人・有名人Wiki検索（誕生日、出身地）

リチャード＝カープのプロフィール Wikipedia（ウィキペディア）

リチャード・マニング・カープ（Richard Manning Karp、1935年1月3日 - ）は、計算機科学者にして計算理論家であり、計算理論の研究で知られている。カリフォルニア大学バークレー校に在籍。

ボストン生まれ。弟妹が3人いる。ハーバード大学で1955年に学士号、1956年に修士号、1959年に応用数学の博士号を取得した。

その後、IBMのトーマス・J・ワトソン研究所に勤務。1968年、カリフォルニア大学バークレー校の計算機科学、数学、オペレーションズリサーチに関する教授となった。4年間だけワシントン大学で教授を務めたが、それ以外は常にバークレーにとどまっていた。1988年から1995年までと、1995年以降、バークレーの国際計算機科学研究所（英語版）の研究員も務め、2012年現在は同研究所のアルゴリズム部門を指揮している。

カープは情報工学とオペレーションズリサーチに関わる組合せ最適化について多数の重要な発見をしている。彼の最近の研究テーマにはバイオインフォマティクスも含まれる。

1971年、ジャック・エドモンズ（英語版）と共同でネットワークの最大フロー問題を解くエドモンズ-カープアルゴリズムを開発した。1972年、計算複雑性理論における重要な論文 "Reducibility Among Combinatorial Problems"（組合せ問題間の還元可能性）を発表し、その中で21の問題がNP完全であること（英語版）を証明した。

1973年、ジョン・ホップクロフトと共同でホップクロフト–カープのアルゴリズム（英語版）を発表。これは2部グラフの最大マッチングを求める最速の技法である。

1980年、リチャード・J・リプトン（英語版）と共にカープ-リプトンの定理（英語版）を証明した。この定理は、多項式個の論理ゲートを使ったブール回路（英語版）でSATが解けるなら、その多項式階層が第2レベルに折りたたまれることを証明したものである。

1987年、マイケル・ラビンと共同でラビン-カープ文字列探索アルゴリズムを開発した。

1979年 - ファルカーソン賞

1985年 - チューリング賞

1990年 - ジョン・フォン・ノイマン理論賞

1994年 - Association for Computing Machinery フェロー

1996年 - アメリカ国家科学賞

1998年 - ハーヴェイ賞（イスラエル工科大学）

2004年 - ベンジャミン・フランクリン・メダル

2008年 - 京都賞先端技術部門、ディクソン賞科学部門（カーネギーメロン大学）

チューリング賞受賞理由は以下のとおり:

^ リチャード・カープ - Mathematics Genealogy Project

^ Richard M. Karp (1972). “Reducibility Among Combinatorial Problems”. In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103. http://www.cs.berkeley.edu/~luca/cs172/karp.pdf 

^ Richard Manning Karp Inamori Foundation

カリフォルニア大学バークレー校のホームページ

ACM Crossroads magazine interview/bio of Richard Karp

表

話

編

歴

アラン・パリス (1966)

モーリス・ウィルクス (1967)

リチャード・ハミング (1968)

マービン・ミンスキー (1969)

ジェームズ・H・ウィルキンソン (1970)

ジョン・マッカーシー (1971)

エドガー・ダイクストラ (1972)

チャールズ・バックマン (1973)

ドナルド・クヌース (1974)

アレン・ニューウェル / ハーバート・サイモン (1975)

マイケル・ラビン / デイナ・スコット (1976)

ジョン・バッカス (1977)

ロバート・フロイド (1978)

ケネス・アイバーソン (1979)

アントニー・ホーア (1980)

エドガー・F・コッド (1981)

スティーブン・クック (1982)

ケン・トンプソン / デニス・リッチー (1983)

ニクラウス・ヴィルト (1984)

リチャード・カープ (1985)

ジョン・ホップクロフト / ロバート・タージャン (1986)

ジョン・コック (1987)

アイバン・サザランド (1988)

ウィリアム・カハン (1989)

フェルナンド・J・コルバト (1990)

ロビン・ミルナー (1991)

バトラー・ランプソン (1992)

ユリス・ハルトマニス / リチャード・スターンズ (1993)

エドワード・ファイゲンバウム / ラジ・レディ (1994)

マヌエル・ブラム (1995)

アミール・プヌーリ (1996)

ダグラス・エンゲルバート (1997)

ジム・グレイ (1998)

フレデリック・ブルックス (1999)

アンドリュー・チーチー・ヤオ (2000)

オーレ＝ヨハン・ダール / クリステン・ニゴール (2001)

ロナルド・リベスト / アディ・シャミア / レオナルド・エーデルマン (2002)

アラン・ケイ (2003)

ヴィントン・サーフ / ロバート・カーン (2004)

ピーター・ナウア (2005)

フランシス・E・アレン (2006)

エドムンド・クラーク / アレン・エマーソン / ジョセフ・シファキス (2007)

バーバラ・リスコフ (2008)

チャック・サッカー (2009)

レスリー・ヴァリアント (2010)

ジューディア・パール (2011)

シャフィ・ゴールドワッサー / シルビオ・ミカリ (2012)

レスリー・ランポート (2013)

マイケル・ストーンブレーカー (2014)

マーティン・ヘルマン / ホイットフィールド・ディフィー (2015)

ティム・バーナーズ＝リー (2016)

ジョン・ヘネシー / デイビッド・パターソン (2017)

ヨシュア・ベンジオ / ジェフリー・ヒントン / ヤン・ルカン (2018)

エドウィン・キャットマル / パット・ハンラハン (2019)

アルフレッド・エイホ / ジェフリー・ウルマン (2020)

ジャック・ドンガラ (2021)

ロバート・メトカーフ (2022)

アヴィ・ヴィグダーソン (2023)

コンピュータ

カテゴリ

ISNI

VIAF

WorldCat

ノルウェー

フランス

BnF data

ドイツ

イスラエル

アメリカ

オランダ

計算機協会

CiNii Books

CiNii Research

DBLP

MathSciNet

Mathematics Genealogy Project

Scopus

zbMATH

SNAC

IdRef

20世紀の数学者

21世紀の数学者

20世紀アメリカ合衆国の数学者

21世紀アメリカ合衆国の数学者

アメリカ合衆国のオペレーションズ・リサーチャー

アメリカ合衆国のバイオインフォマティクス研究者

チューリング賞受賞者

アメリカ国家科学賞受賞者

京都賞先端技術部門受賞者

ベンジャミン・フランクリン・メダル (フランクリン協会) 受賞者

米国科学アカデミー会員

全米技術アカデミー会員

SIAMフェロー

ACMフェロー

カリフォルニア大学バークレー校の教員

ワシントン大学の教員

トーマス・J・ワトソン研究所の人物

ボストン出身の人物

数学に関する記事

1935年生

存命人物

ISNI識別子が指定されている記事

VIAF識別子が指定されている記事

WorldCat Entities識別子が指定されている記事

BIBSYS識別子が指定されている記事

BNF識別子が指定されている記事

BNFdata識別子が指定されている記事

GND識別子が指定されている記事

J9U識別子が指定されている記事

LCCN識別子が指定されている記事

NTA識別子が指定されている記事

ACM-DL識別子が指定されている記事

CINII識別子が指定されている記事

CRID識別子が指定されている記事

DBLP識別子が指定されている記事

MATHSN識別子が指定されている記事

MGP識別子が指定されている記事

Scopus識別子が指定されている記事

ZBMATH識別子が指定されている記事

SNAC-ID識別子が指定されている記事

SUDOC識別子が指定されている記事