Leonid Levin

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa


Leonid Levin
Matemática, ciência da computação
Nacionalidade União das Repúblicas Socialistas Soviéticas Soviético, Estados Unidos estadunidense
Nascimento 2 de novembro de 1948 (66 anos)
Local Dnipropetrovsk
Atividade
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 | editar código-fonte]

Referências

Ligações externas[editar | editar código-fonte]


Ícone de esboço Este artigo sobre um(a) matemático(a) é um esboço. Você pode ajudar a Wikipédia expandindo-o.