Глава 7. Как доказать, что P ≠ NP

Юрис Хартманис, один из основоположников теории вычислительной сложности, любит повторять: «Все знают, что они не равны, а доказать не могут».

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

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

Последующие десятилетия ознаменовались невероятными успехами в математике и кибернетике; удалось разрешить даже одну из самых знаменитых математических проблем – Великую теорему Ферма.

В 1637 году француз Пьер де Ферма, математик-любитель и юрист по профессии, сделал на полях своей древнегреческой «Арифметики» следующее замечание:

«Невозможно разложить куб на два куба, биквадрат на два биквадрата и вообще никакую степень, большую квадрата, на две степени с тем же показателем. Я нашел этому поистине чудесное доказательство, но поля книги слишком узки для него».


Рис. 7.1. Комикс про Дилберта. © Скотт Адамс, 1997. Публикуется с разрешения UNIVERSAL UCLICK. Все права защищены


Другими словами, не существует таких натуральных чисел a, b, c и такого натурального n > 2, что an + bn = cn. Ученый больше нигде не упоминает об этом доказательстве; вполне возможно, что строгое математическое обоснование он так и не придумал. Постепенно теорема приобрела широкую известность и пополнила ряды классических «нерешаемых» математических задач. Знаменитую теорему мечтали доказать даже дети. Один из таких мечтателей (среди которых был и я), став взрослым, превратил мечту в реальность. В 1994 году Эндрю Уайлс из Принстонского университета представил доказательство, основанное на целом ряде работ по теории чисел, и в один миг стал знаменитым – насколько вообще бывают знаменитыми математики.

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

Парадокс лжеца

Давайте рассмотрим одно загадочное утверждение.


Рис. 7.2. Утверждение


Оно истинно или ложно, как вам кажется? Если оно ложно, значит, неверно то, что оно ложно, а значит, оно истинно. Но если оно истинно – значит, верно то, что оно ложно. С какой стороны ни зайди, получишь противоречие. Этот парадокс получил название «парадокс лжеца». Сейчас я лгу. Ну как – солгал я или нет?

В математике не бывает настоящих парадоксов: бывают лишь некомпетентные математики. Утверждение «Это утверждение ложно» некорректно с математической точки зрения, поскольку оно оценивает собственную истинность.

В 1930 году Курт Гёдель пришел к выводу, что о математических доказательствах можно рассуждать на языке самой математики и что высказывания о возможности доказательства того или иного утверждения также могут быть записаны в виде формальных математических утверждений. Ученый изобрел высказывание, которое говорит о возможности собственного доказательства, и сформулировал его на языке математики. Вот оно:


Рис. 7.3. Утверждение о возможности доказательства


Похоже на предыдущее, правда? Предположим, что оно ложно. Тогда его можно доказать, а следовательно, оно истинно. Но это противоречит первоначальному предположению о том, что оно ложно; значит, оно истинно.

Что, опять парадокс? Вообще-то нет: высказывание истинно, вот только это не докажешь. Так Гёдель одним махом пошатнул все фундаментальные основы математики: оказывается, некоторые истинные утверждения невозможно доказать[5]!

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

Примерно так же дело обстоит и с вычислениями. Вам наверняка приходилось любоваться песочными часами на экране монитора и гадать – завис компьютер или просто надолго задумался? Перегрузить его или еще подождать? Вот бы кто-нибудь придумал алгоритм, который бы определял, крутится компьютер в бесконечном цикле или нет! Было бы здорово – но, к сожалению, это опять невозможно, и сейчас мы с вами поймем, почему.

Начнем с простого наблюдения: программа – это набор данных. Такой же, как, к примеру, файл Word или Excel. Поэтому одна программа вполне может проанализировать код другой программы. Впервые подобная мысль была высказана Аланом Тьюрингом в его знаменитой работе 1936 года, заложившей основы теоретической информатики.

Любая компьютерная программа либо остановится и выдаст некий результат, либо будет работать бесконечно. Допустим, у нас есть алгоритм, который определяет, останавливается программа или нет. Применим его к самому себе и создадим программу, представленную на рисунке ниже.

