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 conocido 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 NP-completitud, la construcción de algoritmos combinatorios eficientes y la aplicación de métodos probabilísticos en la informática.
Nacido de 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 de Dorchester en Boston que entonces era mayoritariamente judío.
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 había tenido ambiciones de ir a la escuela de medicina después de Harvard, pero se convirtió en profesor de matemáticas porque no podía pagar las tasas de la escuela de medicina. [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 y Ciencias de la Computación. [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 hasta la actualidad también ha sido científico investigador en el Instituto Internacional de Ciencias de la Computación en Berkeley, donde actualmente dirige el Grupo de Algoritmos.
Richard Karp fue galardonado con la Medalla Nacional de Ciencias , y recibió el Premio Harvey del Technion y la Medalla Benjamin Franklin 2004 en Ciencias Informáticas y Cognitivas por sus ideas sobre la complejidad computacional . En 1994 fue incluido como miembro de la Association for Computing Machinery . Fue elegido miembro de la clase de 2002 de miembros del Institute for Operations Research and the Management Sciences . [5] Ha recibido varios títulos honorarios y es miembro de la Academia Nacional de Ciencias de los Estados Unidos , [6] la Academia Estadounidense de las Artes y las Ciencias , [7] y la Sociedad Filosófica Estadounidense . [8]
En 2012, Karp se convirtió en el director fundador del Instituto Simons para la Teoría de la Computación en 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ó junto con Michael Held el algoritmo Held-Karp , un algoritmo de tiempo exponencial exacto para el problema del viajante de comercio .
En 1971 co-desarrolló 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-completos . [10]
En 1973, él y John Hopcroft publicaron el algoritmo Hopcroft-Karp , el método más rápido conocido para encontrar correspondencias 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 polinomial colapsa a su segundo nivel).
En 1987 desarrolló junto 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, las contribuciones a la teoría de la NP-completitud . 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.
