Золотой билет - Страница 30

Впрочем, в СССР с вычислительной сложностью все было довольно сложно. В 1984 году Трахтенброт напишет:

...

«Напряженность в отношениях с представителями так называемой классической школы – и в особенности с Яблонским – нас очень угнетала. Эти люди занимали крайне негативную позицию касательно применения теории алгоритмов к вопросам сложности <…> Они не допускали и мысли о том, что вычислительную и алгоритмическую сложность можно связать с проблемой перебора. Яблонский к тому времени играл уже далеко не последнюю роль в различных организациях, занимавшихся планированием и контролем математических исследований; в дальнейшем наше противостояние только усилилось – по всей видимости, из-за разногласий по поводу необходимости перебора».

Летом 1963 года в Новосибирск приехал Колмогоров и начал совместные исследования с Трахтенбротом. Ученые пытались понять, каким образом теория алгоритмов может помочь им продвинуться в изучении сложности и информации.

Из Новосибирска Колмогоров вскоре отправился в Киев, где посетил физико-математическую школу-интернат при Киевском университете. Ученый предложил школьникам несколько задач; пятнадцатилетний Леонид Левин справился почти со всеми. Позже Колмогоров пригласил его в Московский университет и взял под свое руководство. Во время учебы в аспирантуре Левин разрабатывал сразу два разных направления.

В рамках одного из них был создан оптимальный алгоритм поиска. Допустим, Элис говорит Бобу, что придумала быстрый алгоритм для задачи о клике, но отказывается его показать. Применив метод Левина, Боб сможет сам создать почти такой же быстрый алгоритм – и для этого ему не нужно будет знать, что написала Элис. В работе Левина используется модифицированный вариант колмогоровской сложности; его оптимальный алгоритм особым образом запускает все возможные алгоритмы, проверяя, дают ли они нужное решение.

Размышляя о задачах поиска и проблеме перебора, Левин пришел к понятию универсальной переборной задачи, которое было эквивалентно понятию NP-полной задачи, введенному Куком. Ученый рассмотрел шесть переборных задач, включая выполнимость, и показал их универсальность, а также сформулировал проблему равенства классов P и NP.

Блестящие результаты! И второй, безусловно, достоин награды; Стивен Кук за аналогичные достижения получил премию Тьюринга. Колмогоров, однако, счел работы Левина несколько сырыми и настоял на том, чтобы вместе довести их «до кондиции». В те годы в Советском Союзе было принято сокращать публикуемые статьи, опуская подробности доказательств. Следуя этому правилу, Левин сократил текст по максимуму и уместил все свои исследования в каких-то две страницы.

Вскоре Левин представил кандидатскую диссертацию; предыдущие работы он в нее включать не стал. Вся советская молодежь тогда состояла в комсомоле – молодежной организации Коммунистической партии. Независимый и свободомыслящий Левин открыто саботировал комсомольские мероприятия, не осознавая, вероятно, к чему это может привести. В конце концов его диссертацию не приняли по причине «неопределенности политического облика».

Политическая травля Левина не прекращалась. В 1978 году ему удалось эмигрировать в Соединенные Штаты. Альберт Мейер из Массачусетского технологического института стал его научным руководителем; спустя год Левину присудили степень доктора философии – за выдающиеся результаты, полученные еще в Советском Союзе. В настоящее время Левин – профессор Бостонского университета.

В Соединенных Штатах об исследованиях Левина узнали в середине семидесятых, когда проблема равенства P и NP уже широко обсуждалась в научных кругах. Левину не пришлось разделить с Куком премию Тьюринга, которую тот получил в 1982 году; и все-таки основной результат касательно NP-полноты со временем стали называть теоремой Кука–Левина – правда, произошло это уже ближе к девяностым.

Потепление в отношениях между СССР и США началось в 1980-х. В седьмой главе мы поговорим о попытках разработать методы для доказательства неравенства P и NP, опирающиеся на теорию сложности схем; ведущую роль в этих разработках сыграл советский и российский математик Александр Разборов, бывший в ту пору студентом.

После распада Советского Союза пришел конец и вынужденной изоляции ученых. А с развитием интернета весь мир превратился в единое научно-исследовательское сообщество.

Письмо Гёделя

В 1956 году Курт Гёдель написал письмо Джону фон Нейману – пионеру в информатике и многих других областях науки. В письме Гёдель на немецком языке рассуждал о проблеме выполнимости и о вопросе равенства классов P и NP, только формулировал он этот вопрос в несколько иных терминах. По словам ученого, если бы мы жили в мире, в котором P = NP, то «математикам более не пришлось бы тратить время на задачи типа „да-нет“: этот труд за них выполняли бы машины <…> Впрочем, я уже перестал относить эту возможность к области несбыточного». Идеи Гёделя на пятнадцать лет опередили работы Левина и Кука.

Получил ли фон Нейман то письмо? Ответил ли он Гёделю? Мы этого не знаем; на тот момент фон Нейман уже был болен раком, и в 1957 году его не стало. О письме научное сообщество узнало лишь в конце восьмидесятых, когда за вопросом о равенстве P и NP уже прочно закрепился статус одной из центральных открытых научных проблем. Сам Гёдель умер в 1978 году; душевное расстройство, омрачившее последние годы его жизни, помешало ученому понять, что Кук в своей работе поднял тот же вопрос.