NP≠P. Док-во от противного-контрпример алгоритмов из NP

[dmitgu]

Xaositect в сообщении #874656 писал(а):

Но Вы утверждали, что $T$ полиномиальный. А я Вам говорю, что полиномиальным от текста задачи он быть не может.

Почему? Там же идет просто банальная подстановка текста заданной задачи в нужное место $T$ - и у нас готов алгоритм для решения каждой ее единичной задачи.

[Xaositect]

Потому что внутри $T$ используется теорема Кука, а конструкция теоремы Кука зависит не только от текста задачи, но и от ограничивающего полинома.

[dmitgu]

Xaositect в сообщении #874665 писал(а):

Потому что внутри $T$ используется теорема Кука, а конструкция теоремы Кука зависит не только от текста задачи, но и от ограничивающего полинома.

Ну да, я об этом тут забывал сказать часто. Но в рассуждении о работе алгоритма и про цикл - говорил. Он выписывает члены коньюнктивной нормальной формы столько раз, сколько этого требует ограничивающий полином. Вот в чем готовность алгоритма - получив на вход "слово" - он вычисляет сколько циклов ему делать для переписывания слова к готовому для решения вида, а после цикла переписывания - решает имеющимся способом. И вот в количестве циклов написания членов конъюнктивной нормальной формы и "играет" ограничивающий полином.

[Xaositect]

То есть Ваш $T$ он не для всех $NP$-задач, а только для тех, у которых полином проверяющей машины имеет некоторую фиксированную степень?

[dmitgu]

Xaositect в сообщении #874681 писал(а):

То есть Ваш $T$ он не для всех $NP$-задач, а только для тех, у которых полином проверяющей машины имеет некоторую фиксированную степень?

Тут уже я начинаю не понимать. А разве полином для заданной задачи не является чем-то фиксированным?
Просто под "текстом задачи" я понимал выше не только текст алгоритма проверки, но и текст ограничивающего полинома. И этого достаточно (этой информации), чтоб алгоритм $T$ мог свести каждую единичную задачу из заданной массовой к известному ему варианту "своей" единичной задачи и решить ее.

И для каждой задачи $NP$ задается свой полином. Эти полиномы могут быть разными для разных задач и степени у них тоже могут отличаться.

[Xaositect]

dmitgu в сообщении #874695 писал(а):

Просто под "текстом задачи" я понимал выше не только текст алгоритма проверки, но и текст ограничивающего полинома. И этого достаточно (этой информации), чтоб алгоритм $T$ мог свести каждую единичную задачу из заданной массовой к известному ему варианту "своей" единичной задачи и решить ее.

Да, но от полинома время работы конструкции из теоремы Кука зависит экспоненциально.

[dmitgu]

Xaositect в сообщении #874698 писал(а):

Да, но от полинома время работы конструкции из теоремы Кука зависит экспоненциально.

Нет. Она выписывает блоков конъюнктивной нормальной формы полиномиальное число от ограничивающего полинома. Этим описываются все возможные пути алгоритма (которых да, неполиномиально много), но все это многообразие путей определяется разными возможными значениями для логических переменных. В этом и сложность решения проблемы выполнимости - экспоненциальное количество вариантов. Но если есть решение для задачи ВЫП, то к нему можно свести и любую другую из $NP$

[Xaositect]

dmitgu в сообщении #874706 писал(а):

Она выписывает блоков конъюнктивной нормальной формы полиномиальное число от ограничивающего полинома.

Длина конъюнктивной нормальной формы экспоненциальна по длине записи ограничивающего полинома.

[dmitgu]

Xaositect в сообщении #874709 писал(а):

Длина конъюнктивной нормальной формы экспоненциальна по длине записи ограничивающего полинома.

Ну и что? Вы имеете в виду, что ограничивающий полином:
$x^2+x+5$ имеет длину 6 символов и будет слишком мал чтоб сравнивать его со временем работы алгоритма решения? Так это для любого решения задачи $NP$ так. Само слово может быть сколь угодно больше размера полинома (длине его текста), не говоря уж о времени решения.

