| Richard M. Karp | ||
|---|---|---|
| ||
Richard Karp in 2009
| ||
| Persoonlijke gegevens | ||
| Volledige naam | Richard Manning Karp | |
| Geboortedatum | 3 januari 1935 | |
| Geboorteplaats | Boston (Verenigde Staten) | |
| Academische achtergrond | ||
| Alma mater | Harvard-universiteit Universiteit van Californië - Berkeley 
| |
| Promotor | Anthony Oettinger[1] | |
| Wetenschappelijk werk | ||
| Vakgebied | Informatica | |
| Bekend van | A simple algorithm for finding frequent elements in streams and bags
| |
| Website | ||
Richard M. Karp (Boston, 3 januari 1935) is een Amerikaans informaticus aan de universiteit van Berkeley. Voor zijn bijdragen aan de complexiteitstheorie kreeg hij in 1985 de Turing Award.
Biografie
Karp werd op 3 januari 1935 geboren in Boston en ging naar de Boston Latin School. Hij studeerde aan de Harvard-universiteit en promoveerde daar in 1959 in de toegepaste wiskunde. Tussen 1959 en 1968 werkte hij bij de onderzoeksafdeling van IBM.
Zijn belangrijkste wetenschappelijke bijdragen deed Karp in de periode van 1968 tot 1994 als hoogleraar aan de Universiteit van Californië in Berkeley. Van 1994 tot 1999 was hij hoogleraar aan de Universiteit van Washington, waarna hij als universiteitshoogleraar terugkeerde in Berkeley.
Werk
Karp heeft belangrijke bijdragen geleverd aan de complexiteitstheorie en operationeel onderzoek. Tegenwoordig houdt hij zich vooral bezig met bio-informatica.
In 1972 publiceerde hij het artikel Reducability among Combinatorial Problems,[2] waarin hij van 21 beslissingsproblemen bewees dat ze NP-volledig zijn, door het vervulbaarheidsprobleem, direct en indirect, naar hen te reduceren. Hiermee gaf hij een belangrijke impuls aan het bestuderen van de complexiteitsklasse NP en de vraag of de complexiteitsklassen P en NP gelijk zijn.
Karp was mede-ontdekker van het Edmonds-Karp-algoritme om de maximale stroom in grafen te bepalen (1971), het Hopcroft-Karp-algoritme om de grootste onafhankelijke kantenverzameling van bipartiete grafen te bepalen (1980) en het Rabin-Karp-algoritme voor zoeken in strings (1987).
In 1980 bewees Karp samen met Richard Lipton de Karp-Lipton-stelling, die zegt dat als het zo is dat het vervulbaarheidsprobleem kan worden opgelost door booleaanse circuits van polynomiale grootte, dan de polynomiale hiërarchie samenvalt met het tweede niveau.
Voor zijn werk in de complexiteitstheorie kreeg Karp in 1985 een Turing Award en in 1996 een National Medal of Science.
Zie ook
- ↑ Mathematics Genealogy Project.
- ↑ Richard M. Karp. "Reducibility Among Combinatorial Problems". In: Raymond E. Miller, James W. Thatcher (Eds.): Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York. Plenum Press, New York 1972 (blz. 85-103)
· 
· 