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

Допустим, Алекс, Кэти и Эрик принадлежат сообществу, а Барбара и Дэвид – нет; тогда наше выражение истинно, так как в каждом условии «ИЛИ» упоминается кто-то, кто в «Альфу» не входит. Теперь предположим, что сообществу принадлежат Алекс, Дэвид и Эрик. Тогда условие (Алекс не в «Альфе» ИЛИ Дэвид не в «Альфе») не выполняется, поскольку и Алекс, и Дэвид входят в сообщество, а значит – ложно и все выражение.

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

Аналогичную конструкцию можно составить и для всех 20 тысяч жителей Королевства. В результате получится огромное, содержащее несколько миллионов символов выражение – впрочем, не настолько длинное, чтобы не уместиться в компьютер. Для краткости обозначим его буквой Φ. Очевидно, что Φ будет истинно только тогда, когда «альфовцы» в самом деле образуют клику.

Через Ψ50 обозначим выражение, истинное в том случае, если в «Альфу» входят хотя бы 50 человек. Не будем углубляться в его структуру; достаточно будет сказать, что построить его можно тем же способом, каким первые цифровые компьютеры выполняли сложение чисел.

Соединим наши выражения в одно: (Ψ50 И Φ). Если члены сообщества образуют клику размером не меньше 50, то новое выражение примет значение «истина», и наоборот – если выражение истинно, то члены сообщества образуют клику размером не меньше 50.

Логическое выражение, проверяющее принадлежность к сообществу, называется выполнимым, если сообщество можно составить таким образом, что выражение примет значение «истина». Выражение (Ψ50 И Φ) выполнимо, когда в сообществе есть клика размера не меньше 50.

Предположим, у нас есть быстрый алгоритм, проверяющий выполнимость логического выражения. Подадим ему на вход выражение (Ψ50 И Φ); если алгоритм ответит «да», то в Королевстве существует клика размера 50, а если «нет» – то не существует. Таким образом, алгоритм решения задачи о выполнимости позволяет решить и задачу о клике.

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

На самом деле к проблеме выполнимости, или SAT (от англ. satisfiability – выполнимость), сводится не одна лишь задача о клике, но и другие задачи класса NP, которые мы обсуждали ранее, включая задачу о коммивояжере, поиск гамильтонова пути, построение максимального разреза и раскраску карт. Стивен Кук доказал, что любая проблема из NP сводится к проблеме выполнимости. Решите проблему выполнимости – и у вас будет ключ ко всем проблемам из NP. Появление эффективного алгоритма для задачи о выполнимости будет означать, что такой алгоритм существует для всех задач, решение которых легко проверяется, а следовательно, P = NP. Создайте эффективный алгоритм решения проблемы SAT – и получите миллион долларов от Института Клэя!

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

Симпозиум проходил в городке Шейкер-Хайтс в штате Огайо, в отеле Somerset Inn, принадлежащем компании Stouffer. Стивен Кук выступил с докладом 4 мая 1971 года.

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

С того дня и ведет свою историю проблема равенства P и NP.

Двадцать плюс одна

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