December 31st, 2014

ёжик

NP≠P. И про "осознаваемую неполноту"

Копирую сюда свою запись с форума dxdy.ru (там она от 09:53 - но у них время на 1 час бежит на сайте впереди Московского):

В июне 2014 я надеялся, что вернусь сюда в августе и дам здесь технически аккуратное доказательство для NPP. Однако по мере углубления в тему, я наталкивался на такие странные вещи, которые не мог проигнорировать, и которые ставили доказательство под сомнение. В итоге причину этих странностей мне все же удалось обнаружить (смею думать) через полгода с лишним. Вы будете крайне удивлены - какая это причина. И согласитесь со мной, что не только трудно было начать искать там, где она оказалась, но и обнародовать её немного страшновато. Зато это очень интересно. Приступим.

Теорема NPP.

Рассмотрим следующую задачу из класса NP, сформулированную в 2-ух пунктах:

1.       Имеется некоторая непротиворечивая (важно!) система аксиом Aks. В качестве слов будем рассматривать A() – записанные на языке теории алгоритмы. В качестве слова-свидетеля будем рассматривать текст доказательства для A() = i. Где i – некоторое число (можно считать, что число записано в десятичном представлении, но это не принципиально). Если имеется слово x и слово-свидетель y, то, как известно из логики, можно при помощи алгоритма автоматической проверки доказательств R(Aks, x, y) за полиномиальное время от размера y, проверить, доказывает ли y какое-то равенство A() = i для x на базе аксиом Aks. На размер y накладывается стандартное для NP ограничение некоторым полиномом от длины x.

2.       Если система аксиом Aks противоречива, то в качестве R(Aks, x, y) выбран предикат, который всегда выдает «ложь».

Заметим, что ограничение на длину доказательств не делает какие-либо доказательства теории недоступными. Просто всегда алгоритм A() можно расширить до нужного размера пустыми операторами. Затем станет доступно доказательство нужной длины для A() без «наполнителя», а затем достаточно дать короткое дополнение в доказательстве, которое приравняет A() с «наполнителем» и A() без «наполнителя». И противоречивая теория точно так же останется противоречивой, выдавая для одного и того же алгоритма какие угодно результаты в качестве доказуемых результатов. Правда все эти доказательства в противоречивой теории должны быть признаны ложными в соответствии с п.2.

Но главное в сформулированной задаче то, что она в любом случае является задачей из класса NP – какой бы пункт не был реализован. Потому что R(Aks, x, y) является полиномиальным по времени своей работы и в пункте 1, и в пункте 2.

В то же время – нет алгоритма, который позволял бы в общем случае определить, какой из пунктов – 1 или 2 – будет реализован. Потому что из логики известно, что задача определения непротиворечивости теории является в общем случае неразрешимой.

В то же время, задача сформулирована корректно, потому что всякая теория является либо противоречивой, либо непротиворечивой. Поэтому либо пункт 1, либо пункт 2 реализованы.

Получается неразрешимость (в общем случае) алгоритма проверки R(Aks, x, y). А это значит, что и универсального способа найти доказательство y по слову x – тем более нет. То есть - для конкретной задачи найти доказательство может и удастся, но способа для всех задач - нет, потому что их совокупность неразрешима.

Из этих общих соображений видно, что NPP. Но мы построим конкретный пример, демонстрирующий невозможность свести задачу NP к P.  Более того, нет вообще никакого корректного и ограниченного по времени универсального способа всегда найти истинное доказательство y для слова x – для подобных (сформулированных в пп. 1 и 2 ) задач. Притом речь идет про доказательства, которые есть и размеры которых соответствуют тем, которые допустимы для слова x. Чуть ниже будет построен конкретный пример такой невозможности.

Collapse )