| Леонид Анатольевич Левин |
|
| Дата рождения: | 2 ноября 1948(1948-11-02) (66 лет) |
|---|
| Место рождения: | Днепропетровск, Украинская ССР, СССР |
|---|
| Страна: | СССР, США |
|---|
| Научная сфера: | информатика |
|---|
| Место работы: | Бостонский университет |
|---|
| Учёная степень: | кандидат физико-математических наук (1972)
доктор философии по математике (1979) |
|---|
| Альма-матер: | МГУ (мехмат)
Массачусетский технологический институт |
|---|
| Научный руководитель: | А. Н. Колмогоров
en:Albert R. Meyer |
|---|
| Известен как: | один из авторов теоремы Кука - Левина |
|---|
| Сайт: | cs.bu.edu/~lnd/ |
|---|
| Леонид Анатольевич Левин |
Леони́д Анато́льевич Ле́вин (род. 2 ноября 1948, Днепропетровск) - советский и американский математик, специалист в области теории вычислительной сложности. Профессор информатики в Бостонском университете.
Содержание- Биография
- Награды
- Примечания
- Литература
- Ссылки
Родился 2 ноября 1948 года в Днепропетровске. В 1970 году окончил Московский государственный университет, после чего работал там же на должности научного сотрудника под научным руководством Андрея Колмогорова. В 1971 году представил кандидатскую диссертацию, выполнив все формальные требования по её предварительному апробированию, диссертация была одобрена Колмогоровым, всеми оппонентами и головной организацией, однако учёная степень Левину присуждена не была. Формальной причиной для этого послужила «неопределённость политического облика» соискателя, что, в совокупности с последующими притеснениями в научных кругах, послужили одной из причин для эмиграции.
В 1972-1973 годах работал в Институте проблем передачи информации АН СССР, а с 1973 по 1977 годы - во Всесоюзном научно-исследовательском институте комплексной автоматизации нефтяной и газовой промышленности (ВНИИКАНефтегаз) на должности старшего научного сотрудника.
В 1978 году эмигрировал в США. В 1979 году получил диплом доктора философии по математике в Массачусетском технологическом институте. С 1980 года работает и преподаёт в Бостонском университете. В 2014 году избран членом Американской академии искусств и наук.
Основные результаты - в области теории вероятностей в применении к информатике, теории сложности вычислений.
Независимо от Стивена Кука доказал в 1971 году теорему Кука - Левина, благодаря которой была сформулирована проблема равенства классов P и NP, ставшая одной из задач тысячелетия. Работа была опубликована только в 1973 году, но была доложена на конференциях, что позже позволило установить приоритет Левина.