Richard Manning Karp matemàtic i informàtic nord-americà

Richard Manning Karp, (nascut el 3 de gener de 1935 a Boston, Mass., EUA), matemàtic i informàtic nord-americà i guanyador del premi Turing AM de 1985, el màxim honor en informàtica, per “les seves continuades contribucions a la teoria de algorismes que inclouen el desenvolupament d'algorismes eficients per al flux de xarxa i altres problemes d'optimització combinacional, la identificació de la computabilitat polinòmica en temps amb la noció intuïtiva d'eficiència algorítmica i, sobretot, contribucions a la teoria de la compleció NP. " Els seus interessos de recerca han inclòs informàtica teòrica, algoritmes combinatorials, probabilitats discretes, biologia computacional i algorismes d'Internet.

Karp va obtenir un títol de batxillerat (1955), un màster (1956) i un doctorat (1959), tots en matemàtiques, per la Universitat de Harvard. Després d’acabar els estudis, treballà com a matemàtic a IBM (1959–68) abans de passar a l’àmbit acadèmic. Karp va ocupar càrrecs a la Universitat de Califòrnia, Berkeley (1968-1994), a la Universitat de Washington (1995–99), i de nou a Berkeley (1999–), on va tornar com a professor universitari.

El paper de Karp, "Reducibilitat entre problemes combinatius", va demostrar que molts problemes combinatoris estudiats habitualment són variants del mateix problema, cosa que implica que probablement són intractables (problemes NP complets, és a dir, problemes per als quals no es coneix cap algorisme de solució eficient). Karp és l’autor de Complexity of Computation (1974) i té una patent per a un tipus de xarxa de commutació multiconnexió.

A més del premi Turing, Karp va rebre el Premi Fulkerson en Matemàtiques Discretes (1979), la Medalla Nacional de la Ciència dels Estats Units (1996), la Medalla centenària de la Universitat de Harvard (1997), el Premi Israel Harvey de l'Institut Israel de Tecnologia (1998), el Premi Dickson de Ciències de la Universitat Carnegie Mellon (2008) i Premi Kyoto del Japó (2008). Va ser elegit a l'Acadèmia de Ciències de Nova York (1980), a l'Acadèmia Nacional de Ciències dels EUA (1980), a l'Acadèmia Americana de les Arts i les Ciències (1985), a l'Institut de Combinatorística i a les seves Aplicacions (1990), a l'Associació Americana per l’Avanç de la Ciència (1991), l’Acadèmia Nacional d’Enginyeria dels Estats Units (1992), la American Philosophical Society (1994), l’Acadèmia Francesa de les Ciències (2002) i l’Acadèmia Europea de les Ciències (2004).