Читать «Золотой билет» онлайн - страница 36
Лэнс Фотноу
На самом деле к проблеме выполнимости, или SAT (от англ.
Сама проблема SAT также принадлежит NP, поскольку для любого набора входных переменных истинность логического выражения проверяется относительно быстро. В классе NP эта задача является универсальной или, как еще говорят, самой трудной, или NP-полной. Доказать наличие эффективного алгоритма для ее решения значит доказать равенство P и NP.
Симпозиум проходил в городке Шейкер-Хайтс в штате Огайо, в отеле
«Полученные результаты дают нам основания полагать, что проблема выполнимости – задача чрезвычайно любопытная, поскольку она, по всей видимости, не имеет эффективных методов решения. Думаю, стоит попытаться доказать данную гипотезу: в теории сложности это стало бы величайшим прорывом».
С того дня и ведет свою историю проблема равенства P и NP.
Двадцать плюс одна
Работу Кука оценили, однако ажиотаж вокруг нее поднялся не сразу. В те годы проблема выполнимости интересовала немногих, и никто еще толком не понимал смысл класса NP. Кук даже не придумал ему названия и пользовался выражением «недетерминированное полиномиальное время». Все изменилось, когда вслед за Куком свою работу опубликовал профессор Ричард Карп из Калифорнийского университета в Беркли.
Ознакомившись с результатами Кука, Карп понял, как можно свести проблему выполнимости к задаче о клике. Он разработал несложный метод преобразования логического выражения в схему, похожую на схему дружеских связей, при котором выражение оказывалось выполнимым в том и только в том случае, когда в схеме существовала клика определенного размера. Отсюда следовало, что любой алгоритм решения задачи о клике заодно решает и проблему выполнимости. Кук доказал, что проблема выполнимости является самой трудной в NP; в работе Карпа было показано, что задача о клике не проще и потому тоже является самой трудной. Появление эффективного алгоритма для задачи о клике будет означать, что любую задачу из NP можно решить быстро, и докажет равенство классов P и NP.
Кук свел задачу о клике к проблеме выполнимости, Карп совершил обратный процесс, и в результате оказалось, что с вычислительной точки зрения эти две совершенно непохожие задачи эквивалентны. Проблему выполнимости можно решить быстро тогда и только тогда, когда быстро решается задача о клике, или – что то же самое – когда P равно NP.