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

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

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

Член Национальной академии наук США (2019)[1].

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

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

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

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

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

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

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

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

  1. National Academy of Sciences Elects Members and Foreign Associates; Historic Number of Women Elected to Its Membership Архивная копия от 19 июня 2020 на Wayback Machine, 30 апреля 2019  (англ.)
  2. Кандидатская диссертация Л. А. Левина. Дата обращения: 7 ноября 2012. Архивировано 29 марта 2017 года.
  3. Отзывы на диссертацию Л. А. Левина. Дата обращения: 7 ноября 2012. Архивировано 4 марта 2016 года.
  4. Б. А. Трахтенброт. Памяти Андрея Петровича Ершова. Дата обращения: 29 июня 2014. Архивировано 19 июня 2017 года.
  5. Интервью с Леонидом Левиным. Дата обращения: 30 июня 2014. Архивировано 14 октября 2017 года.
  6. Кутателадзе С. Премия по информатике для выходца из СССР Архивная копия от 25 октября 2016 на Wayback Machine // Троицкий вариант — Наука. № 23 (117) от 20 ноября 2012. С. 14.
  7. The New 2014 Academy Members. Дата обращения: 29 июня 2014. Архивировано 19 апреля 2016 года.
  8. Л. А. Левин. Универсальные задачи перебора // Проблемы передачи информации. — 1973. — Т. 9, № 3. — С. 115—116.
  9. 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.
  10. Second Annual Kolmogorov Lecture Архивная копия от 5 марта 2016 на Wayback Machine (англ.)
  11. Leonid Levin Wins Humboldt Research Award Архивная копия от 30 мая 2010 на Wayback Machine (англ.)
  12. ACM press release, August 22, 2012. Дата обращения: 9 февраля 2016. Архивировано из оригинала 3 марта 2016 года.
  13. Премия Кнута 2012 присуждена Леониду Левину. Дата обращения: 20 ноября 2012. Архивировано 16 января 2017 года.

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

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