dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

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. Чуть ниже будет построен конкретный пример такой невозможности.

Да, известно мнение, что для задач из класса NP есть способ перебора всех слов-свидетелей в пределах допустимого для них размера и получение заведомо правильного ответа – есть нужное слово-свидетель для заданного слова или его нет. Но это мнение опирается на ошибочную посылку, что заранее известен алгоритм проверки пары слово + слово-свидетель. А это – совершенно не обязательно. Перейдем к построению примера, где метод прямого перебора с ограничением по времени оказывается несостоятельным.

Перед построением примера оговорюсь, что хитрые конструкции, которые я использую в примере – довольно легко реализуются средствами логики (методом диагонализации, а не при помощи неподвижной функции, кстати говоря), и во второй части данной заметки я приведу все эти формальные конструкции и строгие выводы. Сейчас же даю общую картину:

Парадокс «Mt против AntiMt»

Берем нашу задачу из пунктов 1 и 2. Берем метод прямого перебора с ограничением по времени (фактически - ограничение по размеру доказательств) - алгоритм Mt(Aks, x). Для простоты считаем, что он выдает не текст доказательства, а результат этого доказательства (число i) как прогноз результата работы алгоритма A(). Напомню, что текст некоторого алгоритма A() подставлен на место переменной x, когда решается вопрос про результат работы этого алгоритма.

Если же нужного доказательства среди перебираемых доказательств не оказалось, то Mt(Aks, x) возвращает knockout (какое-то значение, которое мы так обозначим – ясно, что результаты Mt не прямо равны результатам A(), но техническое соответствие не обсуждаем пока). В данном случае «нокаут» означает, что счет оборвался, а ничего удовлетворительного не нашлось.

В качестве A() для нашего примера возьмем AntiMt() – такой алгоритм, который запускает внутри себя копию Mt(Aks, «AntiMt()») и возвращает в качестве результата нечто противоположное (отличное) тому, что «предсказывает» Mt про AntiMt. То есть, AntiMt запускает Mt со своим (AntiMt) текстом и «обманывает» Mt. Очевидно, что Mt в принципе не может выдать ничего, что могло бы правильно предсказать результат работы AntiMt. Единственный корректный результат, который может выдать Mt - это knockout.

А теперь мы сделаем и вовсе конфликтную вещь – мы включаем в число аксиом равенство Mt(Aks, «AntiMt()») = knockout. Технически это можно сделать диагонализацией, например. Тут нужно понимать, что Aks, которая подставлена в данную формулу - содержит в себе аксиому, эквивалентную самой этой формуле.

И что тогда выдаст Mt про AntiMt()? Ведь AntiMt() предельно прост – он запускает Mt(Aks, «AntiMt()») и обманывает его. А по аксиоме Mt(Aks, «AntiMt()») = knockout видно, чему равно Mt(Aks, «AntiMt()»). И поэтому ясно, что конкретно должен выдать AntiMt() в ответ на данный результат. «Ясно» - это значит, что есть соответствующее доказательство и оно очень короткое - потому что основано на нашей добавленной аксиоме и простых данных о примитивном устройстве AntiMt().

Но! Если Mt действительно выдаст нечто помимо knockout, то настоящая AntiMt() обманет его. И у этого факта тоже найдется доказательство. А это будет означать, что теория противоречива. А раз теория противоречива, то в нашей задаче включился пункт 2 и корректному алгоритму Mt про AntiMt() следовало выдать knockout. Но при этом разбираемое противоречие исчезло бы – как это ни забавно. Но и Mt повело бы себя корректно, хотя ценой за эту корректность оказывается невозможность для Mt сообщить очевидный прогноз о результате работы AntiMt.

Обратите внимание, как неожиданно красиво согласовались между собой разные факторы. Ведь мы дополнили состав аксиом новой аксиомой, которая, вроде бы, должна была привести к противоречию и ложному срабатыванию Mt() при анализе AntiMt(). Однако оказалось, что выдать значимый результат здесь Mt() не может, потому что тогда получится противоречие и это значит, что он должен выдавать только knockout. Но при таком условии и противоречия не возникает - потому что единственное, что утверждает наша добавленная аксиома, это что в точке AntiMt() наш  Mt() выдает knockout, но именно это и происходит и аксиома отражает реальность. При этом Mt() фактически «видит» свою неполноту и «отказывается» воспользоваться тем доказательством, которое есть и длина которого - в нужных пределах.

