Leonid Levin
- Este artigo foi inicialmente traduzido do artigo da Wikipédia em inglês, cujo título é «Leonid Levin», especificamente desta versão.
| Leonid Levin | |
|---|---|
| Matemática, ciência da computação | |
 |
|
| Nacionalidade |  Soviético,  estadunidense |
| Nascimento | 2 de novembro de 1948 (64 anos) |
| Local | Dnipropetrovsk |
| Actividade | |
| Campo(s) | Matemática, ciência da computação |
| Instituições | Universidade de Boston |
| Alma mater | Universidade Estatal de Moscou, Instituto de Tecnologia de Massachusetts |
| Orientador(es) | Andrei Kolmogorov e Albert R. Meyer |
| Prêmio(s) | Prêmio Knuth (2012) |
Leonid Anatolievich Levin, em russo: Леонид Анатольевич Левин; (Dnipropetrovsk, 2 de novembro de 1948) é um informático soviético-estadunidense.
Ele obteve seu mestrado em 1970 e um Ph.D. em 1972 na Universidade de Moscou onde estudou com Andrey Kolmogorov. Mais tarde, ele emigrou para os EUA em 1978 e também ganhou um Ph.D. no Massachusetts Institute of Technology (MIT) em 1979. Seu orientador no MIT foi Albert R. Meyer.
Levin e Stephen Cook, descobriram a existência de problemas NP-completos. Este teorema da NP-completude, muitas vezes chamado de Teorema de Cook-Levin, foi a base para um dos sete Problemas do Milênio. O teorema de Cook-Levin foi um avanço na ciência da computação e é o fundamento da complexidade computacional.
Atualmente é professor de ciência da computação na Boston University, onde começou a lecionar em 1980.
Ver também [editar]
Referências
Ligações externas [editar]
- Leonid Levin em Mathematics Genealogy Project
- Levin's home page at Boston University.
- Nascidos em 1948
- Professores da Universidade de Boston
- Matemáticos da Rússia
- Matemáticos dos Estados Unidos
- Cientistas da computação da Rússia
- Cientistas da computação dos Estados Unidos
- Ex-alunos do Instituto de Tecnologia de Massachusetts
- Ex-alunos da Universidade Estatal de Moscou
- Judeus da Ucrânia
- Naturais de Dnipropetrovsk
