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

3 481 788 616 673 927 174 126 704 329 430 033 822 428 741 136 969 800 292 509 234 146 086 195 855 824 730 457 281 170 250 134 309 383 506 694 008 809 661 825 431 661 561 845 957 650 386 210 936 569 600

элементов «И».

Рис. 7.10. Схема для клики размера три

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

Существуют ли маленькие схемы для задачи о клике? Равны классы P и NP или не равны? Вопросы эти очень тесно взаимосвязаны, и ответа на них ученые пока не знают; однако сейчас уже мало кто верит, что задача о клике реализуется маленькой схемой, как, впрочем, и в то, что P = NP.

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

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

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

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

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

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

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

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