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 en aleatoriedad en computación , complejidad e intratabilidad algorítmica, complejidad de casos 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 . 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]
Él y Stephen Cook descubrieron de forma independiente la existencia de problemas NP-completos . Este teorema de NP-completo, a menudo llamado teorema de Cook-Levin , fue la base de uno de los siete problemas del Premio del Milenio declarados por el Instituto de Matemáticas Clay con un premio de $1,000,000 ofrecido. El teorema de Cook-Levin fue un gran avance en la ciencia 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 de caso promedio . Es miembro de la Academia Nacional de Ciencias de los Estados Unidos y miembro de la Academia Estadounidense de las Artes y las Ciencias .
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 Moscú de la Academia Nacional de Ciencias en 1972-1973, y un puesto como científico investigador senior en el Instituto Nacional de Investigación de Moscú de Automatización Integrada para la Industria del Petróleo y el Gas 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 muy conocido por su trabajo en aleatoriedad en informática , complejidad algorítmica e intratabilidad, complejidad de casos 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-completo, a menudo llamado teorema de Cook-Levin , fue la base de uno de los siete problemas del Premio del Milenio declarados por el Instituto de Matemáticas Clay con un premio de $1,000,000 ofrecido. El teorema de Cook-Levin fue un gran avance en la ciencia 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 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 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 enseñar en 1980.
