Leonid Levin
Leonid Levin | |
---|---|
Nascimento | 2 de novembro de 1948 (76 anos) Dnipropetrovsk |
Nacionalidade | Soviético, estadunidense |
Alma mater | Universidade Estatal de Moscou, Instituto de Tecnologia de Massachusetts |
Prêmios | Prêmio Knuth (2012) |
Orientador(es)(as) | Andrei Kolmogorov e Albert Ronald Meyer[1] |
Instituições | Universidade de Boston |
Campo(s) | Matemática, ciência da computação |
Leonid Anatolievich Levin, em russo: Леонид Анатольевич Левин; (Dnipropetrovsk, 2 de novembro de 1948) é um informático soviético-estadunidense.
Obteve o mestrado em 1970 e um Ph.D. em 1972 na Universidade de Moscou, onde foi aluno de Andrey Kolmogorov. Em 1978 emigrou para os Estados Unidos, obtendo um Ph.D. no Instituto de Tecnologia de Massachusetts (MIT) em 1979. Seu orientador no MIT foi Albert Ronald 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 Universidade de Boston, onde começou a lecionar em 1980.
Ver também
[editar | editar código-fonte]Referências
- ↑ Leonid Levin (em inglês) no Mathematics Genealogy Project
Ligações externas
[editar | editar código-fonte]- 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
- Alunos do Instituto de Tecnologia de Massachusetts
- Alunos da Universidade Estatal de Moscou
- Judeus da Ucrânia
- Naturais de Dnipro