Richard Karp

Amerikaans wiskundige

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.

Richard M. Karp
Richard Karp in 2009
Persoonlijke gegevens
Volledige naam Richard Manning Karp
Geboortedatum 3 januari 1935
Geboorteplaats Boston (Verenigde Staten)
Wetenschappelijk werk
Vakgebied Informatica
Bekend van A simple algorithm for finding frequent elements in streams and bagsBewerken op Wikidata
Promotor Anthony Oettinger[1]
Alma mater Harvard-universiteit
Universiteit van Californië - BerkeleyBewerken op Wikidata
officiële website

Biografie bewerken

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 bewerken

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 bewerken