ПРЕМИЯ КНУТА 2012
ПРИСУЖДЕНА ЛЕОНИДУ ЛЕВИНУ

Leonid Levin

Днями объявлено, что Леониду Анатольевичу Левину, уроженцу Днепропетровска, выпускнику МГУ, а ныне профессору Бостонского университета, присуждена премия Кнута за 2012 г.

Премия Кнута за выдающийся вклад в основание науки о компьютерах присуждается с 1996 года под эгидой двух весьма представительных международных организаций — Ассоциации компьютерных технологий и Компьютерного общества Института инженеров-электриков и электроников. Материальный компонент премии 5000 долларов. Эта сумма воображение читателя никак не поражает, и событие может показаться заурядным, так как премий присуждается великое множество и за всеми уследить нет никакой возможности.

Между тем каждая премия Кнута — событие весьма незаурядное для всех, кто хоть немного ориентируется в современной информатике и программировании. Дело в том, что Дональд Кнут — здравствующий учёный, автор многотомного сочинения «Искусство программирования», по которому учились и учатся практически все программисты нашего времени. Дональд Кнут подарил учёным всех специальностей прославленные программы TeX и Metafont для подготовки статей с научной символикой, дав образец бескорыстного служения делу науки и просвещения. Увидеть свое имя в перечне обладателей премии Кнута — редкая честь для любого компьютерщика.

Премия Кнута даётся за общий вклад учёного в науку, а не за отдельное яркое достижение. Формула награждения отмечает четыре десятилетия устремлённых в будущее исследований Левина в теории сложности, криптографии и теории информации. Указывается, что Левин известен открытием NP-полноты, стержневого понятия вычислительной сложности. Это открытие было сделано Левиным в СССР в 1971 независимо и практически одновременно со Стефаном Куком. Теорема Кука — Левина вошла во все учебники по компьютерной сложности. Сформулированная в связи с ней задача P=NP открывает перечень знаменитых проблем тысячелетия Института Клея.

Научным руководителем Левина был А. Н. Колмогоров. Организовать защиту кандидатской диссертации, подготовленной Левиным в 1971 г., в Москве не удалось. Дело в том, что в CCCР тех лет независимость Левина толковалась как политическая неблагонадежность, а в математическом мире страны бытовали антисемитские настроения. А. Н. Колмогоров попросил своего товарища С. Л. Соболева, директора Института математики Сибирского отделения Академии наук, провести защиту кандидатской диссертации Левина в Новосибирске. Согласие было дано, но диссертация совершенно неожиданно для С. Л. Соболева была забаллотирована невзирая на положительные отзывы Н. А. Шанина, Б. А. Трахтенброта и Я. М. Бардзиня. Поразительным образом против диссертации выступил учёный, которому проблематика Левина была особенно близка. На защите было заявлено о неясности «политического облика» Левина — математические гадости уже добрались из столицы до Сибири. Левин не стал кандидатом и отношение к нему со стороны властей предержащих после этих событий оставляло желать много лучшего.

Описывая то время, Левин отмечал: «Я стал обузой для всех, с кем был связан; мне стало нельзя работать в серьёзных научных учреждениях и даже неловко ходить на семинары (участников просили сообщать о моих посещениях). Моё существование в Москве начинало выглядеть бессмысленным». Левина выживали из математики и из страны.

Выдающаяся научная одиссея Левина успешно продолжилась в США, куда он иммигрировал в 1978 г. и где у него появились условия для счастливой работы и жизни. Здесь он развил теорию NP-полноты в среднем. Эта теория до сих пор наилучшим образом объясняет почему плохие вычислительные задачи встречаются не в специальных ситуациях, а «в среднем» в условиях достаточно случайного набора исходных данных. Список достижений Левина на американской земле весьма внушителен. Левину, Ласло Бабаи, Лэнсу Фортнау и Марио Шегеди принадлежит понятие «голографических доказательств», истинность которых может быть установлена проверкой малых кусочков. Стоит отметить, что Левину с коллегами удалось решить немало загадок современной криптографии.

Есть много оснований поздравить Леонида, порадоваться и за него, и за мировую науку. Но нельзя отделаться от чувства горечи за то, что интеллектуальный потенциал нашего соотечественника не был востребован на родине, а вызвал зависть и отторжение. Бациллы ксенофобии, воспрепятствования, самовосхваления и изоляции от мирового сообщества в научной жизни неистребимы. Как и в медицине, без санитарии в науке обойтись нельзя.

С. Кутателадзе

8 ноября 2012 г.


Троицкий вариант — Наука, № 23 (117), 20 ноября 2012 г., с. 14.


Available in English


English Page Russian Page
© Кутателадзе С. С. 2012