Richard M. Karp

Richard M. Karp (* 3. Januar 1935) ist ein amerikanischer Informatiker. Er ist verantwortlich für bedeutende Erkenntnisse in der Komplexitätstheorie.

Karp wurde in Boston, Massachusetts geboren. Er besuchte die Harvard University, wo er 1955 seinen Bachelor, 1956 seinen Master und 1959 seinen Ph.D. in Angewandter Mathematik absolvierte. Anschließend arbeitete er im IBM Thomas J. Watson Research Center. 1968 wurde er Professor für Informatik, Mathematik und Operations Research an der University of California, Berkeley. Von einer vierjährigen Periode als Professor an der University of Washington abgesehen, blieb er seither in Berkeley.

1971 entwickelte er mit Jack Edmonds den Edmonds-Karp-Algorithmus zur Lösung des Max-Flow-Problems in Netzwerken.

1972 veröffentlichte er einen Artikel, in dem er die NP-Vollständigkeit einer Reihe von graphentheoretischer Problemen nachwies, darunter das Hamilton-Tour-Problem, das Cliquen-Problem, und das Rucksack-Problem (Siehe: Karps 21 NP-vollständige Probleme).

1985 erhielt er für seine Forschungsarbeit auf dem Gebiet der Theorie der Algorithmen den Turing Award .

1987 entwickelte er gemeinsam mit Michael O. Rabin den Rabin-Karp-Algorithmus zur String-Suche.

Im Jahr 2004 erhielt er die Benjamin Franklin Medaille für Informatik und Kognitionswissenschaft aufgrund seiner Forschungsergebnisse auf dem Gebiet der Komplexitätstheorie.

Gourt Home::Gourt :: Richard M. Karp