n-значных двоичных чисел, то экспоненциальное время уйдет не только на то, чтобы их распечатать, но и на то, чтобы их прочесть, и еще больше времени — на то, чтобы проверить список. Это потребовало бы громадных корректорских усилий. Класс P определенно входит составной частью в класс NP. Если ответ можно найти за полиномиальное время, да еще с гарантией его корректности, то это будет означать, что вы его уже проверили. Так что проверка автоматически может быть произведена за полиномиальное время. Если бы кто-то представил вам предполагаемый ответ, то вы могли бы просто прогнать весь алгоритм еще раз — это и стало бы проверкой.
Теперь мы можем сформулировать задачу тысячелетия. Превосходит ли класс NP по размеру класс P или они суть одно и то же? Или короче: равен ли класс P классу NP?
Если ответ «да», то это значит, что существует принципиальная возможность отыскать быстрые и эффективные алгоритмы для автоматического составления расписаний авиарейсов, оптимизации работы завода, выполнения миллиона других важных практических задач. Если ответ «нет», то у нас будет железная гарантия того, что все вроде бы сложные задачи на самом деле сложны, и мы сможем остановиться и не тратить больше времени на поиск быстрых алгоритмов для них. В том и другом случае мы выигрываем. А вот не знать, как в реальности обстоят дела, очень неприятно.
Математикам было бы гораздо легче жить, если бы ответ был «да», поэтому пессимист, живущий в каждом человеческом существе, не может не заподозрить, что на самом деле все не так просто и ответ, скорее всего, окажется «нет». В противном случае мы все получаем бесплатный бонус, который ничем не заработали и которого не заслуживаем. Я, правда, подозреваю, что большинство математиков предпочло бы, чтобы ответ оказался «нет», потому что в этом случае им была бы гарантирована работа до конца времен. Математики самоутверждаются, решая сложные задачи. В общем, по разным причинам большинство математиков и компьютерщиков ожидают, что ответ на вопрос «Совпадает ли P с NP?» будет «Нет». И мало кто ждет, что ответом на самом деле окажется «да».
Помимо этого, возможны еще два варианта. Не исключено, что можно доказать эквивалентность P и NP, не находя в реальности полиномиальных алгоритмов для каждой конкретной NP-задачи. Математике свойственно предлагать нам неконструктивные доказательства существования: они утверждают, что нечто существует, но не говорят, что оно собой представляет и как его найти. В качестве примеров можно назвать методы проверки на простоту, которые бодро сообщают нам, что данное число не является простым, но не называют ни одного конкретного делителя, или теоремы теории чисел, уверяющие нас, что решения некоего диофантова уравнения ограничены, т. е. не превосходят некоторого предела, но не называющие никакого конкретного ограничения. В конце концов, полиномиальный алгоритм может быть настолько сложным, что записать его, в принципе, невозможно. Тогда естественный пессимизм в отношении бесплатного сыра окажется оправдан даже при положительном ответе на вопрос.
Некоторые исследователи высказываются еще более резко: они считают, что вопрос может оказаться нерешаемым в рамках современной математики, ограниченной формальной логикой. Если так, то невозможно доказать ни да ни нет. Не потому, что мы слишком глупы, чтобы найти доказательство, а потому, что такового не существует. Эта идея появилась на свет в 1931 г., когда Курт Гедель выпустил кошку противоречивости охотиться в стаю философских голубей, населявших подвалы математики (он доказал, что некоторые заявления в арифметике неразрешимы). В 1936 г. Алан Тьюринг нашел неразрешимую задачу попроще — задачу об остановке машины Тьюринга. Всегда ли при заданном алгоритме существует доказательство либо того, что машина остановится, либо того, что она будет считать вечно? Как ни удивительно, ответ Тьюринга был «нет». Для некоторых алгоритмов не существует доказательства ни того ни другого. Не исключено, что задача P/NP окажется такой же. Это объяснило бы, почему никто не может ни доказать, ни опровергнуть соответствующее утверждение. Но никто не может также доказать или опровергнуть утверждение о том, что задача P/NP неразрешима. Может быть, ее неразрешимость сама по себе неразрешима…
Самый очевидный подход к задаче P/NP состоит в том, чтобы выбрать какую-нибудь задачу, о которой известно, что она относится к классу NP, предположить существование полиномиального алгоритма ее решения — и каким-то образом прийти к противоречию. Некоторое время математики пытались применить эту методику к различным задачам, но в 1971 г. Стивен Кук понял, что выбор задачи часто не играет никакой роли. С определенной точки зрения все подобные задачи — с точностью до некоторых технических особенностей — совершенно равноправны. Кук ввел понятие NP-полной задачи. Такая NP-задача обладает следующим свойством: если для ее решения существует алгоритм класса P, то любая NP-задача может быть решена при помощи алгоритма класса P.
Кук нашел несколько NP-полных задач, включая SAT — задачу о выполнимости булевых формул. В ней спрашивается, можно ли сделать заданное логическое выражение истинным при помощи подходящего выбора значений (истинности или ложности) его переменных. Кроме того, он получил более глубокий результат: задача SAT с дополнительными ограничениями (3-SAT) также является NP-полной. Здесь логическая формула должна быть записана в виде «A, или B, или C, или… или Z», где A, B, C…Z — логические формулы, содержащие по три переменные. Спешу добавить, что переменные не обязаны каждый раз быть одними и теми же. Большинство доказательств того, что та или иная задача является NP-полной, восходят к теореме Кука о 3-SAT.
Определение Кука подразумевает, что все NP-полные задачи существуют на равных основаниях. Доказать, что одна из них на самом деле относится к классу P, означает доказать, что к классу P относятся все такие задачи. Это открывает некоторые тактические возможности: может оказаться, что с некоторыми NP-полными задачами работать проще, чем с остальными. Но стратегически это означает, что с тем же успехом можно выбрать любую конкретную NP-полную задачу и работать именно с ней. Все NP-полные задачи ведут себя одинаково, и поэтому на любой из них можно моделировать все остальные. А любую NP-задачу можно конвертировать в частный случай NP-полной задачи при помощи процедуры «шифрования» — с использованием шифра, на применение которого требуется полиномиальное время.
Чтобы представить себе характер этой процедуры, рассмотрим типичную NP-полную задачу: поиск гамильтонова цикла в сети. Требуется найти замкнутый маршрут по ребрам сети, которые прошел бы через каждый узел (т. е. через каждую точку) ровно один раз. «Замкнутый» означает, что в конце концов маршрут возвращается в начальную точку. Размер входных данных здесь — это число ребер, меньшее или равное квадрату числа точек, поскольку каждое ребро соединяет две точки. (Считаем, что любую заданную пару соединяет не больше одного ребра.) Нам не известно ни одного алгоритма класса P, который решал бы эту задачу, но предположим — гипотетически, — что такой алгоритм существует. Теперь выберем какую-нибудь другую задачу и назовем ее задачей X. Пусть задача X может быть переформулирована в терминах поиска такого маршрута в некоей сети, связанной с задачей X. Если метод перевода данных задачи X в данные об этой сети и наоборот, может быть применен за полиномиальное время, то мы автоматически получаем алгоритм класса P для задачи X. Примерно так:
1. Переводим задачу X в задачу поиска гамильтонова цикла в связанной с задачей сети. Это можно сделать за полиномиальное время.
2. Находим такой цикл за полиномиальное время при помощи того самого гипотетического алгоритма для задачи с сетью.
3. Переводим полученный гамильтонов цикл обратно в решение задачи X, что опять же можно проделать за полиномиальное время.
Поскольку все три полиномиальных шага вместе можно проделать тоже за полиномиальное время, этот алгоритм относится к классу P.
Чтобы показать, как это работает, я рассмотрю менее амбициозную версию задачи о поиске гамильтонова цикла, где искомый маршрут не обязан быть замкнутым. В таком виде она называется задачей о поиске гамильтонова пути. Сеть может иметь гамильтонов путь и при этом не иметь цикла (см. пример на рис. 42 слева). Так что решение задачи о поиске гамильтонова цикла может не означать решения задачи о поиске гамильтонова пути. Однако задачу о поиске гамильтонова пути можно переформулировать в задачу о поиске гамильтонова цикла на близкой, но несколько иной сети. Для этого в сеть добавляется одна дополнительная точка, соединенная со всеми точками первоначальной сети, как на рис. 42 справа. Любой гамильтонов цикл в новой сети может быть превращен в гамильтонов путь: для этого достаточно исключить из него добавленный узел и два подходящих к нему ребра цикла. И наоборот, любой гамильтонов путь в первоначальной сети дает цикл в новой: достаточно просто соединить два конца пути с новой точкой. Это «превращение» задачи о поиске пути в задачу о поиске цикла вводит в сеть всего одну новую точку и по одному ребру на каждую точку первоначальной сети, так что эта процедура — и обратная ей тоже — выполняется за полиномиальное время.
Конечно, я здесь всего лишь зашифровал одну конкретную задачу, превратив ее в задачу о поиске гамильтонова цикла. Чтобы доказать, что такая задача является NP-полной, нам нужно проделать то же самое с любой NP-задачей. Это реально: первое доказательство нашел Ричард Карп в 1972 г. в знаменитой статье, где доказывалась NP-полнота 21 различной задачи.
Задача о коммивояжере является «почти» NP-полной, но здесь есть одна техническая сложность: мы не знаем, относится ли она к классу NP. Известно более 300 конкретных NP-полных задач в различных областях математики, включая логику, теорию графов, комбинаторику и оптимизацию. Доказать, что любая из них может (или не может) быть решена за полиномиальное время, означало бы доказать то же для всех них без исключения. Несмотря на богатство выбора, задача P/NP по-прежнему остается открытой. И я бы не удивился, если бы узнал, что она останется таковой и 100 лет спустя.