[Xaositect]

Да, я извиняюсь.

Если существует полиномиальная машина, решающая задачу ВЫП, то существует полномиальная машина, которая получает на вход строку $\Pi*|^c*|^d$, где $\Pi$ - программа машины, проверяющей сертификат для некоторой задачи из $\mathrm{NP}$, а $cn^d$ - многочлен, ограничивающий длину сертификата и время выполнения программы, а на выходе выдает программу машины, решающей рассматриваемую задачу за полиномиальное время.

Что у Вас там было дальше? Вы доказывали, что это невозможно?

[dmitgu]

Xaositect в сообщении #874720 писал(а):

Да, я извиняюсь.

Если существует полиномиальная машина, решающая задачу ВЫП, то существует полномиальная машина, которая получает на вход строку $\Pi*|^c*|^d$, где $\Pi$ - программа машины, проверяющей сертификат для некоторой задачи из $\mathrm{NP}$, а $cn^d$ - многочлен, ограничивающий длину сертификата и время выполнения программы, а на выходе выдает программу машины, решающей рассматриваемую задачу за полиномиальное время.

Что у Вас там было дальше? Вы доказывали, что это невозможно?

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

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

[rubtsov_anton]

Xaositect в сообщении #874720 писал(а):

Если существует полиномиальная машина, решающая задачу ВЫП, то существует полномиальная машина, которая получает на вход строку $\Pi*|^c*|^d$, где $\Pi$ - программа машины, проверяющей сертификат для некоторой задачи из $\mathrm{NP}$, а $cn^d$ - многочлен, ограничивающий длину сертификата и время выполнения программы, а на выходе выдает программу машины, решающей рассматриваемую задачу за полиномиальное время.

А теперь уже я не понимаю о чем идет речь.

Что такое "полиномиальная машина"? Речь о ДМТ или НМТ? Что такое "программа машины"?

[dmitgu]

rubtsov_anton в сообщении #876406 писал(а):

А теперь уже я не понимаю о чем идет речь.

Что такое "полиномиальная машина"? Речь о ДМТ или НМТ? Что такое "программа машины"?

Речь идет о ДМТ - тут обычно идет речь о ДМТ, потому что как раз про нее интересно - можно ли получить алгоритм-решение с полиномиальной скоростью работы.

Я тут выпал из обсуждения, потому что читал теорию алгоритмов. Оказывается, есть такая теорема М. Блюма о псевдоускорителе (и об ускорителе - в развитие), в которой доказано существование такой функции, что для каждого вычисляющего ее алгоритма $A_i$ найдется алгоритм $A_j$, вычисляющий ее почти всюду (кроме конечного числа точек) и почти всюду быстрее чем даже не просто алгоритм $A_i$, но даже быстрее чем его скорость, увеличенная произвольной функцией! Никак не мог несколько дней понять доказательство (из-за иных умолчаний, чем привык - максимум по пустому множеству оказывается они считают ноль, параметрический (по номеру) результат от применения заданной номером функции обозначен той же буквой что и для применяемых функции и т.п.).

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

Но я в своем доказательстве (если там нет ошибок, конечно) отрицательно решаю вопрос и о таком выделении - там тоже есть функции (точнее, семейство алгоритмов), для которых всегда есть более быстрые вычисляющие их алгоритмы, который включает эти функции в "быстрый" класс, куда их не включал прежний алгоритм (каким бы он ни был). Но я рад, что сама моя идея "более быстрый алгоритм вообще говоря есть" - подтвердилась и она такая же, как и у математиков со времен М.Блюма.

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

[rubtsov_anton]

dmitgu в сообщении #877148 писал(а):

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

Хорошо бы еще строго в пределах одной отдельно взятой терминологии. Предпочтительно на языке машин Тьюринга, где наиболее адекватно определено что такое сертификат. В ней же и все ошибки были бы намного виднее.

[dmitgu]

