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

[dmitgu]

mihaild в сообщении #1272971 писал(а):

Теперь мы применяем теорему лемму о диагонализации и находим формулу $AntiSol_{Sol, S}$, такую что $\vdash AntiSol_{Sol, S} \leftrightarrow B_{Sol, S}(\overline{AntiSol_{Sol, S}})$?
И строим язык $C$ как множество троек $AntiSol_{Sol, S}, Sol, S$?

Да, я бы только добавил ещё содержательную информацию, что
$\operatorname{ContrSol_0}(x, Sol, S)$ выдавал противоположное тому, что выдаёт $Sol$ в отношении $(x, S, ss(S))$, а когда была применена лемма о диагонализации, то утверждение $AntiSol_{Sol, S}$ само по себе стало выражать противоположное работе $Sol$ на самом этом утверждении ( вместе с $S, ss(S)$, разумеется ). Хотя, наверно, я забегаю вперёд. Ну и, может, вариант обозначения короче тоже сойдёт - $Anti_{Sol, S}$

А, еще в содержательное добавить про "если $Sol$ не останавливается, то $Anti_{Sol, S}$ не имеет доказательства" - с учетом параллельного перебора доказательств, которое не допускает возникновения доказуемости (так как сразу выдало бы 0). Всё же для нас недоказуемость $Anti_{Sol, S}$ для $Sol(\overline{Anti_{Sol, S}}, S, s)$ выделена - именно про неё будет сообщать алгоритм проверки языка $LS$ для слов языка $C$.

[mihaild]

Итого, язык $C$ состоит из троек $Anti_{Sol,S}, Sol, S$, где $Anti_{Sol,S}$ получается применением леммы о неподвижной точке?

Он вроде бы принадлежит $P$ - при проверке мы можем просто применить сами провести всю конструкцию с диагонализацией и проверить, что она выдаст ровно $Anti_{Sol,S}$.

И еще раз выпишите - в каких из языков $A, B, C$ мы даем число в бинарном виде, а в каких в унарном? (и я тогда запишу их определения сюда)

[dmitgu]

mihaild в сообщении #1272992 писал(а):

Он вроде бы принадлежит $P$ - при проверке мы можем просто применить сами провести всю конструкцию с диагонализацией и проверить, что она выдаст ровно $Anti_{Sol,S}$.

Да, точно.

mihaild в сообщении #1272992 писал(а):

И еще раз выпишите - в каких из языков $A, B, C$ мы даем число в бинарном виде, а в каких в унарном? (и я тогда запишу их определения сюда
)

Вообще-то и в бинарном (типа десятичного? $S$ - заглавная) и в унарном (по размеру строки? $s$ - прописная) надо бы оставить в языке $B$ - иначе не понятно, как быстро отличить слова из $B$ от слов из $C$ - и чем является $s$-прописная - "мусором", который не используется при вычислении или чем-то содержательным. Да я бы везде (то есть, и в $A$ тоже) оставил число в бинарном виде. А соответствующее ему "унарное" при корректном слове будет $s = ss(S)$.

Почему я бы оставил $S$ везде - потому что унарное $s$ является в семантическом отношении вспомогательным и обслуживающим формализм, а не смысл проблемы:

Зависимость размера сертификата (доказательства в разбираемом случае) именно от размера слова является условностью, которая (так сложилось) стала частью формализма класса $NP$. И для соответствия этой условности добавляется аналог $S$-заглавной, который выражает то же самое, что $S$-заглавная, но - своим размером ($s$-прописная).

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

То есть "на всякий случай" я бы оставил везде $S$-заглавная. Может, это и избыточно, но вроде, категоричности от нас никто не просит. С практической стороны, кстати, в языках программирования ситуация аналогична - в памяти, которая соответствует строке, хранится не только строка, как последовательность символов, но и отдельно от неё ещё и размер строки в бинарном виде. И время на вычисление размера строки - это время на получение этого готового числа, а не время перебора всех её символов.

[mihaild]

(не буду комментировать и разбираться в "идейной" части, об определениях $P$ и $NP$ мы уже договорились, уходить в философию бессмысленно)

Итого:
$n$ - некоторая фундаментальная мировая константа
$A$ - язык из слов вида $t, S, s$, где $S$ - число в двоичной записи, $s$ - строка из $S$ единиц, $t$ - теорема арифметики, у которой есть доказательство не длиннее $|s|^n$
$B$ - язык из слов вида $t, a, S, s$, где $\langle t, S, s\rangle \in A$, $a$ - некоторый алгоритм
$C$ - язык из слов вида $Anti_{Sol, S}, Sol, S$, где $Sol$ - некоторый алгоритм от трех аргументов, $S$ - число в двоичной записи, $Anti_{Sol, S}$ - формула, получаемая применением леммы о диагонализации к формуле $Sol(x, S, ss(S)) = 0$ (считая $x$ свободной переменной)
$LS = A \cup B \setminus C$
Так?

(прописная)

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

$s$ - прописная

venco в сообщении #1272465 писал(а):

