Леонід Анатолійович Левін ( 2 листопада 1948, Дніпропетровськ) — радянський і американський математик, фахівець в області теорії обчислювальної складності. Професор інформатики в Бостонському університеті.
Життєпис Народився 2 листопада 1948 року в Дніпропетровську.
1970 — закінчив Московський державний університет, після чого працював там же на посаді наукового співробітника під науковим керівництвом Андрія Колмогорова.
1971 — представив кандидатську дисертацію, виконавши всі формальні вимоги щодо її попереднього опробування, дисертація була схвалена Колмогоровим, усіма опонентами і головною організацією, однак вчений ступінь Левіну присуджена не була. Формальною причиною для цього послужила «невизначеність політичного обличчя» здобувача, що, в сукупності з наступними утисками в наукових колах, стали однією з причин еміграціїКутателадзе С. Премия по информатике для выходца из СССР // Троицкий вариант — Наука. № 23 (117) от 20 ноября 2012. С. 14..
В 1972—1973 роках працював в Інституті проблем передачі інформації АН СРСР, а з 1973 по 1977 роки — у Всесоюзному науково-дослідному інституті комплексної автоматизації нафтової і газової промисловості (ВНИИКАНефтегаз) на посаді старшого наукового співробітника.
У 1978 році емігрував в США. У 1979 році отримав диплом доктора філософії з математики в Массачусетському технологічному інституті.
1980 — працює і викладає в Бостонському університеті.
2014 — обраний членом Американської академії мистецтв і наук.
Основні результати в області теорії ймовірностей в застосуванні до інформатики, теорії складності обчислень.
Незалежно від Стівена Кука довів у 1971 році теорему Кука — Левіна, завдяки якій була сформульована проблема рівності класів P і NP, яка стала однією з задач тисячоліття. Робота була опублікована лише в 1973 роціЛ. А. Левин Универсальные задачи перебора (рус.) // Проблемы передачи информации. — 1973. — Т. 9, № 3. — С. 115—116., але була повідомлена на конференціях, що пізніше дозволило встановити пріоритет Левіна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..
Нагороди 2004 — Медаль Колмогорова (Лондонський університет)Second Annual Kolmogorov Lecture (англ.) 2010 — Премія ГумбольдтаLeonid Levin Wins Humboldt Research Award (англ.) 2012 — Премія Кнута
Примітки
Література Dennis Elliott Shasha, Cathy A. Lazere. Stephen Cook and Leonid Levin: A good solution is hard to find // Out of their minds: the lives and discoveries of 15 great computer scientists. — Springer, 1998. — С. 139—156. — 291 с. — (Copernicus Series). — ISBN 0387982698.
Посилання Персональная страница на сайте Бостонского университета (англ.). Curriculum vitae (англ.). Список публикаций (англ.). Диссертация А. Л. Левина Отзывы о диссертации Л. А. Левина