Richard Manning Karp (nacido el 3 de enero de 1935) es un científico informático y teórico computacional estadounidense de la Universidad de California, Berkeley . Es más notable por su investigación en la teoría de algoritmos , por la que recibió un Premio Turing en 1985, la Medalla Benjamin Franklin en Informática y Ciencias Cognitivas en 2004 , y el Premio Kyoto en 2008. [2]
Karp fue elegido miembro de la Academia Nacional de Ingeniería (1992) por sus importantes contribuciones a la teoría y aplicación de la completitud NP, la construcción de algoritmos combinatorios eficientes y la aplicación de métodos probabilísticos en informática.
Nacido de padres Abraham y Rose Karp en Boston, Massachusetts , Karp tiene tres hermanos menores: Robert, David y Carolyn. Su familia era judía , [3] y creció en un pequeño apartamento, en un barrio entonces mayoritariamente judío de Dorchester en Boston.
Sus padres eran graduados de Harvard (su madre finalmente obtuvo su título de Harvard a los 57 años después de tomar cursos nocturnos), mientras que su padre tenía la ambición de ir a la escuela de medicina después de Harvard, pero se convirtió en profesor de matemáticas porque no podía pagar la escuela de medicina. honorarios. [3] Asistió a la Universidad de Harvard , donde recibió su licenciatura en 1955, su maestría en 1956 y su doctorado. en matemáticas aplicadas en 1959. Comenzó a trabajar en el Centro de Investigación Thomas J. Watson de IBM .
En 1968, se convirtió en profesor de informática, matemáticas e investigación de operaciones en la Universidad de California, Berkeley . Karp fue el primer presidente asociado de la División de Ciencias de la Computación dentro del Departamento de Ingeniería Eléctrica e Informática. [4] Aparte de un período de 4 años como profesor en la Universidad de Washington , ha permanecido en Berkeley. De 1988 a 1995 y de 1999 a la actualidad también ha sido investigador científico en el Instituto Internacional de Ciencias de la Computación de Berkeley, donde actualmente dirige el Grupo de Algoritmos.
Richard Karp recibió la Medalla Nacional de Ciencias y recibió el Premio Harvey del Technion y la Medalla Benjamin Franklin en Informática y Ciencias Cognitivas de 2004 por sus conocimientos sobre la complejidad computacional . En 1994 fue admitido como miembro de la Association for Computing Machinery . Fue elegido miembro de la promoción de 2002 de becarios del Instituto de Investigación de Operaciones y Ciencias de la Gestión . [5] Ha recibido varios títulos honoríficos y es miembro de la Academia Nacional de Ciencias de EE. UU. , [6] de la Academia Estadounidense de Artes y Ciencias , [7] y de la Sociedad Filosófica Estadounidense . [8]
En 2012, Karp se convirtió en director fundador del Instituto Simons de Teoría de la Computación de la Universidad de California, Berkeley . [9]
Karp ha realizado muchos descubrimientos importantes en informática, algoritmos combinatorios e investigación de operaciones . Sus principales intereses de investigación actuales incluyen la bioinformática .
En 1962 desarrolló conjuntamente con Michael Held el algoritmo Held-Karp , un algoritmo de tiempo exponencial exacto para el problema del viajante .
En 1971 desarrolló conjuntamente con Jack Edmonds el algoritmo Edmonds-Karp para resolver el problema de flujo máximo en redes, y en 1972 publicó un artículo histórico en teoría de la complejidad, "Reducibilidad entre problemas combinatorios", en el que demostró que 21 problemas eran NP-completo . [10]
En 1973, él y John Hopcroft publicaron el algoritmo Hopcroft-Karp , el método más rápido conocido para encontrar coincidencias de cardinalidad máxima en gráficos bipartitos .
En 1980, junto con Richard J. Lipton , Karp demostró el teorema de Karp-Lipton (que demuestra que si SAT puede resolverse mediante circuitos booleanos con un número polinomial de puertas lógicas , entonces la jerarquía polinómica colapsa a su segundo nivel).
En 1987 desarrolló conjuntamente con Michael O. Rabin el algoritmo de búsqueda de cadenas Rabin-Karp .
Su cita [11] para el Premio Turing (1985) fue la siguiente:
Por sus continuas contribuciones a la teoría de algoritmos, incluido el desarrollo de algoritmos eficientes para el flujo de redes y otros problemas de optimización combinatoria, la identificación de la computabilidad en tiempo polinomial con la noción intuitiva de eficiencia algorítmica y, más notablemente, sus contribuciones a la teoría de NP. -integridad . Karp introdujo la metodología ahora estándar para demostrar que los problemas son NP-completos, lo que ha llevado a la identificación de muchos problemas teóricos y prácticos como computacionalmente difíciles.
