Richard Manning Karp (* 3. Januar 1935 in Boston, Massachusetts, USA), US-amerikanischer Mathematiker und Informatiker und Gewinner des AM Turing Award 1985, der höchsten Auszeichnung in der Informatik, für „seine fortwährenden Beiträge zur Theorie von Algorithmen, einschließlich der Entwicklung effizienter Algorithmen für den Netzwerkfluss und anderer kombinatorischer Optimierungsprobleme, der Identifizierung der Berechenbarkeit der Polynomzeit mit dem intuitiven Begriff der algorithmischen Effizienz und insbesondere Beiträgen zur Theorie der NP-Vollständigkeit. “ Seine Forschungsinteressen umfassten theoretische Informatik, kombinatorische Algorithmen, diskrete Wahrscheinlichkeit, Computerbiologie und Internetalgorithmen.
Karp erwarb einen Bachelor-Abschluss (1955), einen Master-Abschluss (1956) und einen Doktortitel (1959) in Mathematik an der Harvard University. Nach Abschluss seines Studiums arbeitete er als Mathematiker bei IBM (1959–68), bevor er an die Akademie wechselte. Karp hatte Positionen an der University of California in Berkeley (1968–94), der University of Washington (1995–99) und erneut in Berkeley (1999–99) inne, wo er als Universitätsprofessor zurückkehrte.
Karps 1972 erschienene Arbeit „Reduzierbarkeit unter kombinatorischen Problemen“ bewies, dass viele häufig untersuchte kombinatorische Probleme Varianten desselben Problems sind, was impliziert, dass sie alle wahrscheinlich unlösbar sind (NP-vollständige Probleme - dh Probleme, für die kein effizienter Lösungsalgorithmus bekannt ist). Karp ist Autor von Complexity of Computation (1974) und besitzt ein Patent für eine Art Multiconnection-Switching-Netzwerk.
Neben dem Turing-Preis erhielt Karp den Fulkerson-Preis für diskrete Mathematik (1979), die US-amerikanische National Medal of Science (1996), die Centennial-Medaille der Harvard University (1997) und den Harvey-Preis des Israel Institute of Technology (1998) Dickson-Preis der Carnegie Mellon University für Wissenschaft (2008) und Japans Kyoto-Preis (2008). Er wurde in die New Yorker Akademie der Wissenschaften (1980), die Nationale Akademie der Wissenschaften der USA (1980), die Amerikanische Akademie der Künste und Wissenschaften (1985), das Institut für Kombinatorik und ihre Anwendungen (1990) und die American Association for gewählt der Fortschritt der Wissenschaft (1991), die US National Academy of Engineering (1992), die American Philosophical Society (1994), die French Academy of Sciences (2002) und die European Academy of Sciences (2004).
