Золотой билет - Лэнс Фотноу

Позже Разборов в соавторстве со Стивеном Рудичем из Университета Карнеги-Меллон разработал понятие «естественного доказательства», охватывавшее широкий спектр методов, применяемых для оценки сложности схем. Ученые показали, что при помощи естественных доказательств проблему равенства 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. Не в том смысле, что для этого требуется огромная подготовительная работа; просто мы уже испробовали все мыслимые и немыслимые подходы и исчерпали все известные науке методы доказательства, так что в ближайшем будущем прогресса ждать не приходится.