Золотой билет

Поиск эффективных алгоритмов начался около 3000 лет назад, когда люди впервые стали применять арифметику для ускорения процесса сложения больших чисел. Однако наша отправная точка – тридцатые годы прошлого века: именно в этот период зародилась теория алгоритмов.

Алан Тьюринг

Мы освоили космос. Телескопы переносят нас в отдаленные уголки галактики, позволяя изучать историю развития Вселенной. Через микроскопы мы наблюдаем за атомами; мы даже изобрели огромные машины, в которых эти атомы сталкиваются, распадаясь на еще более мелкие частички. А еще мы расшифровали человеческий геном. И все же одну из самых главных загадок представляет собой то небольшое устройство, которым мы ежедневно пользуемся дома, в машине, и даже носим в кармане. Мы называем его компьютером. Так что же это такое?

Слово computer появилось еще в XVII веке. В те времена никому и в голову не приходило изобретать машины, которые бы что-либо вычисляли. Компьютерами, или вычислителями, называли мастеров счета, занимавшихся вычислениями профессионально. С развитием банковской системы на вычислителей «свалились» еще и вклады и кредиты.

Согласно Оксфордскому словарю, для обозначения механического счетного устройства слово computer впервые применили в 1897 году, а для электронного – в сороковых годах прошлого века. Так от людей-вычислителей термин перешел к огромным установкам из нескольких вычислительных машин, а затем и к компьютерам, которыми мы пользуемся сейчас.

Если абстрагироваться от технической части, то задача компьютера – получить входные данные, обработать их согласно заданным инструкциям и выдать некий результат. С этой точки зрения компьютером является даже обычная почта, которая принимает на вход письмо, обрабатывает указанный на нем адрес и доставляет письмо получателю, а также любой живой организм, который обрабатывает последовательность ДНК и производит необходимые для жизни белки.

А как обстоит дело с самим процессом вычисления? Есть ли что-то такое, что вычислению не поддается? Вопрос был решен еще до появления вычислительных машин: в 1936 году ответ на него дал великий математик Алан Тьюринг. Размышляя над тем, как рассуждают математики, Тьюринг пришел к формальной математической модели вычислительного процесса, которая впоследствии стала классической. Теперь ее называют машиной Тьюринга.

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

Машина Тьюринга казалась очень простой, однако, по словам ученого, на ней можно было вычислить все, что вообще поддавалось вычислению. Почти в то же самое время Алонзо Чёрч сделал аналогичное заявление относительно своего лямбда-исчисления, которое считают предшественником языков программирования. Тезис Чёрча – Тьюринга выдержал испытание временем, хотя сформулирован он был еще до изобретения современных компьютеров. Все, что поддается вычислению, вычислимо и на машине Тьюринга; по своим вычислительным возможностям она не уступит любому современному компьютеру, так что о ее чересчур примитивном устройстве можно не беспокоиться.

Рис. 5.1. Машина Тьюринга

Для понимания сути вычислительного процесса вам даже не нужно знать, что это за машина: достаточно взять любой язык программирования и представить, что у него есть доступ к неограниченному объему памяти. Все языки программирования функционально эквивалентны; все, что может быть запрограммировано, вычислимо и на «простенькой» машине Тьюринга.

В том же 1936 году Тьюринг доказал, что не всякую задачу можно решить на его абстрактной машине. Наиболее известный пример – проблема останова: не существует такой вычислительной машины, которая бы по коду программы определяла, остановится она или будет работать бесконечно.

Во время Второй мировой войны Алан Тьюринг был одним из главных «дешифраторов» Великобритании. В послевоенные годы он задался вопросом, можно ли на его машине сымитировать работу человеческого мозга. Ученый разработал тест, призванный определить, способна ли машина рассуждать «по-человечески»; впоследствии этот тест назвали в его честь. Представьте, что вы переписываетесь с кем-то через систему обмена сообщениями. Вы уверены, что вам отвечает человек? А вдруг это просто компьютерная программа? Программа, сумевшая обмануть большинство собеседников, проходит тест Тьюринга.

К несчастью, исследовательская деятельность Тьюринга прервалась очень рано. В 1952 году он был осужден за гомосексуализм, который в те годы считался в Великобритании противозаконным. Случившееся в конечном итоге привело к тому, что в 1954 году Тьюринг покончил жизнь самоубийством. Лишь в 2009-м британское правительство принесло официальные извинения.

