Leonid Levin

Leonid Anatolievich Levin (lay-oh-NEED LEV-in; ruso: Леони́д Анато́льевич Ле́вин; ucraniano: Леоні́д Анато́лійович Ле́він; nacido el 2 de noviembre de 1948) es un matemático e informático soviético-estadounidense.

Es conocido por su trabajo sobre aleatoriedad en informática, complejidad e intratabilidad algorítmica, complejidad de casos promedio, fundamentos de las matemáticas y la 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 del título de candidato en 1972.

Él y Stephen Cook descubrieron de forma independiente la existencia de problemas NP-completos. Este teorema de completitud NP, a menudo llamado teorema de Cook-Levin, fue la base de uno de los siete Problemas del Premio del Milenio declarados por el Clay Mathematics Institute con un premio ofrecido de 1.000.000 de dólares. 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 recibió el Premio Knuth en 2012 por su descubrimiento de la completitud de NP y el desarrollo de la complejidad del caso promedio. Es miembro de la Academia Nacional de Ciencias de 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 Candidato en 1972. Después de investigar problemas algorítmicos de la teoría de la información en el Instituto de Transmisión de Información del Instituto Nacional de Moscú Academia de Ciencias en 1972-1973, y un puesto como científico investigador senior en el Instituto Nacional de Investigación de Automatización Integrada para la Industria del Petróleo y 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. Su asesor en el MIT fue Albert R. Meyer.

Es bien conocido por su trabajo sobre aleatoriedad en informática, complejidad e intratabilidad algorítmica, complejidad de casos promedio, fundamentos de las matemáticas y la 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 Fuera de sus mentes: las vidas y descubrimientos de 15 grandes científicos informáticos.

Levin y Stephen Cook descubrieron de forma independiente la existencia de problemas NP-completos. Este teorema de completitud NP, a menudo llamado teorema de Cook-Levin, fue la base de uno de los siete Problemas del Premio del Milenio declarados por el Clay Mathematics Institute con un premio ofrecido de 1.000.000 de dólares. 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 Levin sobre este teorema se publicó en 1973; había dado conferencias sobre las ideas contenidas en él durante algunos años antes de esa fecha (ver la encuesta de Trakhtenbrot), aunque la redacción formal completa de los resultados tuvo lugar después de la publicación de Cook.

Levin recibió el Premio Knuth en 2012 por su descubrimiento de la completitud de 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.