На Западе.

Поиск эффективных алгоритмов начался около 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-х годах. Когда много лет спустя его спросили, почему он все-таки решил сменить направление, Блюм ответил: «Потому что Кук был прав».