Леони́д Анато́льевич Ле́вин (род. 2 ноября 1948, Днепропетровск) — советский и американский , специалист в области теории вычислительной сложности. Профессор информатики в Бостонском университете.
Член Национальной академии наук США (2019)National Academy of Sciences Elects Members and Foreign Associates; Historic Number of Women Elected to Its Membership , 30 апреля 2019.
Биография Родился 2 ноября 1948 года в Днепропетровске. В 1970 году окончил Московский государственный университет, после чего работал там же на должности научного сотрудника под научным руководством Андрея Колмогорова. В 1971 году представил кандидатскую диссертацию, выполнив все формальные требования по её предварительному апробированию, диссертация была одобрена Колмогоровым, всеми оппонентами и головной организацией, однако учёная степень Левину присуждена не была. Формальной причиной для этого послужила «неопределённость политического облика» соискателя, что, в совокупности с последующими притеснениями в научных кругах, послужили одной из причин для эмиграцииКутателадзе С. Премия по информатике для выходца из СССР // Троицкий вариант — Наука. № 23 (117) от 20 ноября 2012. С. 14..
В 1972—1973 годах работал в Институте проблем передачи информации АН СССР, а с 1973 по 1977 годы — во Всесоюзном научно-исследовательском институте комплексной автоматизации нефтяной и газовой промышленности (ВНИИКАНефтегаз) на должности старшего научного сотрудника.
В 1978 году эмигрировал в США. В 1979 году получил диплом доктора философии по математике в Массачусетском технологическом институте. С 1980 года работает и преподаёт в Бостонском университете. В 2014 году избран членом Американской академии искусств и наук.
Основные результаты — в области теории вероятностей в применении к информатике, теории сложности вычислений.
Независимо от Стивена Кука доказал в 1971 году теорему Кука — Левина, благодаря которой была сформулирована проблема равенства классов P и NP, ставшая одной из задач тысячелетия. Работа была опубликована только в 1973 году, но была доложена на конференциях, что позже позволило установить приоритет Левина.
Награды 2004 — Медаль Колмогорова (Лондонский университет)Second Annual Kolmogorov Lecture 2010 — Премия ГумбольдтаLeonid Levin Wins Humboldt Research Award 2012 — Премия Кнута
Примечания
Литература
Ссылки
Диссертация А. Л. Левина Отзывы о диссертации Л. А. Левина
Категория:Преподаватели Бостонского университета Категория:Учёные в области информатики США Категория:Ученики Колмогорова Категория:Лауреаты премии Гумбольдта Категория:Члены Национальной академии наук США Категория:Члены Американской академии искусств и наук