Richard M. Karp

A publicação do artigo de 1972 "Reducibility Among Combinatorial Problems" estabeleceu Richard M. Karp como uma figura fundamental na teoria da complexidade computacional. Ao provar que 21 problemas distintos são NP-completos, forneceu a metodologia necessária para que os investigadores identificassem quais os desafios teóricos e práticos na informática que são fundamentalmente difíceis de resolver utilizando algoritmos eficientes de tempo polinomial.

Fundamentos académicos e início de carreira

Nascido em Boston em 1935, Richard Manning Karp realizou toda a sua educação formal na Universidade de Harvard. Obteve uma licenciatura em 1955, um mestrado em 1956 e completou o seu doutoramento em matemática aplicada em 1959 na Harvard School of Engineering and Applied Sciences. Após os seus estudos, iniciou a sua carreira profissional no Centro de Investigação Thomas J. Watson da IBM.

Desenvolvimento de algoritmos combinatórios

O trabalho de Karp abrange várias décadas de desenvolvimento algorítmico. Em 1962, colaborou com Michael Held para criar o algoritmo de Held-Karp para o problema do caixeiro-viajante. Seguiu-se o algoritmo de Edmonds-Karp de 1971, desenvolvido com Jack Edmonds para resolver problemas de fluxo máximo em redes. Em 1973, associou-se a John Hopcroft para produzir o algoritmo de Hopcroft-Karp, que continua a ser o método mais rápido para identificar emparelhamentos de cardinalidade máxima em grafos bipartidos. Além disso, trabalhou com Michael O. Rabin em 1987 para co-desenvolver o algoritmo de pesquisa de cadeias de Rabin-Karp.

Funções institucionais e reconhecimento

Em 1968, Karp juntou-se ao corpo docente da Universidade da Califórnia, Berkeley, onde serviu como o primeiro presidente associado da Divisão de Ciências da Computação. Para além de um mandato de quatro anos como professor na Universidade de Washington, manteve a sua afiliação com Berkeley. Em 2012, tornou-se o diretor fundador do Instituto Simons para a Teoria da Computação. As suas contribuições para a ciência foram reconhecidas com inúmeras distinções, incluindo o Prémio Turing de 1985, o Prémio Harvey de 1998, a Medalha Benjamin Franklin de 2004, o Prémio Kyoto de 2008 e o Prémio Dickson de 2009.

Factos rápidos

- Nascimento: 1935, Boston, Massachusetts - Educação: Universidade de Harvard (B.S., M.S., Ph.D.) - Afiliação principal: Universidade da Califórnia, Berkeley - Prémio Turing: 1985 - Prémio Kyoto em Tecnologia Avançada: 2008 - Áreas de investigação chave: Bioinformática e teoria da computação - Publicação principal de 1972: Reducibility Among Combinatorial Problems - Diretor fundador: Instituto Simons para a Teoria da Computação

Perguntas dos leitores

### Qual é a importância do artigo de 1972 de Richard Karp?

Provou que 21 problemas diferentes eram NP-completos, fornecendo uma metodologia padrão para classificar a dificuldade computacional dos problemas.

### Que prémios importantes recebeu Richard Karp?

Recebeu o Prémio Turing, o Prémio Kyoto, o Prémio Harvey, a Medalha Benjamin Franklin e o Prémio de Teoria John von Neumann, entre outros.