Лэнс Фотноу - Золотой билет

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

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

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

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

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

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

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

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

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

Ошибочно было бы полагать, что рассмотренные Карпом задачи надуманы и интересуют только математиков: большинство из них очень даже практические.

Возьмем, к примеру, компанию Coca-Cola . Под этой маркой производится более трех тысяч напитков по всему миру. Установка для розлива напитков способна выдавать сотни различных продуктов. В ее состав входит несколько разливочных машин, каждая из которых выполняет определенную последовательность операций, чтобы смешать ингредиенты. Одна машина может приготовить множество различных напитков. Задача установки – скоординировать работу всех разливочных машин и добиться наивысшей производительности, выдавая максимальное число напитков за минимальное время, т. е. решить проблему распределения подзадач, которая тоже входит в список Карпа и является самой трудной в NP.

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

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

Однодневная экскурсия по «Волшебному Королевству» для взрослых включает посещение 21 аттракциона. Обходить их можно разными способами; всего существует… 51090942171709440000 вариантов! Удивительно, правда? Пятьдесят один миллиард миллиардов – это примерно в шесть раз больше, чем количество песчинок на планете. А если задачу немного усложнить и начать учитывать очередь по записи, посещение ресторанов и шоу, вариантов будет еще больше.

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

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