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

ainsleigh
  • 2020-05-28
  • 1

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

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

Биография

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

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

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

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

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

Награды

Примечания

  1. от 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. . Дата обращения: 29 июня 2014. 19 апреля 2016 года.
  8. Л. А. Левин. // Проблемы передачи информации. — 1973. — Т. 9 , № 3 . — С. 115—116 . 10 октября 2017 года.
  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. от 5 марта 2016 на Wayback Machine (англ.)
  11. от 30 мая 2010 на Wayback Machine (англ.)
  12. . Дата обращения: 9 февраля 2016. Архивировано из 3 марта 2016 года.
  13. . Дата обращения: 20 ноября 2012. 16 января 2017 года.

Литература

  • Dennis Elliott Shasha, Cathy A. Lazere. Stephen Cook and Leonid Levin: A good solution is hard to find // . — Springer, 1998. — С. 139—156. — 291 с. — (Copernicus Series). — ISBN 0387982698 .

Ссылки

  • (англ.) . Дата обращения: 7 ноября 2012. 8 мая 2012 года.
  • (англ.) . Дата обращения: 7 ноября 2012. 8 мая 2012 года.
  • (англ.) . Дата обращения: 7 ноября 2012. 6 декабря 2012 года.
Источник —

ainsleigh
  • 2020-05-28
  • 1
  • Tags:
Леонид Анатольевич Левин
Дата рождения 2 ноября 1948 ( 1948-11-02 ) (75 лет)
Место рождения Днепропетровск , Украинская ССР , СССР
Страна СССР, США
Научная сфера информатика
Место работы Бостонский университет
Альма-матер МГУ (мехмат)
Массачусетский технологический институт
Учёная степень кандидат физико-математических наук (1972)
доктор философии по математике (1979)
Научный руководитель А. Н. Колмогоров
Известен как один из авторов теоремы Кука — Левина
Награды и премии
Сайт

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

The title for the last searches