Между прочим, "прописная" и "заглавная" - это одно и тоже. Вы, скорее всего, имели в виду "строчная".

[dmitgu]

mihaild в сообщении #1273148 писал(а):

$LS = A \cup B \setminus C$
Так?

Да.

[mihaild]

Добавил в post1256513.html#p1256513

Итак, у нас есть язык $LS$. Он в $NP$, и, видимо, $NP$-полный. Что дальше?

[dmitgu]

mihaild в сообщении #1273172 писал(а):

Итак, у нас есть язык $LS$. Он в $NP$, и, видимо, $NP$-полный. Что дальше?

Получается, что для достаточно большого $S$-заглавная при полиномиально быстром ответе алгоритма $\operatorname{Sol}(\overline{Anti_{Sol,S}}, S, ss(S))$ относительно размера слова из $C$ (а корректный ответ может быть только $0$) у нас будет достаточно короткое - в сравнении с $q(S)$ - доказательство для равенства:

$\operatorname{Sol}(\overline{AntiSol_S}, S, ss(S)) = 0$

А с учётом свойства

$\operatorname{ContrSol}(S) = \operatorname{If}( \operatorname{Sol}(\overline{AntiSol_S}, S, ss(S)) == 0, 1, 0 )$

Будем иметь элементарный вывод и для равенства:

$\operatorname{ContrSol}(S) = 1$, что и будет являться доказательством для утверждения:

$Anti_{Sol, S}$, при этом данное доказательство будет в допустимых пределах и поэтому результат от алгоритма $\operatorname{Sol}(\overline{Anti_{Sol, S}}, S, ss(S)) = 0$ будет отличаться от результата того алгоритма, который сводил бы язык $LS$ к классу $P$ (нужен результат $1$ для этого).

Фактически, это доказывает $NP \ne P$, так как алгоритм $\operatorname{Sol}(..., ..., ...)$ является произвольным и не может выдать ответ про утверждение $Anti_{Sol, S}$, соответствующий корректному алгоритму-решению языка класса $P$ при достаточно больших $S$-заглавная, если он выдаёт результат за полиномиальное время от размера слова языка $C$.

Если же результат $\operatorname{Sol}(\overline{Anti_{Sol, S}}, S, ...)$ будет выдаваться дольше, чем за полиномиальное количество шагов от размера слова языка $C$, то это само по себе не является алгоритмом-решением языка класса $P$. И в этом случае тоже нет сводимости $NP$ к $P$, так как алгоритм-решение $\operatorname{Sol}(..., ..., ...)$ является тут произвольным.

Но нужно понимать, что мы неявно пересмотрели то, что представляет собой неравенство $NP \ne P$ для нашего случая - если сравнивать с «обычными» языками класса $NP$, которые сейчас приводятся в учебниках.

[mihaild]

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

мы неявно пересмотрели то, что представляет собой неравенство $NP \ne P$ для нашего случая - если сравнивать с «обычными» языками класса $NP$, которые сейчас приводятся в учебниках

Мы так не договаривались. Мы договорились об определениях $P$ и $NP$ - post1256513.html#p1256513

Вы можете доказать про какой-то конкретный из языков $A, B, C$, что он не принадлежит $P$? (если нужно, я могу доказать, что из согласованного определения следует, что $P$ замкнуто относительно теоретико-множественных операций - т.е. если все три языка принадлежат $P$, то и $LS \in P$)

[dmitgu]

mihaild в сообщении #1273199 писал(а):

Вы можете доказать про какой-то конкретный из языков $A, B, C$, что он не принадлежит $P$?

Не в отдельном языке дело, а в конструкции из них )

Я же оговаривал особенность:

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

И в этом случае алгоритму решению $\operatorname{Sol}(w)$ переданы для рассмотрения 2 слова вида

1. $w$

2. $\overline{\operatorname{Sol}(...)}, w’$

При этом мы исходим из того, что алгоритм-решение $\operatorname{Sol}(...)$ располагает информацией о своём собственном программном коде $\overline{\operatorname{Sol}(...)}$ в той же мере, что и о значении переданного ему аргумента $w$ (аксиома рефлексии).

Но поскольку алгоритм-решение может вернуть только один результат, то язык $LS$ должен быть построен так, чтобы для обоих слов правильный результат произвольного алгоритма-решения $\operatorname{Sol}(...)$ всегда был одним и тем же.

Назовём это свойство «свойством согласованности языка $LS$».

При таком построении выясняется, что у $0$ (Нуля) есть тот смысл, который не виден на примере "языков из учебников":

Если ты выдавал $1$ про $w$ и это не соответствовало $w \in LS$, то выдавай $0$ - и всё Ок. Именно так обстоят дела для «стороннего наблюдателя», чья работа никак не влияет на принадлежность слова языку ($w \in LS$). Именно про такие языки класса $NP$ мы читаем в современных учебниках. Но корректное $1$ должно означать вообще-то, что и $1$ выдано, и при этом $w \in LS$. То есть, $1$ (единице) у алгоритма проверки должна соответствовать конъюнкция