Тут мы встречаем математические основы рефлексии, имхо, основы того, без чего были бы невозможны наши субъективные «я». Каким-то образом Mt() «понимает» что речь в аксиоме идет именно про него и нарушать эту аксиому ему не следует. Очень интересный эффект. Поэтому я бы дал и второе название этому парадоксу - «Теорема об осознаваемой неполноте». Это по сути очень отличается от теорем Гёделя, где некоторые утверждения просто не могут быть доказаны - как и их отрицания - в теории. Но при этом сама теория не только не отдает себе в этом отчета, но доказательство подобных выводов внутри неё означало бы её противоречивость. А вот в разбираемом парадоксе неполнота в решениях алгоритма Mt() отражена в теории прямо на уровне аксиомы.

Как видим, даже метод прямого перебора с ограничением по времени потерпел крах в попытке решить задачу класса NP в нашем примере. Так что тут трудности с решением задач из класса NP не просто доходят до степени NPP, но и простираются значительно дальше.

Все приведенные рассуждения годятся и для полиномиального по времени алгоритма Mt. Поэтому мы доказали как NPP, так и значительно более сильное утверждение. Пока в эвристическом виде, но попозже дам и строгий.

Сформулируем некоторые выводы и наблюдения.

Ошибочное представление о возможности свести задачу из класса NP к некой NP-полной задаче связано  со следующим: Пусть даже нет в готовом виде алгоритма проверки истинности для пар слово + слово-свидетель в задаче из класса NP. И вместо готового алгоритма у нас есть какая-то менее очевидная формулировка, которая все же логически идентична некоторому подходящему для класса NP алгоритму проверки пар. Но вроде бы (внимание, тут ошибка!) можно за конечное число шагов всегда узнать этот алгоритм. Неважно, за экспоненциальное, факториальное или еще какое время от размера исходной формулировки задачи. Главное – это делается один раз и затем можно использовать для бесконечного числа единичных задач.

Например – для быстрой проверки любых слов-свидетелей надо один раз найти минимальный корень какого-то одного кубического уравнения. И вот если Петя знает, как решить кубическое уравнение, то для него задача проверки слов-свидетелей будет быстрой, а задача будет – из класса NP. А для Васи, который кубические уравнения решать не умеет – задача будет не из класса NP? Конечно же, нет такой зависимости класса NP от знания/незнания математика. А вместо этого предполагается, что всегда найдется Петя.

Однако, есть такие формулировки для NP-задач, которые, вообще говоря, не являются разрешимыми.  То есть, для их решения нет вообще никакого универсального способа. И мы построили пример такой задачи в пп. 1 и 2. А это значит, что неявное предположение о возможности всегда за конечное время найти алгоритм проверки для пары слово + слово-свидетель произвольной задачи из класса NP является ошибочным. Таким образом, мы доказали следующую теорему:

Теорема. Задачи класса NP не являются – вообще говоря – эффективно распознаваемыми.

Следствие. Никакая задача из класса NP не является NP-полной.

Следствие очевидно в силу того, что для сводимости необходимо знать алгоритм проверки пар слово + слово-свидетель для сводимой задачи. А способа для получения этого алгоритма нет – вообще говоря. Хотя именно с посылки о наличии готового алгоритма проверки пар начинается доказательство теоремы Кука о NP-полноте задачи ВЫП (задача проверки выполнимости предложений логики высказываний с пропозициональными переменными). Доказательство проведено корректно, но из неверной посылки. Поэтому не удивительно, что результат доказательства получился ошибочным.

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

Во второй части я дам техническое изложение парадокса «Mt против AntiMt». У меня все выводы и формулы уже написаны в текстовом виде, но надо переписать их в формате TeX, а с этими техническими моментами я обычно торможу – не очень-то я потренировался писать в TeX, а затем надолго отвлекся из-за логических вопросов. Могу выложить в текстовом виде в своем ЖЖ, если кто не хочет ждать и сообщит мне – тогда он сможет посмотреть там в ближайший день-другой.

И остается еще очень интересная тема о рефлексии – вот в разбираемом парадоксе с Mt и AntiMt было промоделировано поведение разумного «я», когда собственное поведение может привести к разрушению собственного прогноза и на основании этого якобы происходит отказ от попытки прогнозировать в подобных случаях. Тут видна логика иллюзии свободы воли, хотя система жестко подчиняется законам природы и либо она изначально устроена корректно, либо же нет (всё либо детерминировано, либо случайности не зависят от воли). Тут удается выйти на модель разумного «я» - но лучше будет отдельно рассмотреть данный вопрос. Весьма принципиальный вопрос, кстати.

Кроме того, можно совершенно иначе переписать те же теоремы Гёделя о неполноте, чтоб утверждения о неполноте заданной теории были доказуемыми в некотором смысле внутри самой заданной теории. Чтоб внутри теории был соответствующий корректный алгоритм, который на вопрос о непротиворечивости данной теории выдавал бы результат knockout и в теории было доказательство такого результата про себя саму.

Tags: NP≠P дискуссии, ЖЖвЖЖ математика
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 34 comments