Книга: Золотой билет

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

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

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

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

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

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

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

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

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

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

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

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

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

Каждый год Ассоциация вычислительной техники вручает премию Тьюринга – «компьютерный» аналог Нобелевской премии, названый в честь Алана Тьюринга, который заложил основы теоретической информатики еще в 30-х годах XX века. В 1982 году за формулировку проблемы равенства P и NP премию получил Стивен Кук. Однако P и NP явно требовали большего, и в 1985 году Ричарда Карпа наградили за вклад в теорию алгоритмов, и в особенности – за список NP-полных задач.

Оглавление книги