Чтобы поставить вопрос разумным образом, необходимо исключить подобные тривиальные примеры. Для этого введем еще один класс алгоритмов, класс NP. Это не класс не-P — это класс алгоритмов, работа которых занимает недетерминированное полиномиальное время. В переводе с математического это означает, что, сколько бы времени ни требовалось алгоритму на поиск ответа, убедиться в верности этого ответа мы можем за полиномиальное время. Задача поиска ответа может быть сложной, но если ответ найден, то существует простой способ проверки его корректности.
Слово «недетерминированный» здесь используется потому, что существует возможность решить NP-задачу при помощи просто вдохновенной догадки. Сделав это, можно проверить и убедиться, что ответ действительно верен (или нет). К примеру, если задача заключается в разложении на простые множители числа 11 111 111 111, то вы можете предположить, что одним из множителей является простое число 21 649. Пока это всего лишь догадка, однако ее легко проверить: достаточно разделить исходное число на 21 649 и посмотреть, что получится. Частное равняется 513 239 точно, без остатка. Таким образом, ваша догадка оказалась верной. А если бы я догадался, что делителем должно быть 21 647 — тоже простое число, то деление привело бы к ответу 513 286 с остатком 9069. Таким образом, догадка оказалась бы неверной.
В данном случае правильное предположение можно сделать только чудом или при помощи обмана (я, кстати, прежде чем высказывать «предположение», разложил 11 111 111 111 на простые множители). Но, по существу, мы хотим именно этого. Если бы наша догадка не была чудесной, то можно было бы превратить алгоритм класса NP в алгоритм класса P очень простым способом: нужно было бы делать предположения одно за другим до тех пор, пока одно из них не оказалось бы верным. Мой пример позволяет увидеть, что так не получится: понадобилось бы слишком много попыток. В самом деле, то, что мы пытаемся делать, это всего лишь «пробное деление» на все возможные простые числа до тех пор, пока одно из них не сработает. Из главы 2 мы знаем, что это далеко не лучший способ искать делители.
Класс NP исключает глупые примеры вроде уже упоминавшегося очень длинного списка. Если кто-то в порыве вдохновения выдаст список всех 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.