Программа либо остановится, либо будет работать бесконечно. В любом случае мы придем к противоречию, а значит, наше допущение неверно, т. е. создать программу, которая бы для любой другой программы определяла, остановится она или нет, просто невозможно. Невозможно ни на стационарном компьютере, ни на ноутбуке. Невозможно ни сейчас, ни через сотню лет. Никто и никогда такую программу не напишет, потому что алгоритма, решающего проблему останова, просто-напросто не существует.


Рис. 7.4. Программа


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

Для начала определим алгоритм Q, который принимает на вход код программы R и решает следующую задачу:

• Если программа R, получив на вход свой собственный код, за полиномиальное время выдает ответ «Да», ответить «Нет».

• В противном случае ответить «Да».

Теперь возьмем произвольный эффективный алгоритм S. Очевидно, что Q(S) ответит «Да» в том и только в том случае, когда S(S) ответит «Нет», а это значит, что ни один эффективный алгоритм никогда не совпадет с алгоритмом Q.

Несмотря на это, алгоритм Q вполне корректный, и задача, которую он выполняет, разрешима, – вот только за полиномиальное время с ней не справиться.

Раз Q не принадлежит классу P, тогда, если бы мы доказали, что Q лежит в NP, т. е. любое заданное решение быстро проверяется, это означало бы, что P ≠ NP, и проблема тысячелетия была бы решена.

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

Схемы

В основе любого современного вычислительного устройства лежит интегральная схема.

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

Для начала рассмотрим один электрический провод, на который подается либо высокое напряжение, либо низкое. Возможны только два значения, интерпретируемые обычно как наличие тока или его отсутствие; эти значения кодируют два состояния – единицу и ноль, или «истину» и «ложь». Количество информации, передаваемое таким двузначным сигналом, получило название «бит» (англ. bit – сокращение от binary digit, т. е. «двоичная цифра»).


Рис. 7.5. Интегральная схема. Фото любезно предоставлено Пенсильванским университетом


Сам по себе провод – или даже несколько отдельных проводов – мало на что способны. Если мы хотим организовать какое-нибудь вычисление, то должны преобразовывать идущие по проводам сигналы. Простейший метод – инвертировать входное напряжение, т. е. реализовать логический вентиль «НЕ».


Рис. 7.6. Вентиль «НЕ»


Если на входе вентиля, т. е. слева от элемента «НЕ», будет высокое напряжение, на выходе оно станет низким, и наоборот.

Занимаясь каждым проводом в отдельности, полноценную схему не составить: на самом деле провода нужно специальным образом комбинировать. Вентиль «И» принимает на вход два или более сигнала и преобразует их в один; на выходе будет единица, если на все входы подается единица. Вентиль «ИЛИ» также принимает на вход два или более сигнала и преобразует их в один; на выходе будет единица, если хотя бы на один из входов подается единица.


Рис. 7.7. Вентили «И» и «ИЛИ»


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


Рис. 7.8. Вентиль «Исключающее ИЛИ»


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


Рис. 7.9. «И» с тремя входами


Чтобы узнать, есть ли в компании из пяти человек – Алекс, Боб, Венди, Гарри и Диана – клика размера три, мы можем построить схему, изображенную на рис. 7.10.

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

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 решить невозможно.

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

Как не доказать, что P ≠ NP

6 августа 2010 года сотрудник исследовательской лаборатории Hewlett-Packard Винэй Деолаликар разослал двадцати двум ведущим специалистам в области теоретической информатики препринт своей работы, лаконично озаглавленной «P ≠ NP». Многие мечтают прославиться и сорвать большой куш, т. е. миллион долларов от Математического института Клэя; то и дело из ниоткуда возникают люди с «доказательствами», заявляющие, что проблема решена и они установили, что P равно NP, или что P не равно NP, или что решить этот вопрос нельзя, или что он вообще не имеет смысла. Каждый год десятки подобных работ выкладывают в интернет, предлагают в научные журналы и рассылают по электронной почте известным ученым. В одно из самых престижных изданий по теоретической информатике – Journal of ACM – «доказательства» идут непрерывным потоком. Журнал даже разработал специальную политику для авторов:

