Премия Дональда Кнута за 2012
Премия Кнута дается за общий вклад ученого в науку, а не за отдельное яркое достижение. Формула награждения отмечает четыре десятилетия устремленных в будущее исследований Левина в теории сложности, криптографии и теории информации. Указывается, что Леонид Левин известен открытием NP-полноты — стержневого понятия вычислительной сложности. Это открытие было сделано Левиным в СССР в 1971 году независимо и практически одновременно со Стефаном Куком. Теорема Кука — Левина вошла во все учебники по компьютерной сложности. Сформулированная в связи с ней задача P=NP открывает перечень знаменитых проблем тысячелетия Института Клэя.
Научным руководителем Левина был академик Андрей Николаевич Колмогоров. Организовать защиту кандидатской диссертации, подготовленной Левиным в 1971 году, в Москве не удалось. Дело в том, что в CCCР тех лет независимость Левина толковалась как политическая неблагонадежность, а в математическом мире страны бытовали антисемитские настроения. Колмогоров попросил своего товарища академика Сергея Львовича Соболева, директора Института математики Сибирского отделения Академии наук, провести защиту кандидатской диссертации Левина в Новосибирске. Согласие было дано, но диссертация совершенно неожиданно для Соболева была забаллотирована невзирая на положительные отзывы Н.А. Шанина, Б.А. Трахтенброта и Я. Бардзиня.
Поразительным образом против диссертации выступил ученый, которому проблематика Левина была особенно близка. На защите было заявлено о неясности «политического облика» Левина — математические гадости уже добрались из столицы до Сибири. Левин не стал кандидатом наук, и отношение к нему со стороны власть предержащих после этих событий оставляло желать лучшего.
Описывая то время, Левин отмечал: «Я стал обузой для всех, с кем был связан; мне стало нельзя работать в серьезных научных учреждениях и даже неловко ходить на семинары (участников просили сообщать о моих посещениях). Мое существование в Москве начинало выглядеть бессмысленным». Левина выживали из математики и из страны.
Впрочем, выдающаяся научная одиссея Левина успешно продолжилась в США, куда он иммигрировал в 1978 году и где у него появились условия для счастливой работы и жизни. Здесь он развил теорию NP-полноты в среднем. Эта теория до сих пор наилучшим образом объясняет, почему плохие вычислительные задачи встречаются не в специальных ситуациях, а «в среднем» в условиях достаточно случайного набора исходных данных.
Список достижений Левина на американской земле весьма внушителен. Левину, Ласло Бабаи, Лэнсу Фортнау и Марио Шегеди принадлежит понятие «голографических доказательств», истинность которых может быть установлена проверкой малых кусочков. Стоит отметить, что Левину с коллегами удалось решить немало загадок современной криптографии.
Есть много оснований поздравить Леонида, порадоваться и за него, и за мировую науку. Но нельзя отделаться от чувства горечи за то, что интеллектуальный потенциал нашего соотечественника не был востребован на родине, а вызвал зависть и отторжение. Бациллы ксенофобии, самовосхваления и изоляции от мирового сообщества в научной жизни неистребимы. Как и в медицине, без санитарии в науке обойтись нельзя.
Семён Кутателадзе