Leonid Levin

Leonid Anatolievich Levin ( / ˌ l eɪ . oʊ ˈ n iː d ˈ l ɛ v ɪ n / LAY -oh- NECESITA LEV -in ; ruso : Леони́д Анато́льевич Ле́вин [ lʲɪɐˈnʲit ɐnɐˈtolʲjɪvʲɪtɕ ˈlʲevʲɪn ] Ucraniano : Леоні́д Анато́лійович Ле́він [ leoˈn⁽ʲ⁾id ɐnɐˈtɔl⁽ʲ⁾ijowɪtʃ ˈlɛwin ] ; nacido el 2 de noviembre de 1948) es un matemático y científico informático soviético-estadounidense .

Es conocido por su trabajo en aleatoriedad en computación , complejidad e intratabilidad algorítmica, complejidad del caso 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 para el grado de candidato en 1972. ^{[ 2 ]}

Él 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 de uno de los siete Problemas del Premio del Milenio declarados por el Instituto Clay de Matemáticas, con un premio de 1.000.000 de dólares. El teorema de Cook-Levin representó un gran avance en la informática y un paso importante en el desarrollo de la teoría de la complejidad computacional .

Levin recibió el Premio Knuth en 2012 ^{[ 3 ]} por su descubrimiento de la NP-completitud y el desarrollo de la complejidad del caso promedio . Es miembro de la Academia Nacional de Ciencias de los Estados Unidos y miembro de la Academia Estadounidense de Artes y Ciencias .

Biografía

Obtuvo su maestría en la Universidad de Moscú en 1970, donde estudió con Andrey Kolmogorov y completó los requisitos académicos del grado de candidato en 1972. ^{[ 2 ]}^{[ 4 ]} Después de investigar problemas algorítmicos de la teoría de la información en el Instituto de Transmisión de Información de la Academia Nacional de Ciencias de Moscú en 1972-1973, y un puesto como científico investigador sénior en el Instituto Nacional de Investigación de Automatización Integrada para la Industria del Petróleo y el Gas de Moscú en 1973-1977, emigró a los EE. UU. en 1978 y también obtuvo un doctorado en el Instituto Tecnológico 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 algorítmica e intratabilidad, complejidad del caso promedio , ^{[ 1 ]} fundamentos de matemáticas y ciencias de la computación , 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 . ^{[ 5 ]}

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 de uno de los siete Problemas del Premio del Milenio declarados por el Instituto Clay de Matemáticas, con un premio de 1.000.000 de dólares. El teorema de Cook-Levin fue un avance en la informática y un paso importante en el desarrollo de la teoría de la complejidad computacional . El artículo de Levin sobre este teorema se publicó en 1973; ^{[ 6 ]} había impartido conferencias sobre las ideas que contiene durante algunos años antes de esa fecha (véase el estudio 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 NP-completitud y el desarrollo de la complejidad del caso promedio .

Actualmente es profesor de informática en la Universidad de Boston , donde comenzó a impartir clases en 1980.

Notas

1 2 Levin, Leonid (1986). "Problemas completos en el caso promedio" . SIAM J. Comput . 15 (1): 285– 6. doi : 10.1137/0215020 .
1 2 3 Currículum vitae de Levin
1 2 Comunicado de prensa de ACM, 22 de agosto de 2012. Archivado el 3 de marzo de 2016 en Wayback Machine .
↑ Tesis doctoral de 1971 (en ruso); traducción al inglés en arXiv
↑ Shasha, Dennis; Cathy Lazere (septiembre de 1995). Fuera de sí: Las vidas y los descubrimientos de 15 grandes científicos informáticos . Springer . ISBN 0-387-97992-1.
^ 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 Perebor (búsquedas por fuerza bruta)" . Anales de la historia de la computación . 6 (4). IEEE : 384–400 . doi : 10.1109/MAHC.1984.10036 . S2CID 950581 .

Referencias

"Leonid A. Levin" . Proyecto de genealogía matemática .

Enlaces externos

Página principal de Levin en la Universidad de Boston.
Premio Knuth 2012 a Leonid Levin

[SIAM86-1] 1 2 Levin, Leonid (1986). "Problemas completos en el caso promedio" . SIAM J. Comput . 15 (1): 285– 6. doi : 10.1137/0215020 .

[CV-2] 1 2 3 Currículum vitae de Levin

[ACM2012-3] 1 2 Comunicado de prensa de ACM, 22 de agosto de 2012. Archivado el 3 de marzo de 2016 en Wayback Machine .

[4] Tesis doctoral de 1971 (en ruso); traducción al inglés en arXiv

[LevinOoTM-5] Shasha, Dennis; Cathy Lazere (septiembre de 1995). Fuera de sí: Las vidas y los descubrimientos de 15 grandes científicos informáticos . Springer . ISBN 0-387-97992-1.

[6] 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)

[LevinTrakhtSurvey-7] Boris A. Trakhtenbrot (1984). "Un estudio de los enfoques rusos de los algoritmos Perebor (búsquedas por fuerza bruta)" . Anales de la historia de la computación . 6 (4). IEEE : 384–400 . doi : 10.1109/MAHC.1984.10036 . S2CID 950581 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]