Stephen Cook
Stephen Arthur Cook, (Buffalo, 14 de dezembro de 1939) é um cientista da computação e matemático estadunidense-canadense, que teve maior contribuição no campo da teoria da complexidade e complexidade de prova.
| Stephen Cook | |
|---|---|
 | |
| Conhecido(a) por | NP-completude Complexidade da prova Teorema de Cook-Levin |
| Nascimento | 14 de dezembro de 1939 (84 anos) Buffalo, Nova Iorque |
| Nacionalidade | Estadunidense |
| Alma mater | Universidade Harvard, Universidade de Michigan |
| Prêmios | Prêmio Turing (1982), Prêmio Izaak-Walton-Killam (1997), Prêmio CRM-Fields-PIMS (1999), Prêmio John L. Synge (2006), Medalha Bernard Bolzano, Medalha de Ouro Gerhard Herzberg (2012), Prêmios Fronteiras do Conhecimento (2015) |
| Orientador(es)(as) | Hao Wang |
| Orientado(a)(s) | Paul Beame Mark Braverman Valentine Kabanets Toniann Pitassi Robert A. Reckhow Walter Savitch |
| Instituições | Universidade da Califórmia Universidade de Toronto |
| Campo(s) | Ciência da computação |
É professor de informática da Universidade de Toronto, Departamento de Ciência da Computação e Departamento de Matemática. Seu campo de interesse principal é a complexidade computacional, interessando-se também por lógica e computabilidade.
Cook tornou-se famoso na teoria da computação pelo Teorema de Cook: O problema da satisfabilidade booleana é NP-completo. Por esta descoberta recebeu o Prêmio Turing de 1982.
Biografia editar
Cook recebeu seu bacharelato in 1961 pela Universidade de Michigan, e seu mestrado e Ph.D. da Universidade de Harvard, respectivamente em 1962 e 1966. Ele entrou na Universidade da Califórmia no departamento de matemática em 1966 como professor assistente e esteve lá até 1970 quando ele teve sua recondução negada. Em um discurso de celebração do 30º aniversário do departamento Berkeley EECS, seu companheiro vencedor do Prêmio Turing e professor de Berkeley Richard Karp disse que, "É nossa eterna vergonha não termos sido capazes de convencer o departamento de matemática para dar-lhe posse."[1] Cook entrou na Universidade de Toronto, Departamento de Ciência da Computação e Matemática em 1970 como professor associado, onde ele foi promovido a professor em 1975 e a posição honorária de professor com distinção em 1985.
Pesquisa editar
Stephen Cook é considerado um dos precursores da teoria da complexidade computacional.
Durante seu PhD, Cook trabalhou na complexidade de funções, principalmente na multiplicação. Em seu artigo seminal de 1971 "The Complexity of Theorem Proving Procedures",[2][3] Cook formalizou as noções de redução em tempo polinomial (também conhecido como redução de Cook) e NP-completude e provou a existência de um problema NP-completo mostrando que o problema da satisfatibilidade booleana (usualmente conhecido como SAT) é NP-completo. Esse teorema foi provado independentemente por Leonid Levin na União Soviética, e assim acabou recebendo o nome de teorema de Cook-Levin. O artigo também formulou o mais famoso problema da ciência da computação, o problema P vs. NP. Informalmente, a questão "P vs. NP" indaga se cada problema de otimização em que a resposta pode ser verificada por corretude/otimização também pode ser resolvido otimamente por um algoritmo eficiente. Dada a abundância de problemas de otimização no dia dia a dia, uma resposta positiva para a questão "P vs. NP" seria provável de ter profundas consequências práticas e filosóficas.
Referências
- ↑ A Personal View of Computer Science at Berkeley - Richard Karp
- ↑ "The Complexity of Theorem Proving Procedures", PDF file of a scanned version
- ↑ "The Complexity of Theorem Proving Procedures", PDF file of a retyped version
Ligações externas editar
- «Página pessoal na Universidade de Toronto» (em inglês)
| Precedido por Edgar Frank Codd |
Prêmio Turing 1982 |
Sucedido por Ken Thompson e Dennis Ritchie |