За неоценимый вклад, внесенный ученым в развитие информатики и искусственного интеллекта, Ассоциация вычислительной техники назвала в его честь свою главную награду – «компьютерный» аналог Нобелевской премии. Среди ученых, о которых речь пойдет дальше, многие являются лауреатами премии Тьюринга.

Вычислительная сложность

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

В 1943 году нейропсихологи Уоррен Маккаллок и Уолтер Питтс разработали нейронную сеть – теоретическую модель, описывающую деятельность человеческого мозга. В пятидесятых годах математик и логик Стивен Клини изобрел конечный автомат – частный случай машины Тьюринга – и изучал свойства разрешимых на нем задач. При помощи конечных автоматов удобно описывать алгоритмы работы простейших агрегатов (к примеру, автомата с газировкой), однако что-то более сложное они уже не потянут.

Примерно в тот же период, в пятидесятых годах, лингвист Ноам Хомский исследовал механизмы построения предложений в английском и некоторых других языках. Он сформулировал понятие контекстно-свободной грамматики, в которой предложениям ставились в соответствие схемы, называемые «деревьями разбора». На рисунке ниже представлено дерево разбора для английского предложения The quick brown fox jumped over the lazy dog.

Рис. 5.2. Дерево разбора

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

Как выяснилось, такие грамматики прекрасно подходят для описания языков программирования и разметки (XML), а вот интуитивное понятие эффективных вычислений им уже не по зубам (как и конечным автоматам).

В последующие годы было создано множество вычислительных моделей, однако настоящий прорыв совершили в 1962 году Юрис Хартманис и Ричард Стернс, работавшие в то время в Исследовательской лаборатории General Electric в Скенектади, штат Нью-Йорк. Для оценки качества работы программы ученые предлагали смотреть, как меняются время ее выполнения и объем задействованной памяти при увеличении объема входных данных. Блестящая идея! В 1965 году вышла их совместная статья «О вычислительной сложности алгоритмов», заложившая основы нового раздела математики – теории сложности вычислений. В 1993 году Хартманис и Стернс получили за эту работу премию Тьюринга.

В 1960-х теория вычислительной сложности развивалась сразу в двух направлениях. Приверженцы одного выбирали конкретные вычислительные модели, ограничивали время исполнения и доступный объем памяти и пытались определить, какие задачи могут быть решены при таких условиях, а какие – не могут. Мануэль Блюм, работая над диссертацией в Массачусетском технологическом институте, использовал иной – совершенно абстрактный – подход, не зависящий ни от вычислительной модели, ни от времени и памяти и каких-либо других ресурсов. Ни один из вариантов не приблизил ученых к понятию вычислительной эффективности.

Классы P и NP

В середине 1960-х формальное определение эффективного алгоритма появилось сразу в двух работах: «Пути, деревья и цветы» Джека Эдмондса и «Внутренняя вычислительная трудность функций» Алана Кобэма.

Работа Эдмондса получила широкую известность благодаря тому, что в ней впервые был предложен эффективный алгоритм для задачи о числе паросочетаний, рассмотренной нами в третьей главе. В главе под названием «Отступление» ученый рассуждает об экспоненциальной и алгебраической сложности, предостерегая в то же время от использования слишком жестких критериев эффективности.

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

Кобэм в своей работе независимо от Эдмондса вводит тот же класс задач и приводит аналогичные рассуждения о пользе четкого определения.

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

Понятие класса P, так же как и понятие вычислимости, не зависит от конкретной вычислительной модели.

Кобэм тоже считает своим долгом предупредить:

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

В 1971 году Стивен Кук сформулировал понятие класса NP (задачи, решение которых можно эффективно проверить), а также поставил вопрос о равенстве P и NP и нашел первую NP-полную задачу. Годом позже Ричард Карп доказал NP-полноту для целого ряда известных математических проблем.

Выступление Карпа стало самым знаменательным событием на Конференции по вопросам сложности вычислений, проведенной в 1972 году Исследовательским центром IBM имени Томаса Дж. Уотсона. Будущее нового направления активно обсуждалось на итоговом заседании организаторской комиссии. Одной из главных тем был вопрос о том, как из горстки разрозненных результатов – нескольких алгоритмов и нижних оценок сложности – построить единую теорию. Участники заседания, среди которых был и Ричард Карп, вряд ли отдавали себе отчет, что ответ на этот вопрос находится у них перед глазами – в работах Кука и самого Карпа, описывающих классы P и NP, понятие сводимости, а также свойство, которое позже назовут NP-полнотой.

Карп прекрасно понимал, что новой области науки требуется хорошее название:

В конце концов победило название «вычислительная сложность». Вопрос о равенстве P и NP приобрел огромное значение и быстро затмил все остальные направления исследований в данной области. Абстрактная теория сложности отошла на второй план; даже Блюм переключился на криптографию и верификацию программ. В 1995 году ученый получил премию Тьюринга за свою активную исследовательскую деятельность в 1960–1980-х годах. Когда много лет спустя его спросили, почему он все-таки решил сменить направление, Блюм ответил: «Потому что Кук был прав».

В СССР проблемами теоретической кибернетики занимались многие выдающиеся ученые. Мы подробно остановимся на трех из них; все они являются представителями различных подходов к методу перебора.

1. Сергей Всеволодович Яблонский первым применил перебор для поиска минимальных схем, реализующих дискретные функции. К сожалению, его самонадеянность в сочетании с огромным влиянием, которое он приобрел в научной среде, тормозили развитие теории вычислительной сложности.

2. Андрей Николаевич Колмогоров – крупнейший ученый в истории русской науки – предложил в качестве меры сложности алгоритмическую информацию.

3. Ученик Колмогорова Леонид Анатольевич Левин независимо от Кука сформулировал проблему равенства классов P и NP и пришел к понятию NP-полноты. На родине защитить диссертацию он не смог по политическим причинам.

Сергей Всеволодович Яблонский

В Советском Союзе исследования в области теории вычислений проводились в рамках теоретической кибернетики. Активное развитие этой области началось в 1950-х годах, когда электронные вычислительные машины были взяты на вооружение военными. Сергей Яблонский родился в 1924 году в Москве. Вернувшись с фронта после окончания Второй мировой войны, он продолжил изучать математику в Московском государственном университете. В 1953 году Яблонский защитил кандидатскую диссертацию под руководством Петра Сергеевича Новикова, который одним из первых в СССР начал заниматься проблемами вычислимости. Вместе с Алексеем Андреевичем Ляпуновым, также работавшим под руководством Новикова, Яблонский проводил в МГУ семинары по вопросам реализации булевых функций. Яблонский и Ляпунов организовывали и направляли всю исследовательскую деятельность в области теории вычислений.

Проблема выполнимости, упомянутая в четвертой главе, касается логических формул, т. е. формул, в которых основными операциями являются «И», «ИЛИ» и «НЕ». На самом деле любой вычислительный процесс можно представить в виде набора таких операций, или, другими словами, в виде схемы из элементов «И», «ИЛИ» и «НЕ». Одни задачи решаются схемами небольшого размера, для других необходимо огромное число элементов. Возникает понятие схемной сложности, и в начале пятидесятых Яблонский этим понятием заинтересовался.

Основатель теории информации – американский ученый Клод Шеннон – доказал, что некоторые логические функции имеют чрезвычайно высокую схемную сложность. Яблонский решил исследовать сложность построения таких функций. Хоть это и не очевидно, но если P и NP окажутся не равны, отсюда будет следовать, что некоторые легко формулируемые поисковые задачи нельзя решить при помощи маленьких схем.

Из результатов Шеннона вытекало, что сложность логических функций, заданных случайным образом, почти всегда близка к максимальной. Яблонский первым обратил внимание на этот факт и начал заниматься вопросом поиска сложных логических функций без использования случайных величин. Возникала ли при этом необходимость полного перебора всех функций? Ученый показал, что во время построения последовательности функций, имеющих сложную схемную реализацию, обязательно будут строиться и все остальные функции. Отсюда, в частности, следовало, что всякий метод построения некоторой сложной функции можно преобразовать таким образом, чтобы он строил любую другую функцию. Из того факта, что при построении сложных функций строятся также и все остальные, Яблонский сделал вывод о необходимости перебора. В 1959 году вышла его работа «О невозможности элиминации перебора всех функций из P₂ при решении некоторых задач теории схем».

Важность результатов Яблонского сложно переоценить; и все же интерпретировал он их не совсем верно. Ведь если при построении сложной функции можно получить и любую другую, то это еще не означает, что строить все остальные функции необходимо и другим способом сложную функцию никак не найти. На самом деле в работе Яблонского мало что говорилось о вычислительной сложности поиска самых сложных функций. Годом позже ученик Яблонского Юрий Иванович Журавлёв опубликовал статью с не менее впечатляющим названием – «О невозможности построения минимальных дизъюнктивных нормальных форм функций алгебры логики в одном классе алгоритмов», в которой тема вычислительной сложности также не затрагивалась. По сути ни та ни другая работа не касалась вопросов, связанных с проблемой равенства P и NP.

