Золотой билет. P, NP и границы возможного - Лэнс Фортноу

Колмогоров придумал определять степень случайности последовательности в зависимости от длины ее самого короткого описания. Первая последовательность – это «51 девятка». Вторая – «1/√2». Описать третью можно, только повторив ее целиком: «982 922 216 207 267 591 232 795 977 564 268 549 473 337 889 037 097». Конечно, «описание» – понятие неформальное; Колмогоров формализовал его через понятие компьютерной программы.

Аналогичные идеи независимо друг от друга и от Колмогорова разработали также двое американских ученых: Рэй Соломонов (из Кливленда, а не из СССР, как можно было бы подумать по его фамилии) – чуть раньше Колмогорова, Грегори Хайтин – чуть позже. Однако Колмогоров и его последователи углубились в эту тему гораздо дальше, так что сложность, определяемую через длину описания, стали называть «колмогоровской».

Последовательность называется случайной, если самый короткий способ описать ее – это привести ее целиком, как в случае с нашим третьим примером.

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

982 922 216 207 267 591 232 795 977 564 268 549 473 337 889 037 097

действительно является случайной: чтобы доказать это, мне пришлось бы проанализировать все возможные описания меньшей длины, а эта задача явно не из легких!

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

В 2800 километрах к востоку от Москвы находится Новосибирск – самый крупный город в Сибири и третий по численности во всей России. В 1961 году из Москвы в Новосибирск приехал Алексей Андреевич Ляпунов и вскоре основал в Новосибирском университете кафедру теоретической кибернетики.

Первыми сотрудниками стали преимущественно бывшие московские студенты Яблонского и самого Ляпунова. Новая кафедра быстро приобрела статус центра кибернетических исследований – второго по значимости в Советском Союзе. Почти сразу к исследовательскому коллективу присоединился Борис Трахтенброт, который также занимался кибернетикой и на тот момент – в сорок с небольшим лет – уже был доктором наук; вскоре Трахтенброт стал одним из ведущих сотрудников кафедры. В 1962 году в Новосибирск приехал Ян Мартынович Барздинь, незадолго до того защитивший кандидатскую в Латвийском государственном университете в Риге. Трахтенброт и Барздинь начали совместные исследования в области сложности вычислений и привлекли к работе множество российских и латышских студентов. В середине шестидесятых ученые уже вовсю разрабатывали теорию алгоритмической сложности – аналогичную той, что в то же самое время создавалась на Западе.

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

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

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

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

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

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

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

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

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