Richard Karp

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Richard M. Karp
Richard Karp in 2009
Richard Karp in 2009
Persoonlijke gegevens
Volledige naam Richard Manning Karp
Geboortedatum 3 januari 1935
Geboorteplaats Boston (Verenigde Staten)
Wetenschappelijk werk
Vakgebied Informatica
Officiële 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[bewerken]

Karp werd op 3 januari 1935 geboren in Boston en ging naar de Boston Latin School. Hij studeerde aan de Universiteit van Harvard 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,[1] 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]

Bronnen, noten en/of referenties
  1. 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)