| Richard M. Karp | |||
|---|---|---|---|
 | |||
| Født | 3. jan. 1935 (91 år)Boston | ||
| Beskjeftigelse | Matematiker, informatiker, universitetslærer | ||
| Utdannet ved | Harvard University Harvard School of Engineering and Applied Sciences University of California, Berkeley | ||
| Doktorgrads- veileder | Anthony Oettinger | ||
| Nasjonalitet | USA | ||
| Medlem av | 8 oppføringer
| ||
| Utmerkelser | 18 oppføringer
Turing-prisen (1985)
John von Neumann Theory Prize (1990) Harvard Centennial Medal Harveyprisen (1998; statsborgerskap: USA) Fulkerson Prize (1979) National Medal of Science (1996) EATCS award (2000) Benjamin Franklin-medaljen (2004) Kyotoprisen for avansert teknologi (2008) Benjamin Franklin-medaljen (2004) Dickson Prize in Science (2009) Honorary doctorate of Technion Honorary fellow of Weizmann Institute ACM Fellow (1994) Fellow of the Society for Industrial and Applied Mathematics (2009) Frederick W. Lanchester Prize (1977) Honorary doctor of ETH Zürich Charles Babbage Award (1995) | ||
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.