Richard Manning Karp, (geboren op 3 januari 1935, Boston, Massachusetts, VS), Amerikaanse wiskundige en informaticus en winnaar van de 1985 AM Turing Award, de hoogste eer in de informatica, voor 'zijn voortdurende bijdragen aan de theorie van algoritmen, waaronder de ontwikkeling van efficiënte algoritmen voor netwerkflow en andere combinatorische optimalisatieproblemen, de identificatie van polynoom-tijd berekenbaarheid met het intuïtieve begrip van algoritmische efficiëntie, en, met name, bijdragen aan de theorie van NP-volledigheid. " Zijn onderzoeksinteresses omvatten theoretische informatica, combinatorische algoritmen, discrete waarschijnlijkheid, computationele biologie en internetalgoritmen.
Karp behaalde een bachelordiploma (1955), een masterdiploma (1956) en een doctoraat (1959), allemaal in de wiskunde, aan de Harvard University. Nadat hij zijn studie had afgerond, werkte hij als wiskundige bij IBM (1959–68) voordat hij naar de academische wereld verhuisde. Karp bekleedde functies aan de University of California, Berkeley (1968-1994), de University of Washington (1995-1999) en opnieuw aan Berkeley (1999–), waar hij terugkeerde als universiteitsprofessor.
Karp's paper uit 1972 "Reduceerbaarheid tussen combinatorische problemen" bewees dat veel algemeen bestudeerde combinatorische problemen varianten zijn van hetzelfde probleem, wat inhoudt dat ze waarschijnlijk allemaal hardnekkig zijn (NP-volledige problemen - dat wil zeggen problemen waarvoor geen efficiënt oplossingsalgoritme bekend is). Karp is de auteur van Complexity of Computation (1974) en heeft een patent op een type multiconnection-schakelnetwerk.
Naast de Turing Award ontving Karp de Fulkerson Prize in Discrete Mathematics (1979), de US National Medal of Science (1996), de Harvard University Centennial Medal (1997), het Israel Institute of Technology Harvey Prize (1998), de Carnegie Mellon University Dickson Prize in Science (2008) en de Kyoto-prijs van Japan (2008). Hij werd gekozen in de New York Academy of Sciences (1980), de US National Academy of Sciences (1980), de American Academy of Arts and Sciences (1985), het Institute of Combinatorics and Its Applications (1990), de American Association for the Advancement of Science (1991), de US National Academy of Engineering (1992), de American Philosophical Society (1994), de French Academy of Sciences (2002) en de European Academy of Sciences (2004).
