Leonid Levin Anatolievich ( / l eɪ . Oʊ n i d l ɛ v ɪ n / lay-OH NECESIDAD LEV -en ; ruso : Леонид Анатольевич Левин ; Ucrania : Леонід Анатолійович Левін ;, 2 noviembre 1948) es un Soviética -American matemático y científico de la computación .
Leonid Anatolievich Levin | |
---|---|
Nació | |
alma mater | Instituto de Tecnología de Massachusetts de la Universidad de Moscú |
Conocido por | Teorema de Cook-Levin Complejidad de casos promedio Investigación en complejidad, aleatoriedad, información |
Premios | Premio Knuth (2012) |
Carrera científica | |
Campos | Matemáticas Informática |
Instituciones | Universidad de Boston |
Asesor de doctorado | Andrey Kolmogorov , Albert R. Meyer |
Es conocido por su trabajo en aleatoriedad en computación , complejidad e intratabilidad algorítmica , complejidad de casos promedio , [1] fundamentos de matemáticas e informática , probabilidad algorítmica , teoría de la computación y teoría de la información . Obtuvo su maestría en la Universidad de Moscú en 1970, donde estudió con Andrey Kolmogorov y completó los requisitos académicos de grado de candidato en 1972. [2]
Stephen Cook y él descubrieron de forma independiente la existencia de problemas NP-completos . Este teorema de NP-completitud, a menudo llamado teorema de Cook-Levin , fue la base para uno de los siete problemas del premio Millennium declarados por el Clay Mathematics Institute con un premio de $ 1,000,000 ofrecido. El teorema de Cook-Levin supuso un gran avance en la informática y un paso importante en el desarrollo de la teoría de la complejidad computacional .
Levin fue galardonado con el Premio Knuth en 2012 [3] por su descubrimiento de la completitud NP y el desarrollo de la complejidad del caso promedio . Su vida se describe en un capítulo del libro Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists . [4]
Biografía
Obtuvo su maestría en la Universidad de Moscú en 1970, donde estudió con Andrey Kolmogorov y completó los requisitos académicos de Candidato en 1972. [2] [5] Después de investigar sobre problemas algorítmicos de la teoría de la información en el Instituto de Transmisión de Información de Moscú del National Academia de Ciencias en 1972-1973, y un puesto como Investigador Científico Senior en el Instituto Nacional de Investigación de Automatización Integrada para la Industria del Petróleo / Gas de Moscú en 1973-1977, emigró a los Estados Unidos en 1978 y también obtuvo un Ph.D. en el Instituto de Tecnología de Massachusetts (MIT) en 1979. [2] Su asesor en el MIT fue Albert R. Meyer .
Es bien conocido por su trabajo en aleatoriedad en computación , complejidad e intratabilidad algorítmica , complejidad de casos promedio , [1] fundamentos de matemáticas e informática , probabilidad algorítmica , teoría de la computación y teoría de la información .
Su vida se describe en un capítulo del libro Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists . [4]
Levin y Stephen Cook descubrieron de forma independiente la existencia de problemas NP-completos . Este teorema de NP-completitud, a menudo llamado teorema de Cook-Levin , fue la base para uno de los siete problemas del premio Millennium declarados por el Clay Mathematics Institute con un premio de $ 1,000,000 ofrecido. El teorema de Cook-Levin supuso un gran avance en la informática y un paso importante en el desarrollo de la teoría de la complejidad computacional . El artículo de revista de Levin sobre este teorema se publicó en 1973; [6] había dado conferencias sobre las ideas en él durante algunos años antes de ese momento (ver la encuesta de Trakhtenbrot ), [7] aunque la redacción formal completa de los resultados tuvo lugar después de la publicación de Cook.
Levin fue galardonado con el Premio Knuth en 2012 [3] por su descubrimiento de la completitud NP y el desarrollo de la complejidad del caso promedio .
Actualmente es profesor de informática en la Universidad de Boston , donde comenzó a enseñar en 1980.
Notas
- ↑ a b Levin, Leonid (1986). "Problemas completos de casos promedio" . SIAM J. Comput . 15 (1): 285–6. doi : 10.1137 / 0215020 .
- ^ a b c Currículum vitae de Levin
- ^ a b Comunicado de prensa de ACM, 22 de agosto de 2012 Archivado el 3 de marzo de 2016 en Wayback Machine.
- ^ a b Shasha, Dennis; Cathy Lazere (septiembre de 1995). Fuera de sus mentes: las vidas y los descubrimientos de 15 grandes científicos informáticos . Springer . ISBN 0-387-97992-1.
- ^ Disertación de 1971 (en ruso); Traducción al inglés en arXiv
- ^ Levin, Leonid (1973). "Problemas de búsqueda universal (ruso: Универсальные задачи перебора, Universal'nye perebornye zadachi)". Problemas de transmisión de información (ruso: Проблемы передачи информации, Problemy Peredachi Informatsii) . 9 (3): 115-116. (pdf)
- ^ Boris A. Trakhtenbrot (1984). "Un estudio de los enfoques rusos de los algoritmos de Perebor (búsquedas de fuerza bruta)" . Anales de la historia de la informática . IEEE . 6 (4): 384–400. doi : 10.1109 / MAHC.1984.10036 . S2CID 950581 .
Referencias
- "Leonid A. Levin" . Proyecto de genealogía matemática .
enlaces externos
- Página de inicio de Levin en la Universidad de Boston.
- Premio Knuth 2012 a Leonid Levin