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

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

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

Биография

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

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

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

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

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

Награды

2004 — Медаль Колмогорова ( Лондонский университет )
2010 — Премия Гумбольдта
2012 — Премия Кнута

Примечания

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