В 2800 километрах к востоку от Москвы находится Новосибирск – самый крупный город в Сибири и третий по численности во всей России. В 1961 году из Москвы в Новосибирск приехал Алексей Андреевич Ляпунов и вскоре основал в Новосибирском университете кафедру теоретической кибернетики.
Первыми сотрудниками стали преимущественно бывшие московские студенты Яблонского и самого Ляпунова. Новая кафедра быстро приобрела статус центра кибернетических исследований – второго по значимости в Советском Союзе. Почти сразу к исследовательскому коллективу присоединился Борис Трахтенброт, который также занимался кибернетикой и на тот момент – в сорок с небольшим лет – уже был доктором наук; вскоре Трахтенброт стал одним из ведущих сотрудников кафедры. В 1962 году в Новосибирск приехал Ян Мартынович Барздинь, незадолго до того защитивший кандидатскую в Латвийском государственном университете в Риге. Трахтенброт и Барздинь начали совместные исследования в области сложности вычислений и привлекли к работе множество российских и латышских студентов. В середине шестидесятых ученые уже вовсю разрабатывали теорию алгоритмической сложности – аналогичную той, что в то же самое время создавалась на Западе.
Впрочем, в СССР с вычислительной сложностью все было довольно сложно. В 1984 году Трахтенброт напишет:
«Напряженность в отношениях с представителями так называемой классической школы – и в особенности с Яблонским – нас очень угнетала. Эти люди занимали крайне негативную позицию касательно применения теории алгоритмов к вопросам сложности Они не допускали и мысли о том, что вычислительную и алгоритмическую сложность можно связать с проблемой перебора. Яблонский к тому времени играл уже далеко не последнюю роль в различных организациях, занимавшихся планированием и контролем математических исследований; в дальнейшем наше противостояние только усилилось – по всей видимости, из-за разногласий по поводу необходимости перебора»[4].
Летом 1963 года в Новосибирск приехал Колмогоров и начал совместные исследования с Трахтенбротом. Ученые пытались понять, каким образом теория алгоритмов может помочь им продвинуться в изучении сложности и информации.
Из Новосибирска Колмогоров вскоре отправился в Киев, где посетил физико-математическую школу-интернат при Киевском университете. Ученый предложил школьникам несколько задач; пятнадцатилетний Леонид Левин справился почти со всеми. Позже Колмогоров пригласил его в Московский университет и взял под свое руководство. Во время учебы в аспирантуре Левин разрабатывал сразу два разных направления.
В рамках одного из них был создан оптимальный алгоритм поиска. Допустим, Элис говорит Бобу, что придумала быстрый алгоритм для задачи о клике, но отказывается его показать. Применив метод Левина, Боб сможет сам создать почти такой же быстрый алгоритм – и для этого ему не нужно будет знать, что написала Элис. В работе Левина используется модифицированный вариант колмогоровской сложности; его оптимальный алгоритм особым образом запускает все возможные алгоритмы, проверяя, дают ли они нужное решение.
Размышляя о задачах поиска и проблеме перебора, Левин пришел к понятию универсальной переборной задачи, которое было эквивалентно понятию NP-полной задачи, введенному Куком. Ученый рассмотрел шесть переборных задач, включая выполнимость, и показал их универсальность, а также сформулировал проблему равенства классов P и NP.
Блестящие результаты! И второй, безусловно, достоин награды; Стивен Кук за аналогичные достижения получил премию Тьюринга. Колмогоров, однако, счел работы Левина несколько сырыми и настоял на том, чтобы вместе довести их «до кондиции». В те годы в Советском Союзе было принято сокращать публикуемые статьи, опуская подробности доказательств. Следуя этому правилу, Левин сократил текст по максимуму и уместил все свои исследования в каких-то две страницы.
Вскоре Левин представил кандидатскую диссертацию; предыдущие работы он в нее включать не стал. Вся советская молодежь тогда состояла в комсомоле – молодежной организации Коммунистической партии. Независимый и свободомыслящий Левин открыто саботировал комсомольские мероприятия, не осознавая, вероятно, к чему это может привести. В конце концов его диссертацию не приняли по причине «неопределенности политического облика».
Политическая травля Левина не прекращалась. В 1978 году ему удалось эмигрировать в Соединенные Штаты. Альберт Мейер из Массачусетского технологического института стал его научным руководителем; спустя год Левину присудили степень доктора философии – за выдающиеся результаты, полученные еще в Советском Союзе. В настоящее время Левин – профессор Бостонского университета.
В Соединенных Штатах об исследованиях Левина узнали в середине семидесятых, когда проблема равенства P и NP уже широко обсуждалась в научных кругах. Левину не пришлось разделить с Куком премию Тьюринга, которую тот получил в 1982 году; и все-таки основной результат касательно NP-полноты со временем стали называть теоремой Кука–Левина – правда, произошло это уже ближе к девяностым.
