Левин, Леонид Анатольевич

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Леонид Анатольевич Левин
LeonidLevin2010.jpg
Дата рождения 2 ноября 1948(1948-11-02) (69 лет)
Место рождения Днепропетровск, Украинская ССР, СССР
Страна СССР, США
Научная сфера информатика
Место работы Бостонский университет
Альма-матер МГУ (мехмат)
Массачусетский технологический институт
Учёная степень кандидат физико-математических наук (1972)
доктор философии по математике (1979)
Научный руководитель А. Н. Колмогоров
en:Albert R. Meyer
Известен как один из авторов теоремы Кука — Левина
Награды и премии
Сайт cs.bu.edu/~lnd/
Commons-logo.svg Леонид Анатольевич Левин на Викискладе

Леони́д Анато́льевич Ле́вин (род. 2 ноября 1948, Днепропетровск) — советский и американский математик, специалист в области теории вычислительной сложности. Профессор информатики в Бостонском университете.

Биография[править | править код]

Родился 2 ноября 1948 года в Днепропетровске. В 1970 году окончил Московский государственный университет, после чего работал там же на должности научного сотрудника под научным руководством Андрея Колмогорова. В 1971 году представил кандидатскую диссертацию[1], выполнив все формальные требования по её предварительному апробированию, диссертация была одобрена Колмогоровым, всеми оппонентами и головной организацией[2], однако учёная степень Левину присуждена не была[3][4]. Формальной причиной для этого послужила «неопределённость политического облика» соискателя, что, в совокупности с последующими притеснениями в научных кругах, послужили одной из причин для эмиграции[5].

В 1972—1973 годах работал в Институте проблем передачи информации АН СССР, а с 1973 по 1977 годы — во Всесоюзном научно-исследовательском институте комплексной автоматизации нефтяной и газовой промышленности (ВНИИКАНефтегаз) на должности старшего научного сотрудника.

В 1978 году эмигрировал в США. В 1979 году получил диплом доктора философии по математике в Массачусетском технологическом институте. С 1980 года работает и преподаёт в Бостонском университете. В 2014 году избран членом Американской академии искусств и наук[6].

Основные результаты — в области теории вероятностей в применении к информатике, теории сложности вычислений.

Независимо от Стивена Кука доказал в 1971 году теорему Кука — Левина, благодаря которой была сформулирована проблема равенства классов P и NP, ставшая одной из задач тысячелетия. Работа была опубликована только в 1973 году[7], но была доложена на конференциях, что позже позволило установить приоритет Левина[8].

Награды[править | править код]

Примечания[править | править код]

  1. Кандидатская диссертация Л. А. Левина
  2. Отзывы на диссертацию Л. А. Левина
  3. Б. А. Трахтенброт. Памяти Андрея Петровича Ершова
  4. Интервью с Леонидом Левиным
  5. Кутателадзе С. Премия по информатике для выходца из СССР // Троицкий вариант — Наука. № 23 (117) от 20 ноября 2012. С. 14.
  6. The New 2014 Academy Members
  7. Л. А. Левин Универсальные задачи перебора (рус.) // Проблемы передачи информации. — 1973. — Т. 9, № 3. — С. 115—116.
  8. Boris A. Trakhtenbrot A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms (англ.) // Annals of the History of Computing. — 1984. — Vol. 6, no. 4. — P. 384—400.
  9. Second Annual Kolmogorov Lecture (англ.)
  10. Leonid Levin Wins Humboldt Research Award (англ.)
  11. ACM press release, August 22, 2012  (недоступная ссылка — история). Проверено 9 февраля 2016. Архивировано 3 марта 2016 года.
  12. Премия Кнута 2012 присуждена Леониду Левину

Литература[править | править код]

Ссылки[править | править код]