title: Richard Karp
text: 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, 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
  Karps 21 NP-volledige problemen
  
  Winnaar van de A.M. Turing Award
  Amerikaans informaticus
  Lid van de Académie des sciences