Richard M. Karp

Richard Manning Karp (født 3. januar 1935 i Boston) er en amerikansk informatiker som har gitt betydningsfulle bidrag til forskning innen kompleksitetsteori. For dette arbeidet mottok han Turing-prisen i 1985.

Karp gikk på Harvard University hvor han tok bachelorgraden i 1955, mastergraden i 1956 og doktorgraden i anvendt matematikk i 1959. Deretter jobbet han på Thomas J. Watson Research Center hos IBM. I 1968 ble han professor i informatikk, matematikk og operations research ved University of California, Berkeley. Siden det har han vært i Berkeley, med unntak av fire år hvor han arbeidet som professor ved University of Washington. Karp mottok også Benjamin Franklin-medaljen i 2004 i informatikk og kognitiv vitenskap for bidragene sine innen kompleksitetsteori.

I 1971 utviklet han Edmonds-Karp-algoritmen for maks-flyt-problemet sammen med Jack Edmonds, og i 1972 publiserte han en viktig artikkel i kompleksitetsteori, Reducibility Among Combinatorial Problems hvor han viste at 21 problemer er NP-fullstendige. I 1987 utviklet han Rabin-Karp-algoritmen for tekstsøking sammen med Michael O. Rabin.

Han har gjort mange andre viktige oppdagelser i informatikk, spesielt i kombinatorisk optimalisering. For tiden er hans viktigste forskningsområde bioinformatikk.

Referanser

Eksterne lenker 
 
 Intervju med Richard Karp i ACM Crossroads magazine (engelsk)
 Karps hjemmeside hos Berkeley (engelsk)

Informatikere fra USA
Mottagere av Turing-prisen
Personer tilknyttet Harvard
Medlemmer av Det franske vitenskapsakademiet
Personer fra Boston
Fødsler i 1935