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

Леонид Анатольевич Левин
Леонид Анатольевич Левин
Дата рождения	2 ноября 1948(1948-11-02) (74 года)
Место рождения	Днепропетровск, Украинская ССР, СССР
Страна	СССР, США
Научная сфера	информатика
Место работы	Бостонский университет
Альма-матер	МГУ (мехмат) ; Массачусетский технологический институт
Учёная степень	кандидат физико-математических наук (1972) ; доктор философии по математике (1979)
Научный руководитель	А. Н. Колмогоров; en:Albert R. Meyer
Известен как	один из авторов теоремы Кука — Левина
Награды и премии	премия Кнута (2012) стипендия Александра фон Гумбольдта[d] премия Гумбольдта стипендия Гуггенхайма (1993)
Сайт	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].

НаградыПравить

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

ПримечанияПравить

↑ National Academy of Sciences Elects Members and Foreign Associates; Historic Number of Women Elected to Its Membership Архивная копия от 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.
↑ The New 2014 Academy Members (неопр.). Дата обращения: 29 июня 2014. Архивировано 19 апреля 2016 года.
↑ Л. А. Левин. Универсальные задачи перебора (рус.) // Проблемы передачи информации. — 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.
↑ Second Annual Kolmogorov Lecture Архивная копия от 5 марта 2016 на Wayback Machine (англ.)
↑ Leonid Levin Wins Humboldt Research Award Архивная копия от 30 мая 2010 на Wayback Machine (англ.)
↑ ACM press release, August 22, 2012 (неопр.). Дата обращения: 9 февраля 2016. Архивировано из оригинала 3 марта 2016 года.
↑ Премия Кнута 2012 присуждена Леониду Левину (неопр.). Дата обращения: 20 ноября 2012. Архивировано 16 января 2017 года.

ЛитератураПравить

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.

СсылкиПравить

Персональная страница на сайте Бостонского университета (англ.). Дата обращения: 7 ноября 2012. Архивировано 8 мая 2012 года.
Curriculum vitae (англ.). Дата обращения: 7 ноября 2012. Архивировано 8 мая 2012 года.
Список публикаций (англ.). Дата обращения: 7 ноября 2012. Архивировано 6 декабря 2012 года.
Диссертация А. Л. Левина
Отзывы о диссертации Л. А. Левина

[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 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]