Леонид Анатольевич Левин ( / l eɪ . oʊ ˈ n iː d ˈ l ɛ v ɪ n / lay-oh- НУЖЕН ЛЕВ -ин ; русский : Леони́д Анато́льевич Ле́вин ; украинский : Леоні́д Анато́лійович Ле́він ; родился 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] Его советником в Массачусетском технологическом институте был Альберт Р. Мейер .
Он хорошо известен своими работами в области случайности в вычислениях , алгоритмической сложности и неразрешимости, сложности среднего случая , [1] основ математики и информатики , алгоритмической вероятности , теории вычислений и теории информации .
Его жизнь описана в главе книги « Вне их разума: жизнь и открытия 15 великих ученых-компьютерщиков» . [5]
Левин и Стивен Кук независимо друг от друга обнаружили существование NP-полных задач . Эта теорема NP-полноты, часто называемая теоремой Кука-Левина , легла в основу одной из семи задач Премии тысячелетия, объявленной Математическим институтом Клея с предложенной премией в 1 000 000 долларов. Теорема Кука-Левина стала прорывом в информатике и важным шагом в развитии теории сложности вычислений . Журнальная статья Левина по этой теореме была опубликована в 1973 году; [6] он читал лекции по изложенным в ней идеям за несколько лет до этого (см. обзор Трахтенброта ), [7] хотя полное формальное изложение результатов произошло после публикации Кука.
Левин был удостоен премии Кнута в 2012 году [3] за открытие NP-полноты и развитие сложности в среднем случае .
В настоящее время он является профессором информатики в Бостонском университете , где начал преподавать в 1980 году.
