La publicación del artículo de 1972 "Reducibility Among Combinatorial Problems" estableció a Richard M. Karp como una figura fundamental en la teoría de la complejidad computacional. Al demostrar que 21 problemas distintos son NP-completos, proporcionó la metodología necesaria para que los investigadores identificaran qué desafíos teóricos y prácticos en la informática son fundamentalmente difíciles de resolver utilizando algoritmos eficientes de tiempo polinómico.
Fundamentos académicos y carrera temprana
Nacido en Boston en 1935, Richard Manning Karp cursó toda su educación formal en la Universidad de Harvard. Obtuvo una licenciatura en 1955, una maestría en 1956 y completó su doctorado en matemáticas aplicadas en 1959 en la Escuela de Ingeniería y Ciencias Aplicadas de Harvard. Tras sus estudios, comenzó su carrera profesional en el Centro de Investigación Thomas J. Watson de IBM.
Desarrollo de algoritmos combinatorios
El trabajo de Karp abarca varias décadas de desarrollo algorítmico. En 1962, colaboró con Michael Held para crear el algoritmo de Held-Karp para el problema del viajante. A esto le siguió el algoritmo de Edmonds-Karp de 1971, desarrollado con Jack Edmonds para resolver problemas de flujo máximo en redes. En 1973, se asoció con John Hopcroft para producir el algoritmo de Hopcroft-Karp, que sigue siendo el método más rápido para identificar emparejamientos de cardinalidad máxima en grafos bipartitos. Además, trabajó con Michael O. Rabin en 1987 para desarrollar conjuntamente el algoritmo de búsqueda de cadenas de Rabin-Karp.
Roles institucionales y reconocimiento
En 1968, Karp se unió al cuerpo docente de la Universidad de California, Berkeley, donde se desempeñó como el primer presidente asociado de la División de Ciencias de la Computación. Aparte de un mandato de cuatro años como profesor en la Universidad de Washington, ha mantenido su afiliación con Berkeley. En 2012, se convirtió en el director fundador del Instituto Simons para la Teoría de la Computación. Sus contribuciones a la ciencia han sido reconocidas con numerosos honores, incluidos el Premio Turing de 1985, el Premio Harvey de 1998, la Medalla Benjamin Franklin de 2004, el Premio Kioto de 2008 y el Premio Dickson de 2009.
Veinte preguntas, ocho minutos de reloj y un percentil medido frente a todos los que la han hecho. Sin registro.
Hacer la prueba de CI →Datos rápidos
- Nacimiento: 1935, Boston, Massachusetts - Educación: Universidad de Harvard (B.S., M.S., Ph.D.) - Afiliación principal: Universidad de California, Berkeley - Premio Turing: 1985 - Premio Kioto en Tecnología Avanzada: 2008 - Áreas de investigación clave: Bioinformática y teoría de la computación - Publicación principal de 1972: Reducibility Among Combinatorial Problems - Director fundador: Instituto Simons para la Teoría de la Computación
Preguntas frecuentes
### ¿Cuál es la importancia del artículo de 1972 de Richard Karp?
Demostró que 21 problemas diferentes eran NP-completos, proporcionando una metodología estándar para clasificar la dificultad computacional de los problemas.
### ¿Qué premios importantes ha recibido Richard Karp?
Ha recibido el Premio Turing, el Premio Kioto, el Premio Harvey, la Medalla Benjamin Franklin y el Premio de Teoría John von Neumann, entre otros.
.jpg)
