Почему я не верю в простые алгоритмы для NP-полных задач

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

Примерно полгода назад, в августе 2010-го была опубликована попытка доказать что P≠NP. Тогда один математик-блогер, Скотт Оронсон, чтобы не казаться голословным в своём недоверии к этому доказательству поставил свой дом на то, что доказательство окажется ошибочным. Пожалуй, я ничего не потеряю если последую (с меньшим размахом) его примеру и поставлю на то, что нынешний алгоритм неправилен свой автомобиль (Auris 2008-го года выпуска).

По-моему, Оронсон немного рисковал. Винод Деолаликар, автор того доказательства — относительно известный математик, задача P≠NP входит в область его компетенции, и само доказательство использовало несколько принципиально новых идей, дающих надежду на то, что с помощью них удастся обойти трудности, с которыми сталкивались те кто пытался доказать этот факт до него. С нынешним доказательством ситуация немного иная.

Сначала о том, что говорит в его пользу. Доказательство написано достаточно грамотно, его автор обладает математической подготовкой, а главное — кроме статьи про алгоритм существует его работающая реализация.

Теперь о том, почему я не верю в то, что этот алгоритм может оказаться правильным.

Начну с того, что на сегодняшний день в среде учёных, занимающихся теорией сложности и вообще theoretical computer science, существует консенсус, что P таки не равно NP, то есть быстрых алгоритмов для задач типа задачи коммивояжёра, 3-SAT, SAT, задачи о рюкзаке и т.д. не существует. Почему учёные так думают? Потому что в последние несколько десятков лет стали известны сотни NP-полных задач, вплоть до задачи об оптимальном алгоритме для игры в сапёра. Достаточно решить хоть одну из этих задач, чтобы все они оказались решены. И тем не менее, несмотря на все усилия тысяч людей, никаких продвижений в сторону создания алгоритмов для этих задач пока не наблюдается.

Даже если представить себе, что когда-нибудь окажется что P=NP, то доказательство этого факта и алгоритм для решения NP-полных задач обязаны использовать какие-то принципиально новые идеи, какие-то методы, которыми мы сейчас не владеем. Деолаликар, к примеру, в своей попытке доказательства пользовался статистическими методами. Как правило, прорывы в старых сложных задачах происходят именно так. Теорему Ферма доказали только построив вокруг неё большую теорию из области алгебраической геометрии.

Как это не парадоксально, доверия нынешнему доказательству не прибавляет и то, что само оно достаточно короткое: его существенные части занимают едва ли 2-3 страницы. Для сравнения, доказательство теоремы Ферма занимает 200-300 страниц, не включая предварительные сведения из использующихся разделов математики.

Последний и, вероятно, главный повод для недоверия содержится в самом методе доказательства. Чтобы не вдаваться в подробности, проведу аналогию. Представьте себе, что вы решаете судоку (да-да, решение судоку — это тоже NP-полная задача). Допустим, вы делаете это следующим способом: вы фиксируете для себя несколько правил, а дальше обходите табличку, применяя их некотором порядке. Правила должны быть локальными типа:

— Строчка уже содержит данное число, значит в других клетках строчки это число стоять не может.
— В двух клетках квадрата могут стоять только числа X и Y, значит в других клетках квадрата эти числа стоять не могут.
и т.д.

Так вот, если судоку простой, то вполне возможно, что пользуясь только этими правилами, вы сможете его решить. Но в сложном судоку вам неприменно придётся помимо тупого применения правил разбирать какие-нибудь варианты.

Ситуация с обсуждаемым алгоритмом примерно такая же как с методом игры в судоку. В нём зафиксировано несколько правил, в соответствии с которыми мы отбрасываем не подходящие нам решения. Проблема в том, что также как и в судоку, в задаче 3-SAT этого хватать не должно.

P.S. Прошу не считать этот пост опровержением алгоритма. Это всего лишь эвристические доводы почему этот алгоритм не должен работать. Автор предыдущего поста обещал опубликовать завтра продолжение, в котором он ответит на поступившие в комментариях вопросы.