Новая заявка на решение задачи P vs. NP

На днях Норберт Блюм ^[1] опубликовал ^[2] на архиве препринт с названием «A Solution of the P versus NP Problem». Таким образом Блюм претендует на решение одной из задач тысячелетия ^[3], за которую кроме почестей полагается 1 миллион долларов. В данной статье я собрал небольшое резюме об этом.

Что доказывается?

Проблему равенства классов P и NP можно неформально определить следующим образом:

Если положительный ответ на какой-то вопрос можно быстро (за полиномиальное время) проверить (используя некоторую вспомогательную информацию, называемую сертификатом), то верно ли, что и сам ответ (вместе с сертификатом) на этот вопрос можно быстро найти? Задачи первого типа относятся к классу P, второго — к классу NP. Проблема равенства этих классов является одной из важнейших проблем теории алгоритмов. (Wikipedia)

В статье Блюма доказывается более сильное утверждение:

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

Из этого утверждения следует, что P ≠ NP. Действительно, если P = NP, то для каждой задачи из NP (в т.ч. и для проверки клики) существует полиномиальный алгоритм, а полиномиальный алгоритм можно преобразовать в семейство булевых схем полиномиального размера. Таким образом, если для какой-то задачи из NP не существует булевых схем полиномиального размера, то P ≠ NP.

Почему сам факт появления доказательства не удивителен

Как и для любой другой известной математической проблемы, доказательства P = NP или P ≠ NP появляются с завидной регулярностью — можете посмотреть подборку из 100+ доказательств на этом сайте ^[4]. Однако далеко не все из них привлекают внимание научного сообщества. В предыдущий раз такое случалось 7 лет назад, когда свое доказательство опубликовал ^[5] Винай Деолаликар, но и в его доказательстве обнаружили ошибку ^[6].

Почему же доказательство Блюма привлекло внимание?

Во-первых, Норберт Блюм — известный и уважаемый учёный, который в то же время славится своей дотошностью. Сомнительно, что он стал бы публиковать эту статью, если бы не был уверен на 100% в её правильности. Во-вторых, предложенная техника обходит все известные ограничения на доказательство P ≠ NP. Дело в том, что в теории сложности есть серия утверждений вида «такая техника не сможет доказать P ≠ NP» (Natural Proofs, релятивизация, алгебраизация), но предложенная техника аккуратно обходит все эти ограничения.

Единственный на данный момент серьёзный аргумент против этого доказательства заключается в том, что эта статья выглядит слишком простой для такого результата. Удивительно, что в статье на 30 с небольшим страниц разрешена такая сложная проблема. Действительно, по сравнению с доказательствами Уайлса (Большая теорема Ферма), Перельмана (гипотеза Пуанкаре) и даже с недавним результатом Бабая (квазиполиномиальный алгоритм для изоморфизма графов), доказательство Блюма выглядит невероятно простым и коротким. С другой стороны, у этого может быть объяснение — Блюм не доказывает с нуля, а развивает технику Берга и Ульфберга, которая в свою очередь основана на прорывных результатах Разборова, Андреева и Тардош, то есть может оказаться, что «всё сложное» уже было сделано раньше, и оставалось только «сложить паззл».

Что теперь будет?

Ничего особенного. Скорей всего через некоторое время в статье найдут ошибку, как это случалось во всех предыдущих случаях. При этом не исключено (но очень маловероятно), что Блюм действительно доказал, что P ≠ NP. В таком случае на проверку статьи уйдёт довольно много времени — статья не будет признана верной, пока эксперты в этой области не разберут весь результат по кирпичикам и не проверят его правильность досконально.

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

Основное обсуждение происходит на StackExchange ^[7] — там собираются все комментарии и определяются места, в которых могут быть ошибки. Есть так же тред на Quora и некоторое обсуждение в комментариях к посту ^[8] Луки Тревиссана.

Если вы хотите более подробно разобраться в том, что происходит, то почитайте посты Луки Тревиссана ^[8] и Ричарда Липтона ^[9].

Объяснение от «не специалиста» так же можно найти тут ^[10].

Пока большинство экспертов настроенны скептично. Например, известный эксперт по сложности и квантовым вычисленим Скотт Ааронсон ^[11] поставил ^[12] $200 тыс. на то, что доказательство не верно. Кстати, у Скотта Ааронсона есть интереснейший набор из 10 тестов ^[13], которые позволяют определить, заслуживает ли статья с решением какой-то серьёзной проблемы, внимания. Насколько я понимаю, статья Блюма проходит все эти тесты, кроме последнего: предложенное доказательство выглядит слишком простым.

Update: Пока я писал этот пост, в обсуждении на StackExchange появился комментарий, в котором утверждается, что Александр Разборов ^[14] (на результатах которого строится доказательство Блюма) уже просмотрел статью и нашёл в ней ошибку.

Автор: avsmal

Источник ^[15]