Richard M Karp

Richard Manning Karp (nacido el 3 de enero de 1935) es un científico informático estadounidense y teórico computacional de la Universidad de California, Berkeley. Es más notable por su investigación en la teoría de los 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.

Karp fue elegido miembro de la Academia Nacional de Ingeniería (1992) por sus importantes contribuciones a la teoría y la aplicación de la integridad NP, la construcción de algoritmos combinatorios eficientes y la aplicación de métodos probabilísticos en informática.

Biografía

Nacido de padres Abraham y Rose Karp en Boston, Massachusetts, Karp tiene tres hermanos menores: Robert, David y Carolyn. Su familia era judía, y él creció en un apartamento pequeño, en un barrio 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. los honorarios de la escuela de medicina. Asistió a la Universidad de Harvard, donde recibió su licenciatura en 1955, su maestría en 1956 y su Ph.D. 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. 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 científico investigador en el Instituto Internacional de Ciencias de la Computación en Berkeley, donde actualmente dirige el Grupo de Algoritmos.

Richard Karp recibió la Medalla Nacional de la Ciencia y recibió el Premio Harvey del Technion y la Medalla Benjamin Franklin 2004 en Informática y Ciencias Cognitivas por sus conocimientos sobre la complejidad computacional. En 1994 fue admitido como miembro de la Association for Computing Machinery. Fue elegido miembro de la clase de 2002 de Fellows del Instituto de Investigación de Operaciones y Ciencias de la Administración. Ha recibido varios títulos honoríficos y es miembro de la Academia Nacional de Ciencias de EE. UU., la Academia Estadounidense de Artes y Ciencias y la Sociedad Filosófica Estadounidense.

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.

Trabajo

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, co-desarrolló 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 de Edmonds-Karp para resolver el problema de flujo máximo en redes, y en 1972 publicó un artículo histórico en la teoría de la complejidad, "Reducibilidad entre problemas combinatorios", en el que demostró que 21 problemas eran NP-completos.

En 1973, él y John Hopcroft publicaron el algoritmo Hopcroft-Karp, el método conocido más rápido 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 prueba que si SAT se puede resolver mediante circuitos booleanos con un número polinomial de puertas lógicas, entonces la jerarquía polinomial colapsa a su segundo nivel).

En 1987, co-desarrolló con Michael O. Rabin el algoritmo de búsqueda de cadenas Rabin-Karp.

Premio Turing

Su mención para el (1985) Premio Turing fue la siguiente:

Para sus continuas contribuciones a la teoría de algoritmos incluyendo el desarrollo de algoritmos eficientes para el flujo de red y otros problemas de optimización combinatorial, la identificación de computabilidad polinomio-tiempo con la noción intuitiva de eficiencia algoritmo, y, sobre todo, contribuciones a la teoría de la completeidad NP. Karp introdujo la actual metodología estándar para probar que los problemas son completos por NP, lo que ha llevado a la identificación de muchos problemas teóricos y prácticos como siendo computacionalmente difícil.