Советский Союз был социалистической страной с централизованной системой управления экономикой. В науке применялся аналогичный подход, и математические исследования находились под контролем различных комиссий, в которых Яблонский играл далеко не последнюю роль. Ученый полагал, что проблема перебора уже достаточно изучена в его собственной работе, и потому не приветствовал дальнейшие исследования в этом направлении, особенно если дело касалось вычислительной сложности и поиска алгоритмов. Далее мы увидим, что в результате такого подхода в шестидесятые годы в математическом сообществе случился раскол.

Андрей Николаевич Колмогоров

Андрей Колмогоров родился в 1903 году в Тамбове. В 1920 году он поступил в Московский университет, где поначалу интересовался не только математикой, но и пробовал свои силы и в истории, занимаясь изучением налогообложения на Руси в Средние века. Вопрос в его работе ставился такой: назначался ли налог сразу целому селению или же складывался из налогов, назначенных отдельных дворам? Проанализировав старинные налоговые записи, Колмогоров показал: расшифровать эти записи и объяснить правило, по которому они составлялись, будет гораздо проще в предположении, что налог назначался селению. На историческом отделении работу студента оценили очень высоко. Однако в ответ на вопрос, следует ли ему опубликовать полученные результаты, Колмогоров услышал: «У вашей гипотезы есть лишь одно обоснование. А для публикации требуется как минимум два», что в конечном итоге заставило его отвернуться от истории и посвятить себя науке, в которой одного доказательства было вполне достаточно. Колмогоров внес неоценимый вклад в самые разные области математики; это величайший математик XX века и один из крупнейших ученых в истории всей российской и мировой науки.

Существует забавная история – анекдот, по всей видимости, – о том, как Колмогоров спас теорию вероятностей от сталинского режима.

В тридцатых годах Сталин стремился укрепить свою власть. Все достижения науки и искусства, представлявшие потенциальную угрозу режиму, безжалостно уничтожались. Биологией заправляла группа псевдоученых, «приближенных к императору». В 1937 году очень многие генетики были арестованы как троцкисты и агенты фашистской разведки. В последующие десятилетия советская генетика – некогда предмет настоящей гордости – почти полностью прекратила свое существование.

Разобравшись с генетикой, «светочи науки» ополчились на теорию вероятностей за понятие независимых событий. Теория вероятностей занимается изучением шансов на тот или иной исход; к примеру, если одновременно бросить две игральные кости, то вероятность того, что в сумме выпадет пять очков, равняется одной девятой. Через понятие вероятности определяются и независимые события. Например, при подкидывании двух игральных костей число выпавших очков на одной никак не зависит от числа выпавших очков на другой. Все это плохо согласовывалось с марксистской философией, согласно которой все кругом взаимосвязано и взаимообусловлено.

Колмогорова вызвали наверх и упрекнули в том, что независимые события идут вразрез с идеями марксизма.

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

«Допустим, поп во время засухи молится о ниспослании дождя, – продолжал ученый. – На следующий день начинается дождь. Эти два события совершенно независимы». Что тут можно было возразить? Допустить даже самую отдаленную связь значило признать действенность религии, что было равносильно попытке дискредитировать учение Маркса. Так Колмогоров спас теорию вероятностей.

Рис. 5.3. Комикс про Дилберта. © Скотт Адамс, 2001. Публикуется с разрешения UNIVERSAL UCLICK. Все права защищены

Стремление проникнуть в суть вероятности и случайности привело Колмогорова к одной удивительно простой и в то же время гениальной идее. Рассмотрим три последовательности цифр:

• 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999;

707 106 781 186 547 524 400 844 362 104 849 039 284 835 937 688 474;

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

Одну из них мне выдал генератор случайных чисел, а остальные были получены другими способами. Все три последовательности абсолютно равновероятны: нет никаких причин, по которым одна была бы «менее случайна», чем другая. Прежде чем читать дальше, попробуйте догадаться, какая из них – творение генератора.

Выдавать одни девятки для генератора случайных чисел не очень-то естественно. Вторая последовательность, – как некоторые уже, наверно, догадались, – это начало дробной части квадратного корня из 1/2. А вот третья действительно была создана генератором.

Колмогоров придумал определять степень случайности последовательности в зависимости от длины ее самого короткого описания. Первая последовательность – это «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-полноты со временем стали называть теоремой Кука–Левина – правда, произошло это уже ближе к девяностым.

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

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