Richard Karp

Richard Karp
Ciência da computação
Nacionalidade	Estadunidense
Nascimento	3 de janeiro de 1935 (78 anos)
Local	Boston
Actividade
Campo(s)	Ciência da computação
Prêmio(s)	Prêmio Fulkerson (1979), Prêmio Turing (1985), John von Neumann Lecture (1987), Medalha Nacional de Ciências (1996), Medalha Benjamin Franklin (2004), Prêmio Kyoto (2008)

Richard Manning Karp (Boston, 3 de janeiro de 1935) é um cientista da computação e teórico computacional da Universidade da California, Berkeley, reconhecido pela sua pesquisa sobre teoria dos algoritmos, pelo qual recebeu um Prêmio Turing em 1985, Medalha Benjamin Franklin em Computação e Ciência Cognitiva em 2004, e o Prêmio Kyoto em 2008.

Biografia

Filho de Abraham e Rose Karp, nasceu em Boston, Massachusetts, Richard tem três irmãos mais novos: Robert, David, e Carolyn. Ele estudou na Universidade de Harvard, onde recebeu o seu diploma de Bacharel em 1955, o seu diploma de Mestre em 1956, e o seu Ph.D. em matemática aplicada em 1959.

Ele começou a trabalhar no Thomas J. Watson Research Center da IBM. Em 1968, se tornou Professor de Ciência da Computação, Matemática, e Pesquisa de Operações na Universidade da California, Berkeley. Além dos 4 anos como professor na Universidade de Washington, ele permaneceu em Berkeley. De 1988 a 1995 e de 1999 até os dias de hoje ele também tem sido Pesquisador no International Computer Science Institute em Berkeley, onde ele atualmente lidera o Algorithms Group.

Richard Karp foi premiado com a Medalha Nacional de Ciências, e foi o beneficiário do Prêmio Harvey da Technion e da Medalha Benjamin Franklin em Computação e Ciência Cognitiva em 2004 por suas percepções na complexidade computacional. Em 1994, ele foi introduzido como um fellow da Association for Computing Machinery. Ele é o beneficiário de vários títulos honoríficos.

Trabalho

Ele fez várias outras descobertas importantes em ciências da computação e em pesquisa operacional na área de otimização combinatória. Seu maior interesse atual de pesquisa envolve bioinformática.

Em 1971, ele desenvolveu com Jack Edmonds o Edmonds–Karp algorithm para resolver problemas de máximo-fluxo nas redes, e em 1972, ele publicou um artigo que envolvia a teoria da complexidade, "Reducibility Among Combinatorial Problems", no qual ele provou 21 Problems to be NP-complete.

Em 1973, ele e John Hopcroft publicaram o Hopcroft–Karp algorithm, que ainda é o método mais rápido para encontrar as correspondências de cardinalidade máxima em grafos bipartidos.

Em 1980, junto com Richard Lipton, Karp provou o teorema de Karp-Lipton (o qual prova que, se o SAT pode ser resolvido por circuitos booleanos com um número polinomial de portas lógicas, então a hierarquia polinomial desmorona ao seu segundo nível).

Em 1987, ele desenvolveu com Michael Rabin o Rabin-Karp string search algorithm.

Prêmio Turing

A citação dele para o Turing Award foi como se segue:

Por suas contribuições contínuas para a teoria dos algoritmos incluindo o desenvolvimento de algoritmos eficientes para problemas de fluxo de rede e outros problemas de otimização combinatória, a identificação da computabilidade em tempo-polinomial com a noção intuitiva da eficiência do algoritmo, e, mais notável, contribuições para a teoria da NP-completude. Karp introduziu a metodologia padrão atual para provar que problemas são NP-completos o que levou à identificação de muitos outros problemas práticos e teóricos como sendo de dificuldade computacional.

Ligações externas

• ACM Crossroads magazine interview/bio of Richard Karp
• Karp's Home Page at Berkeley