Richard Manning Karp, (né le 3 janvier 1935, Boston, Massachusetts, États-Unis), mathématicien et informaticien américain et lauréat du prix AM Turing de 1985, la plus haute distinction en informatique, pour «ses contributions continues à la théorie de algorithmes, y compris le développement d'algorithmes efficaces pour l'écoulement du réseau et d'autres problèmes d'optimisation combinatoire, l'identification de la calculabilité polynomiale en temps avec la notion intuitive d'efficacité algorithmique, et, plus particulièrement, les contributions à la théorie de la complétude NP. " Ses intérêts de recherche ont inclus l'informatique théorique, les algorithmes combinatoires, la probabilité discrète, la biologie computationnelle et les algorithmes Internet.
Karp a obtenu un baccalauréat (1955), une maîtrise (1956) et un doctorat (1959), tous en mathématiques, de l'Université Harvard. Après avoir terminé ses études, il a travaillé comme mathématicien chez IBM (1959-1968) avant de passer au monde universitaire. Karp a occupé des postes à l'Université de Californie, Berkeley (1968-1994), à l'Université de Washington (1995-1999), et de nouveau à Berkeley (1999-1999), où il est revenu en tant que professeur d'université.
L'article de Karp de 1972 «Réductibilité parmi les problèmes combinatoires» a prouvé que de nombreux problèmes combinatoires couramment étudiés sont des variantes du même problème, ce qui implique qu'ils sont probablement tous insolubles (problèmes NP-complets, c'est-à-dire des problèmes pour lesquels aucun algorithme de solution efficace n'est connu). Karp est l'auteur de Complexity of Computation (1974) et détient un brevet pour un type de réseau de commutation à connexions multiples.
En plus du prix Turing, Karp a reçu le prix Fulkerson en mathématiques discrètes (1979), la médaille nationale des sciences des États-Unis (1996), la médaille du centenaire de l'Université Harvard (1997), le prix Harvey Harvey de l'Institut israélien de technologie (1998), le Prix Dickson en science de l'Université Carnegie Mellon (2008) et Prix Kyoto du Japon (2008). Il a été élu à la New York Academy of Sciences (1980), à la US National Academy of Sciences (1980), à l'American Academy of Arts and Sciences (1985), à l'Institute of Combinatorics and Its Applications (1990), à l'American Association for l'Avancement des sciences (1991), l'Académie nationale des États-Unis d'ingénierie (1992), l'American Philosophical Society (1994), l'Académie française des sciences (2002) et l'Académie européenne des sciences (2004).