«В редакцию регулярно поступают работы, авторы которых претендуют на решение известных открытых проблем теории сложности, в частности – проблемы равенства классов P и NP. Рассмотрение и рецензирование подобных работ осуществляется на добровольной основе и отнимает значительную часть редакционных ресурсов, поскольку требует проведения тщательного анализа на предмет выявления возможных ошибок. Редакция не исключает вероятность того, что проблема равенства P и NP, а также связанные с ней вопросы будут когда-нибудь решены; попытки доказательства таких проблем по-прежнему приветствуются. Тем не менее с целью избавления от дополнительной нагрузки, вызванной регулярной проверкой одних и тех же работ, которые после исправления выявленных в процессе рассмотрения ошибок направляются в редакцию повторно, для авторов устанавливаются следующие ограничения: рукописи по проблеме равенства P и NP и другим связанным с ней открытым проблемам теории сложности можно представлять в редакцию не чаще, чем раз в два года, – за исключением случаев, когда у автора имеется специальное разрешение от главного редактора. Данное правило касается также повторного предоставления ранее отклоненных рукописей».

По большей части представляемые доказательства абсолютно нечитабельны или пестрят глупейшими ошибками, и научное сообщество их просто-напросто игнорирует. Однако в случае с Деолаликаром дело приняло совсем другой оборот: у ученого уже имелся целый ряд научных публикаций, а качество представленной работы выгодно отличало его от других претендентов. Некоторые специалисты полагали, что труд Деолаликара заслуживает самого пристального рассмотрения. Из-за этого твиты и блоги запестрели преждевременными сообщениями о том, что проблема тысячелетия решена. Доказательство изучали известные математики и кибернетики; в результате всплыли как мелкие и средние недочеты, так и серьезные изъяны. Уже 16 августа – всего через десять дней после выхода препринта Деолаликара – газета New York Times опубликовала статью под названием Step 1: Post Elusive Proof. Step 2: Watch Fireworks, в которой описывалась вся эта история. К тому времени научное сообщество пришло к единому мнению: доказательство принять нельзя, поскольку в нем содержатся серьезные ошибки. Вопрос о равенстве P и NP по-прежнему оставался открытым.

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

Допустим, вы уверены, что решили проблему равенства P и NP, и уже потираете руки в предвкушении чека на миллион долларов от Математического института Клэя. Не спешите радоваться: с вероятностью 99,9 % доказательство окажется неверным. Попробуйте понять, что с ним не так; ищите ошибку – и ваши поиски почти наверняка увенчаются успехом.

Давайте разберем несколько типичных ошибок, встречающихся у тех, кто думает, что все доказал.

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

Ошибку Кардано в том или ином виде регулярно повторяют современные авторы, которым кажется, что они доказали неравенство P и NP. Давайте снова обратимся к задаче о клике. Любой алгоритм, утверждающий, что клику заданного размера найти невозможно, должен доказать, что ее действительно нет. Единственный способ в этом удостовериться – перебрать все возможные группы и проверить, не образуют ли они клику. Поскольку потенциальных вариантов слишком много, алгоритм не справится с проверкой за разумное время. Отсюда вытекает, что эффективных алгоритмов для задачи о клике не существует. Следовательно, P ≠ NP, ч. т. д. (что и требовалось доказать). Этим выражением (или аббревиатурой Q.E.D. – от латинского quod erat demonstrandum) математики часто завершают свои выкладки, подчеркивая тот факт, что доказательство окончено.

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

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

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

Текущее положение дел

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

Единственную на сегодняшний момент потенциальную возможность открыл Кетан Мулмулэй из Чикагского университета. Ученый показал, что решение некоторых трудных проблем из области математики под названием «алгебраическая геометрия» (и это не помесь школьной алгебры и геометрии, а нечто гораздо более сложное) может дать ключ к доказательству неравенства P и NP. Вот только для решения этих алгебраически-геометрических проблем потребуются такие техники, которых в нашем арсенале нет и которые в ближайшее время вряд ли появятся. Несколько лет назад Мулмулэй предположил, что реализация этого плана займет около ста лет. Теперь тот прогноз уже кажется ему чересчур оптимистичным.

Так сколько нам еще ждать? Не исключено, что сейчас, когда вы читаете эти строки, проблему уже решили. Хотя, скорее всего, над ней будут биться еще очень долго; дольше даже, чем над Великой теоремой Ферма, которая поддалась лишь через 357 лет. А может, она так навсегда и останется одной из величайших загадок в истории математики и вообще всей науки.

Загрузка...