$(\operatorname{Sol}(w) = 1 \wedge w \in LS)$.

А вот $0$ (нулю) тогда соответствует вовсе не конъюнкция отрицаний членов данной конъюнкции, а такая дизъюнкция:

$(\operatorname{Sol}(w) \ne 1 \vee w \notin LS)$ и случай

$(\operatorname{Sol}(w) = 0 \wedge w \in LS)$

вполне ему соответствует! И такое возможно и построено для «деятельного участника» (работа и результат работы которого влияет на язык) - в отличие от «стороннего наблюдателя» (работа которого не влияет на язык). И тогда полиномиальное соответствие скорости работы алгоритма-решения размеру слова и $0$ (нулю) алгоритма проверки приводит совсем не к привычному для «стороннего наблюдателя» результату $(w \notin LS)$, а как раз наоборот $(w \in LS)$ - в отношении слова из языка $A$.

[mihaild]

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

Не в отдельном языке дело, а в конструкции из них )

Этого не может быть, потому что

mihaild в сообщении #1273199 писал(а):

$P$ замкнуто относительно теоретико-множественных операций

(и это логично - если мы можем быстро проверять принадлежность $A, B, C$, то мы можем быстро проверить и принадлежность чему-то сооруженному из них с помощью объединения и вычитания)

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

И в этом случае алгоритму решению $\operatorname{Sol}(w)$ переданы для рассмотрения 2 слова вида

Я не понимаю, что это значит. И тем более я не понимаю, что такое "смысл нуля".

Я так понимаю, вы для каждого полиномиального алгоритма $T$ хотите найти либо слово, принадлежащее $LS$, на которое $T$ говорит "нет", либо слово, не принадлежащее $LS$, на которое $T$ говорит "да". Вы можете как-то явно выписать эти слова через $T$?

[dmitgu]

mihaild в сообщении #1273211 писал(а):

$P$ замкнуто относительно теоретико-множественных операций

А тут я не понимаю ) Мы же вроде тот язык из $NP$ пытаемся построить, который не является языком из $P$ ?

mihaild в сообщении #1273211 писал(а):

dmitgu в сообщении #1273204

писал(а):
И в этом случае алгоритму решению $\operatorname{Sol}(w)$ переданы для рассмотрения 2 слова вида
Я не понимаю, что это значит.

У $Sol$ есть информация, которая достаточна для построения 2-х слов языка $LS$. И корректный ответ (число) может быть только 0 (Ноль) для $Sol$ - при этом в отношении каждого из этих слов.

-- 08.12.2017, 19:05 --

З.Ы. Про смыслы $0$ - это у меня "философия" )

[mihaild]

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

Мы же вроде тот язык из $NP$ пытаемся построить, который не является языком из $P$ ?

Ага, причем собираем его простыми операциями из трех языков. Чтобы у нас получилось, нужно чтобы хотя бы один из исходных языков не принадлежал $P$. Потому что можно доказать $A \in P \wedge B \in P \wedge C \in P \rightarrow (A \cup B \setminus C) \in P$

Что значит "достаточная информация для построения чего-то там" я не понимаю.

Давайте не перепрыгивать. Мы договорились об определении языка $LS$. Теперь нужно доказать, что он не принадлежит $P$.

[dmitgu]

mihaild в сообщении #1273222 писал(а):

Давайте не перепрыгивать. Мы договорились об определении языка $LS$. Теперь нужно доказать, что он не принадлежит $P$.

Ок.
$\operatorname{Sol}(\overline{Anti_{Sol, S}}, S, s)$

он ищет ответ про какое слово? Про оба:

1. $\overline{Anti_{Sol, S}}, S, s$
2. $\overline{\operatorname{Sol}(..., ..., ...)}, \overline{Anti_{Sol, S}}, S$

И корректный ответ может быть только $0$, потому что так в отношении 2-го случая (слово языка $C$), а в отношении 1-го если $s \ne ss(S)$, то понятно, а иначе 1 сделает $Anti_{Sol, S}$ недоказуемым.

[mihaild]

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

он ищет ответ

Что значит "алгоритм ищет ответ"?

Что такое $Sol$? Всё еще произвольный алгоритм? Тогда это может скажем быть алгоритм "игнорируй вход и выдай $0$" или "игнорируй вход и выдай $1$".
Термин "корректный ответ алгоритма" не определен.

[dmitgu]

mihaild в сообщении #1273228 писал(а):

Термин "корректный ответ алгоритма" не определен.

Определён - если мы сравниваем с тем, может ли данный алгоритм быть алгоритмом проверки языка класса $P$. Класс $P$ определён так, что для принадлежащего языку слова алгоритм проверки должен возвращать 1, а для не принадлежащего - 0. Хоть это и условность и можно было бы определить ещё миллионом способов. Но что однозначно - это полиномиальное количество шагов относительно размера слова. Так если у нас 1 будет результат у $\operatorname{Sol}(\overline{Anti_{Sol, S}}, S, s)$ - то это заведомо некорректный результат, если сравнивать с алгоритмом проверки языка класса $P$.