Леонид Левин - Leonid Levin

Леонид Анатольевич Левин
ЛеонидЛевин2010.jpg
Леонид Левин в 2010 году
Родился ( 1948-11-02 )2 ноября 1948 г. (72 года)
Днепропетровск , Украинская ССР , Советский Союз
Альма-матер Московский университет
Массачусетский технологический институт
Известен Теорема Кука – Левина.
Средняя сложность.
Исследование сложности, случайности, информации.
Награды Приз Кнута (2012)
Научная карьера
Поля математика
информатика
Учреждения Бостонский университет
Докторант Андрей Колмогоров , Альберт Р. Мейер

Леонид Анатольевич Левин ( / л eɪ . Oʊ п я д л ɛ об ɪ н / лежал-OH- НЕОБХОДИМОСТЬ МВВ -в ; русском : Леонид Анатольевич Левин ; украинский : Леонід Анатолійович Левін ; родился 2 ноября 1948) советский -Американский математик и ученый-компьютерщик .

Он известен своими работами в области случайности в вычислениях , алгоритмической сложности и неразрешимости, средней сложности , основ математики и информатики , алгоритмической вероятности , теории вычислений и теории информации . В 1970 году он получил степень магистра в Московском университете, где учился у Андрея Колмогорова, а в 1972 году получил ученую степень кандидата наук .

Он и Стивен Кук независимо друг от друга обнаружили существование NP-полных проблем . Эта теорема о NP-полноте, часто называемая теоремой Кука – Левина , явилась основой для одной из семи задач, связанных с Премией тысячелетия, объявленных Институтом математики Клэя с предложенной премией в размере 1 000 000 долларов. Теорема Кука – Левина явилась прорывом в информатике и важным шагом в развитии теории вычислительной сложности .

Левин был удостоен премии Кнута в 2012 году за открытие NP-полноты и разработку средней сложности . Он является членом Национальной академии наук США и научным сотрудником Американской академии искусств и наук .

биография

Он получил степень магистра в Московском университете в 1970 году, где учился у Андрея Колмогорова и завершил ученую степень кандидата наук в 1972 году. После исследования алгоритмических проблем теории информации в Московском институте передачи информации Национальной академии наук в 1972–1973 годах. и занимал должность старшего научного сотрудника в Московском национальном научно-исследовательском институте комплексной автоматизации нефтегазовой промышленности в 1973–1977 гг., эмигрировал в США в 1978 г., где также получил степень доктора философии. в Массачусетском технологическом институте (MIT) в 1979 году. Его советником в MIT был Альберт Р. Мейер .

Он хорошо известен своими работами в области случайности в вычислениях , алгоритмической сложности и неразрешимости, средней сложности , основ математики и информатики , алгоритмической вероятности , теории вычислений и теории информации .

Его жизнь описана в главе книги « Не в своем уме: жизни и открытия 15 великих ученых-компьютерщиков» .

Левин и Стивен Кук независимо друг от друга обнаружили существование NP-полных проблем . Эта теорема о NP-полноте, часто называемая теоремой Кука – Левина , явилась основой для одной из семи задач, связанных с Премией тысячелетия, объявленных Институтом математики Клэя с предложенной премией в размере 1 000 000 долларов. Теорема Кука – Левина явилась прорывом в информатике и важным шагом в развитии теории вычислительной сложности . Журнальная статья Левина по этой теореме была опубликована в 1973 г .; он читал лекции по содержащимся в нем идеям за несколько лет до этого (см. обзор Трахтенброта ), хотя полное формальное написание результатов было проведено после публикации Кука.

Левин был удостоен премии Кнута в 2012 году за открытие NP-полноты и разработку средней сложности .

В настоящее время он является профессором информатики в Бостонском университете , где начал преподавать в 1980 году.

Примечания

использованная литература

внешние ссылки