Leonid Anatolievich Levin ( / l eɪ . oʊ ˈ n iː d ˈ l ɛ v ɪ n / lay-oh- NECESITA LEV -in ; ruso : Леони́д Анато́льевич Ле́вин ; ucraniano : Леоні́д Анато́лійович Ле́ він ; nacido el 2 de noviembre de 1948) es un soviético -Matemático e informático estadounidense .
Es conocido por su trabajo sobre aleatoriedad en informática , complejidad e intratabilidad algorítmica , complejidad de casos promedio , [1] 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. [2]
É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 de 1.000.000 de dólares 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 recibió el Premio Knuth en 2012 [3] 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 .
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. [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 Moscú 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. [2] 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 , [1] 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 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 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 de 1.000.000 de dólares 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 Levin sobre este teorema se publicó en 1973; [6] había dado conferencias sobre las ideas contenidas en él durante algunos años antes de esa fecha (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 recibió el Premio Knuth en 2012 [3] 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.
