Леонид Анатольевич Левин ( / l eɪ . oʊ ˈ n iː d ˈ l ɛ v ɪ n / lay-oh- НУЖЕН ЛЕВ -ин ; ‹См. Tfd› русский : Леони́д Анато́льевич Ле́вин ; украинский : Леоні́д Анато́лійович Ле́він ; родился 2 ноября 1948 г. ) — советско-американский математик и учёный-компьютерщик .
Он известен своими работами по случайности в вычислениях , алгоритмической сложности и неразрешимости, сложности в среднем случае , [1] основам математики и компьютерной науки , алгоритмической вероятности , теории вычислений и теории информации . Он получил степень магистра в Московском университете в 1970 году, где он учился у Андрея Колмогорова , и завершил академические требования к степени кандидата наук в 1972 году. [2]
Он и Стивен Кук независимо друг от друга открыли существование NP-полных задач . Эта теорема о NP-полноте, часто называемая теоремой Кука–Левина , легла в основу одной из семи задач Премии тысячелетия, объявленной Математическим институтом Клэя с призом в 1 000 000 долларов. Теорема Кука–Левина стала прорывом в компьютерной науке и важным шагом в развитии теории сложности вычислений .
В 2012 году Левин был удостоен премии Кнута [3] за открытие NP-полноты и разработку сложности в среднем случае . Он является членом Национальной академии наук США и членом Американской академии искусств и наук .
Он получил степень магистра в Московском университете в 1970 году, где он учился у Андрея Колмогорова , и завершил обучение в аспирантуре в 1972 году. [2] [4] После исследования алгоритмических проблем теории информации в Московском институте передачи информации Национальной академии наук в 1972–1973 годах и должности старшего научного сотрудника в Московском национальном научно-исследовательском институте комплексной автоматизации нефтегазовой промышленности в 1973–1977 годах он эмигрировал в США в 1978 году, а также получил степень доктора философии в Массачусетском технологическом институте (MIT) в 1979 году. [2] Его научным руководителем в MIT был Альберт Р. Мейер .
Он хорошо известен своими работами в области случайности в вычислениях , алгоритмической сложности и неразрешимости, сложности в среднем случае , [1] основами математики и компьютерной науки , алгоритмической вероятности , теории вычислений и теории информации .
Его жизнь описана в главе книги « Выжившие из ума: жизни и открытия 15 великих учёных-компьютерщиков» . [5]
Левин и Стивен Кук независимо друг от друга открыли существование NP-полных задач . Эта теорема о NP-полноте, часто называемая теоремой Кука–Левина , легла в основу одной из семи проблем Премии тысячелетия, объявленных Математическим институтом Клэя с призом в 1 000 000 долларов. Теорема Кука–Левина стала прорывом в компьютерной науке и важным шагом в развитии теории сложности вычислений . Журнальная статья Левина об этой теореме была опубликована в 1973 году; [6] он читал лекции об идеях, изложенных в ней, в течение нескольких лет до этого времени (см. обзор Трахтенброта ), [7] хотя полное формальное написание результатов произошло после публикации Кука.
В 2012 году Левин был удостоен премии Кнута [3] за открытие NP-полноты и разработку теории сложности в среднем случае .
В настоящее время он является профессором компьютерных наук в Бостонском университете , где начал преподавать в 1980 году.
