Золотой билет. P, NP и границы возможного - Лэнс Фортноу Страница 32

Вернемся к схемам для поиска клики, которые мы только что построили. Заметьте, что в них нет ни одного вентиля «НЕ». Вообще-то некоторые схемы реализовать без отрицания нельзя: оно необходимо даже для такой простой операции, как «исключающее ИЛИ». А вот в задаче о клике можно обойтись одними только «И» и «ИЛИ» – правда, размер подобных схем будет просто устрашающий.

В 1985 году Александр Разборов – студент Математического института им. В. А. Стеклова в Москве – доказал, что любая схема, реализующая алгоритм для задачи о клике при помощи одних лишь вентилей «И» и «ИЛИ» (т. е. без использования «НЕ»), обязательно содержит огромное число элементов. Конечно, проблему равенства P и NP это не снимало; использование элемента «НЕ» вполне могло бы привести к значительному сокращению размера схемы, хотя для задачи о клике он совсем не обязателен.

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

В Соединенные Штаты ранние работы Разборова попали непереведенными. Сипсер привлек к делу несколько русских студентов; вместе они в ожидании чуда скрупулезно переводили текст на английский и с каждой следующей статьей надеялись, что вопрос о равенстве P и NP вот-вот будет закрыт. Авторству Разборова принадлежит целый ряд замечательных работ, однако ключ к доказательству неравенства P и NP они не дают.

В третьей главе мы разбирали задачу о числе паросочетаний и составляли из дружеских пар романтические. Как и в случае с кликой, для решения задачи о паросочетаниях можно строить схемы, содержащие только операции «И» и «ИЛИ». Для оценки общего числа элементов подходят те же методы, что были использованы в задаче о клике. Поэтому схемы, решающие задачу о паросочетаниях при помощи одних лишь «И» и «ИЛИ», всегда содержат огромное число элементов.

Впрочем, для паросочетаний, в отличие от клики, эффективные алгоритмы все же существуют, а значит, существуют и небольшие схемы из элементов «И», «ИЛИ» и «НЕ». Конечно, отрицание использовать совсем не обязательно, однако с его помощью число элементов схемы можно значительно уменьшить. Простой и скромный вентиль «НЕ» на самом деле гораздо мощнее, чем кажется.

Все это практически сводит на нет любые попытки разобраться с классами P и NP, основываясь на результатах Разборова относительно клики. Если для решения некоторой задачи при помощи одних лишь «И» и «ИЛИ» требуется схема из огромного числа элементов, то отсюда вовсе не следует, что при добавлении «НЕ» ситуация останется прежней. В более поздних работах Разборов этот вопрос прояснил; он четко показал, почему для схем с отрицанием его методы не годятся, и почему их почти наверняка невозможно будет переделать.

Позже Разборов в соавторстве со Стивеном Рудичем из Университета Карнеги-Меллон разработал понятие «естественного доказательства», охватывавшее широкий спектр методов, применяемых для оценки сложности схем. Ученые показали, что при помощи естественных доказательств проблему равенства P и NP решить невозможно.

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