Richard Karp

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.^[2]

Richard Karp
Richard Karp
Algoritmo de Edmonds-Karp
Nascimento	3 de janeiro de 1935 (90 anos) Boston
Nacionalidade	estadunidense
Cidadania	Estados Unidos
Alma mater	Universidade Harvard
Ocupação	matemático, cientista de computação, professor universitário
Distinções	Prêmio Fulkerson (1979), Prêmio Turing (1985), John von Neumann Lecture (1987), Medalha Nacional de Ciências (1996), Prêmio Harvey (1998), Prêmio EATCS (2000), Medalha Benjamin Franklin (2004), Prêmio Kyoto (2008), Prêmio Dickson de Ciências (2008)
Empregador(a)	Universidade da Califórnia em Berkeley, Universidade de Washington
Orientador(a)(es/s)	Anthony Oettinger[1]
Orientado(a)(s)	Narendra Karmarkar, Michael Luby, Rajeev Motwani, Noam Nisan, Barbara Simons
Instituições	Universidade da Califórnia em Berkeley, IBM
Campo(s)	ciência da computação
Obras destacadas	A simple algorithm for finding frequent elements in streams and bags
Página oficial
http://www.eecs.berkeley.edu/Faculty/Homepages/karp.html
[edite no Wikidata]

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.^[3]

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^[4] 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.

Referências

1. Richard Karp (em inglês) no Mathematics Genealogy Project.
2. «Cópia arquivada». Consultado em 20 de abril de 2013. Arquivado do original em 14 de março de 2010
3. Richard M. Karp (1972). «Reducibility Among Combinatorial Problems» (PDF). In: R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. [S.l.]: New York: Plenum. pp. 85–103
4. Association for Computing Machinery. «ACM Award Citation/Richard M. Karp». Consultado em 17 de janeiro de 2010. Arquivado do original em 3 de julho de 2012