Премия по информатике для выходца из СССР

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

Эта премия за вы­дающийся вклад в основания науки о компьютерах присужда­ется с 1996 года под эги­дой двух весьма пред­ставительных международных организаций — Ассоциации вы­числительной техники и Компьютерного общества Институ­та инженеров по электротехнике и электронике (www.sigact.org/Prizes/Knuth/). Материальный компонент премии — 5000 долларов. Эта сумма воображение читателя никак не поражает, и событие мо­жет показаться заурядным, так как премий присуждается великое множество и за всеми уследить нет никакой возможности.

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

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

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

Поразительным образом против диссертации выступил ученый, которому проблематика Левина была особенно близка. На защите было заявлено о неясности «политического облика» Левина — мате­матические гадости уже добрались из столицы до Сибири. Левин не стал кандидатом наук, и отношение к нему со стороны власть преде­ржащих после этих событий оставляло желать лучшего.

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

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

Список достижений Левина на американской земле весьма вну­шителен. Левину, Ласло Бабаи, Лэнсу Фортнау и Марио Шегеди при­надлежит понятие «голографических доказательств», истинность ко­торых может быть установлена проверкой малых кусочков. Стоит от­метить, что Левину с коллегами удалось решить немало загадок со­временной криптографии.

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

Семён Кутателадзе