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

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