Читать «Золотой билет» онлайн - страница 71
Лэнс Фотноу
Все это практически сводит на нет любые попытки разобраться с классами P и NP, основываясь на результатах Разборова относительно клики. Если для решения некоторой задачи при помощи одних лишь «И» и «ИЛИ» требуется схема из огромного числа элементов, то отсюда вовсе не следует, что при добавлении «НЕ» ситуация останется прежней. В более поздних работах Разборов этот вопрос прояснил; он четко показал, почему для схем с отрицанием его методы не годятся, и почему их почти наверняка невозможно будет переделать.
Позже Разборов в соавторстве со Стивеном Рудичем из Университета Карнеги-Меллон разработал понятие «естественного доказательства», охватывавшее широкий спектр методов, применяемых для оценки сложности схем. Ученые показали, что при помощи естественных доказательств проблему равенства P и NP решить невозможно.
«Неестественные» методы доказательства могут основываться на парадоксах, подобных тем, что обсуждались выше. Разработка таких методов для схем уже принесла некоторые плоды, однако доказать, что для некоторой NP-полной задачи требуется большая схема (и решить тем самым вопрос о равенстве P и NP), вряд ли когда-нибудь получится; надежда на это постепенно угасает.
Как не доказать, что P ≠ NP
6 августа 2010 года сотрудник исследовательской лаборатории
«В редакцию регулярно поступают работы, авторы которых претендуют на решение известных открытых проблем теории сложности, в частности – проблемы равенства классов P и NP. Рассмотрение и рецензирование подобных работ осуществляется на добровольной основе и отнимает значительную часть редакционных ресурсов, поскольку требует проведения тщательного анализа на предмет выявления возможных ошибок. Редакция не исключает вероятность того, что проблема равенства P и NP, а также связанные с ней вопросы будут когда-нибудь решены; попытки доказательства таких проблем по-прежнему приветствуются. Тем не менее с целью избавления от дополнительной нагрузки, вызванной регулярной проверкой одних и тех же работ, которые после исправления выявленных в процессе рассмотрения ошибок направляются в редакцию повторно, для авторов устанавливаются следующие ограничения: рукописи по проблеме равенства P и NP и другим связанным с ней открытым проблемам теории сложности можно представлять в редакцию не чаще, чем раз в два года, – за исключением случаев, когда у автора имеется специальное разрешение от главного редактора. Данное правило касается также повторного предоставления ранее отклоненных рукописей».