В июне 2014 я надеялся, что вернусь сюда в августе и дам здесь технически аккуратное доказательство для $NP \ne P$. Однако по мере углубления в тему, я наталкивался на такие странные вещи, которые не мог проигнорировать, и которые ставили доказательство под сомнение. В итоге причину этих странностей мне все же удалось обнаружить (смею думать) через полгода с лишним. Вы будете крайне удивлены - какая это причина. И согласитесь со мной, что не только трудно было начать искать там, где она оказалась, но и обнародовать её немного страшновато. Зато это очень интересно. Приступим.
Теорема $NP \ne P$. Часть первая - эвристический уровень.
Рассмотрим следующую задачу из класса $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$ – тем более нет. То есть - для конкретной задачи найти доказательство может и удастся, но способа для всех задач - нет, потому что их совокупность неразрешима.
Из этих общих соображений видно, что $NP \ne P$. Но мы построим конкретный пример, демонстрирующий невозможность свести задачу $NP$ к $P$. Более того, нет вообще никакого корректного и ограниченного по времени универсального способа всегда найти истинное доказательство $y$ для слова $x$ – для подобных (сформулированных в пп. 1 и 2 ) задач. Притом речь идет про доказательства, которые есть и размеры которых соответствуют тем, которые допустимы для слова $x$. Чуть ниже будет построен конкретный пример такой невозможности.
Да, известно мнение, что для задач из класса $NP$ есть способ перебора всех слов-свидетелей в пределах допустимого для них размера и получение заведомо правильного ответа – есть нужное слово-свидетель для заданного слова или его нет. Но это мнение опирается на ошибочную посылку, что заранее известен алгоритм проверки пары слово + слово-свидетель. А это – совершенно не обязательно. Перейдем к построению примера, где метод прямого перебора с ограничением по времени оказывается несостоятельным.
Перед построением примера оговорюсь, что хитрые конструкции, которые я использую в примере – довольно легко реализуются средствами логики (методом диагонализации, а не при помощи неподвижной функции, кстати говоря), и во второй части данной заметки я приведу все эти формальные конструкции и строгие выводы. Сейчас же даю общую картину.
Парадокс «$Mt$ против $AntiMt$»
Берем нашу задачу из пунктов 1 и 2. Берем метод прямого перебора с ограничением по времени (фактически - ограничение по размеру доказательств) - алгоритм $\operatorname{Mt}(Aks, x)$. Для простоты считаем, что он выдает не текст доказательства, а результат этого доказательства (число $i$) как прогноз результата работы алгоритма $A()$. Напомню, что текст некоторого алгоритма $A()$ подставлен на место переменной $x$, когда решается вопрос про результат работы этого алгоритма. Чтоб отличить в формулах алгоритмы от их текстов, буду обозначать тексты чертой над обозначением алгоритма. Вот так, например: $\overline{\operatorname{AntiMt}()}$
Если же нужного доказательства среди перебираемых доказательств не оказалось, то $\operatorname{Mt}(Aks, x)$ возвращает $knockout$ (какое-то значение, которое мы так обозначим – ясно, что результаты $Mt()$ не прямо равны результатам $A()$, но техническое соответствие не обсуждаем пока). В данном случае «нокаут» означает, что счет оборвался, а ничего удовлетворительного не нашлось.
В качестве $A()$ для нашего примера возьмем $\operatorname{AntiMt}()$ – такой алгоритм, который запускает внутри себя копию $\operatorname{Mt}( Aks, \overline{\operatorname{AntiMt}()})$ и возвращает в качестве результата нечто противоположное (отличное) тому, что «предсказывает» $Mt$ про $AntiMt$. То есть, $AntiMt$ запускает $Mt$ со своим ($AntiMt$) текстом и «обманывает» $Mt$. Очевидно, что $Mt$ в принципе не может выдать ничего, что могло бы правильно предсказать результат работы $AntiMt$. Единственный корректный результат, который может выдать $Mt$ - это $knockout$.
А теперь мы сделаем и вовсе конфликтную вещь – мы включаем в число аксиом равенство $\operatorname{Mt}( Aks, \overline{\operatorname{AntiMt}()}) = knockout$. Технически это можно сделать диагонализацией, например. Тут нужно понимать, что $Aks$, которая подставлена в данную формулу - содержит в себе аксиому, эквивалентную самой этой формуле.
И что тогда выдаст $Mt$ про $AntiMt$? Ведь $AntiMt()$ предельно прост – он запускает $\operatorname{Mt}( Aks, \overline{\operatorname{AntiMt}()} )$ и обманывает его. А по аксиоме $\operatorname{Mt}( Aks, \overline{\operatorname{AntiMt}()}) = knockout$ видно, чему равно $\operatorname{Mt}( Aks, \overline{\operatorname{AntiMt}()} )$. И поэтому ясно, что конкретно должен выдать $AntiMt()$ в ответ на данный результат. «Ясно» - это значит, что есть соответствующее доказательство и оно очень короткое - потому что основано на нашей добавленной аксиоме и простых данных о примитивном устройстве $AntiMt()$.
Но! Если $Mt$ действительно выдаст нечто помимо $knockout$, то настоящая $AntiMt()$ обманет его. И у этого факта тоже найдется доказательство. А это будет означать, что теория противоречива. А раз теория противоречива, то в нашей задаче включился пункт 2 и корректному алгоритму $Mt()$ про $AntiMt()$ следовало выдать прогноз $knockout$ (хотя точнее назвать это отказом от прогнозирования). Но при этом разбираемое противоречие исчезло бы – как это ни забавно. Но и $Mt$ повел бы себя корректно, хотя ценой за эту корректность оказывается невозможность для $Mt$ сообщить очевидный прогноз о результате работы $AntiMt$.
Обратите внимание, как неожиданно красиво согласовались между собой разные факторы. Ведь мы дополнили состав аксиом новой аксиомой, которая, вроде бы, должна была привести к противоречию и ложному срабатыванию $Mt()$ при анализе $AntiMt()$. Однако оказалось, что выдать значимый результат здесь $Mt()$ не может, потому что тогда получится противоречие и это значит, что он должен выдавать только $knockout$. Но при условии выдачи $knockout$ и противоречия не возникает - потому что единственное, что утверждает наша добавленная аксиома, это что в точке $\overline{\operatorname{AntiMt}()}$ наш $Mt()$ выдает $knockout$, но именно это и происходит и аксиома отражает реальность. При этом $Mt()$ фактически «видит» свою неполноту и «отказывается» воспользоваться тем доказательством, которое есть и длина которого - в нужных пределах.
Тут мы встречаем математические основы рефлексии, имхо, основы того, без чего были бы невозможны наши субъективные «я». Каким-то образом $Mt()$ «понимает» что речь в аксиоме идет именно про него и нарушать эту аксиому ему не следует. Очень интересный эффект. Поэтому я бы дал и второе название этому парадоксу - «Теорема об осознаваемой неполноте». Это по сути очень отличается от теорем Гёделя, где некоторые утверждения просто не могут быть доказаны - как и их отрицания - в теории. Но при этом сама теория не только не отдает себе в этом отчета, но доказательство подобных выводов внутри неё означало бы её противоречивость. А вот в разбираемом парадоксе неполнота в решениях алгоритма $Mt()$ отражена в теории прямо на уровне аксиомы и противоречий не возникает.
Как видим, даже метод прямого перебора с ограничением по времени потерпел крах в попытке решить задачу класса $NP$ в нашем примере. Так что тут трудности с решением задач из класса $NP$ не просто доходят до степени $NP \ne P$, но и простираются значительно дальше.
Все приведенные рассуждения годятся и для полиномиального по времени алгоритма $Mt$. Поэтому мы доказали как $NP \ne P$, так и значительно более сильное утверждение. Пока в эвристическом виде, но попозже дам и строгий.
Сформулируем некоторые выводы и наблюдения.
Ошибочное представление о возможности свести задачу из класса $NP$ к некой $NP$-полной задаче связано со следующим: Пусть даже нет в готовом виде алгоритма проверки истинности для пар слово + слово-свидетель в задаче из класса $NP$. И вместо готового алгоритма у нас есть какая-то менее очевидная формулировка, которая все же логически идентична некоторому подходящему для класса $NP$ алгоритму проверки пар. Но вроде бы (внимание, тут ошибка!) можно за конечное число шагов всегда узнать этот алгоритм. Неважно, за экспоненциальное, факториальное или еще какое время от размера исходной формулировки задачи. Главное – это делается один раз и затем можно использовать для бесконечного числа единичных задач.
Например – для быстрой проверки любых слов-свидетелей надо один раз найти минимальный корень какого-то одного кубического уравнения. И вот если математик Петя знает, как решить кубическое уравнение, то для него задача проверки слов-свидетелей будет быстрой, а задача будет – из класса $NP$. А для математика Васи, который кубические уравнения решать не умеет – задача будет не из класса $NP$? Конечно же, нет такой зависимости класса $NP$ от знания/незнания математика. А вместо этого предполагается, что всегда найдется Петя.
Однако, есть такие формулировки для $NP$-задач, которые, вообще говоря, не являются разрешимыми. То есть, для их решения нет вообще никакого универсального способа. И мы построили пример такой задачи в пп. 1 и 2. А это значит, что неявное предположение о возможности всегда за конечное время найти алгоритм проверки для пары слово + слово-свидетель произвольной задачи из класса $NP$ является ошибочным. Таким образом, мы доказали следующую теорему:
Теорема. Задачи класса $NP$ не являются – вообще говоря – эффективно распознаваемыми.
Следствие. Никакая задача из класса $NP$ не является $NP$-полной.
Следствие очевидно в силу того, что для сводимости необходимо знать алгоритм проверки пар слово + слово-свидетель для сводимой задачи. А способа для получения этого алгоритма нет – вообще говоря. Хотя именно с посылки о наличии готового алгоритма проверки пар начинается доказательство теоремы Кука о NP-полноте задачи ВЫП (задача проверки выполнимости предложений логики высказываний с пропозициональными переменными). Доказательство проведено корректно, но из неверной посылки. Поэтому не удивительно, что результат доказательства получился ошибочным.
В ещё недавней истории, обнаруженные в логике парадоксы привели к необходимости пересмотреть основания математики, что породило глубокие и опустошительные результаты. И вот если изложенный здесь парадокс правильный, то теория алгоритмов тоже нуждается в основательном пересмотре.
Во второй части я дам техническое изложение парадокса «$Mt$ против $AntiMt$». У меня все выводы и формулы уже написаны в текстовом виде, но надо переписать их в формате $\TeX$, а с этими техническими моментами я обычно торможу – не очень-то я потренировался писать в $\TeX$, а затем надолго отвлекся из-за логических вопросов. Могу выложить в текстовом виде в своем ЖЖ, если кто не хочет ждать и сообщит мне – тогда он сможет посмотреть там в ближайший день-другой.
И остается еще очень интересная тема о рефлексии – вот в разбираемом парадоксе с $Mt$ и $AntiMt$ было промоделировано поведение разумного «я», когда собственное поведение может привести к разрушению собственного прогноза и на основании этого якобы происходит отказ от попытки прогнозировать в подобных случаях. Тут видна логика иллюзии свободы воли, хотя система жестко подчиняется законам природы и либо она изначально устроена корректно, либо же нет (всё либо детерминировано, либо случайности не зависят от воли). Тут удается выйти на модель разумного «я» - но лучше будет отдельно рассмотреть данный вопрос. Весьма принципиальный вопрос, кстати.
Кроме того, можно совершенно иначе переписать те же теоремы Гёделя о неполноте, чтоб утверждения о неполноте заданной теории были доказуемыми в некотором смысле внутри самой заданной теории. Чтоб внутри теории был соответствующий корректный алгоритм, который на вопрос о непротиворечивости данной теории выдавал бы результат $knockout$ и в теории было доказательство такого результата про себя саму.