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

[dmitgu]

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

У любого конкретного слова есть размер.

Не обязательно оно конкретное ) "Часть слова" $s$ может не использоваться в проверке как и слишком длинный сертификат. И ответ будет 0. И чем тогда является "часть слова" $s$ - действительно частью слова или частью сертификата? Который избыточен? Это же полный произвол - считать, что в отвергнутом слове есть или нет часть $s$, которая не используется )

[mihaild]

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

И чем тогда является "часть слова" $s$ - действительно частью слова или частью сертификата?

Я вообще не понимаю, что это значит. Можете переформулировать в терминах кортежей, кодирования и т.д.?

[dmitgu]

Ну, "часть сертификата" я зря сказал. Я имею в виду, что алгоритм проверки может не использует часть $s$ чтобы отвергнуть слово. Отвергает некое слово "не глядя" на его $s$ - хоть при 0-й длине, хоть не при нулевой. Посмотрел на часть слова ($t$, $a$), а на $s$ - не смотрел. И где Ваше "кроме того" - в котором ограничение от длины слова? По логике работы алгоритма проверки он отверг слово, в котором вообще нет части $s$ или онА (часть) нулевой длины.

З.Ы. Тут по работе грузят, не смогу сейчас отвечать, видимо, пардон.

[mihaild]

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

И где Ваше "кроме того" - в котором ограничение от длины слова? По логике работы алгоритма проверки он отверг слово, в котором вообще нет части $s$ или оно нулевой длины.

Вот именно для этого нужны строгие определения. Что такое "логика алгоритма"?
Если хотите - можно рассматривать только входы какого-то определенного вида (кортежи нужной длины) и оценивать время работы в терминах отдельных элементов этих кортежей. Собственно у меня так и сделано.

Если хотите - можете предложить свое определение $NP$, только строго; прочитайте внимательно мои формулировки, а лучше - формулировки в хороших книгах, и попробуйте им подражать - определение должно иметь вид, например, "язык $L$ принадлежит $NP$, если существуют ..., такие что ...".

[dmitgu]

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

можете предложить свое определение $NP$, только строго

Ок, попробую но не сегодня-завтра наверно. Согласны, что в учебнике с их "размером слов" есть явно тёмные места? )) И у Вас - раз слово "которого нет" может быть неопределенной длины. Можно считать длину условно - от того, что использует алгоритм проверки когда отвергает слово. Такое определение пойдёт? Если его аккуратно расписать?

[mihaild]

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

Согласны, что в учебнике с их "размером слов" есть явно тёмные места?

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

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

раз слово "которого нет" может быть неопределенной длины

Я всё еще не понимаю, что такое "слово, которого нет".

(Оффтоп)

И единственная ассоциация тут - с Лукьяненко

-- 18.10.2017, 16:58 --

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

Можно считать длину условно - от того, что использует алгоритм проверки когда отвергает слово

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

[dmitgu]

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

Я всё еще не понимаю, что такое "слово, которого нет".

Вот такое впечатление, но не могу его сейчас тщательно продумать – пока работа в приоритете:

Если есть язык $L_1$ со словами

$t, s$

и алгоритм проверки $V(t, s, y)$ соответствующий алгоритму проверки класса $NP$ для языка $L_1$, то если слова вида

$t_1, s$

не принадлежат языку $L_1$ для произвольных $s$ и время работы алгоритма $V(t_1, s, y)$ полиномиально относительно размера $|t_1|$, то у нас есть язык $L_2$ - тоже класса $NP$ с тем же алгоритмом проверки $V(t, s, y)$ и вместо слов (многих)

$t_1, s$, не принадлежащих языку $L_1$

ему (языку $L_2$) не принадлежит слово (одно)

$t_1$

А сертификатами, которые не подтверждают это слово выступают все наборы $s, y$

То есть, мы можем неполиномиально сильно «ужать» (по размеру и по количеству) некоторые слова, «которых нет» в языке, опираясь всего лишь на некоторые особенности работы алгоритма проверки.

[mihaild]

Вы тут $NP$ и $coNP$ тут не путаете? Для $NP$ у нас сертификаты, подтверждающие принадлежность языку, для $coNP$ - опровергающие.

Что я пока что понял: у нас есть некоторый язык из $L_1$ из $NP$ (состоящий из пар слов), есть алгоритм $V$, распознающий $L_1$ с подсказкой, и есть множество (?) $T_1$ таких слов, что $V$ отвергает любую тройку вида $(t_1 \in T_1, s, y)$ за полиномиальное от $t_1$ время. Так?
В этом случае $T_1 \in coNP$ (причем можно подобрать $L_1$ такой, что $T_1$ будет $coNP$-полным).

[dmitgu]

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

Теперь – о свойствах языка $LS$.

Свойство 1 (верно, что):

$\exists s_{max} = (1, \exp(\operatorname{Len_S}(\overline{AntiSol})))^*:$

$q_{Anti}(|\overline{AntiSol}|, N_{Sol}) \le Y_{max}(|s_{max}|) \wedge Sol(\overline{AntiSol}, s_{max}) = 0$

$\Rightarrow \exists y = \operatorname{DoIt}(\overline{AntiSol}): \operatorname{Ls}(\overline{AntiSol}, s_{max}, y) = 1$

$\exists s_{max} = ...$ тут – это просто подстановка, в качестве которой берется строка из символов «1» с длиной, равной числу (пусть десятичному), которое находится внутри строки $\overline{AntiSol}$. Смысл не в подстановке, а в том, что при «достаточно быстрой» работе $\operatorname{Sol}(\overline{AntiSol}, s_{max})$ с результатом $0$ будет доказано как раз «не 0», а принадлежность слова $\overline{AntiSol}, s_{max}$ языку $LS$. При этом «достаточно быстро» тут (алгоритм $q_{Anti}(..., ...)$ является полиномом) – это даже не полиномиально малое количество шагов относительно размера $|\overline{AntiSol}|$, но того же уровня полиномиальности (определение дам чуть ниже), что и размер $|s_{max}|$ (то есть, экспоненциально дольше).

Максимальный размер доказательства $|y_{max}|$ при данном $|s_{max}|$ задаётся полиномом $Y_{max}(|s_{max}|)$.

Алгоритм $\operatorname{DoIt}(\overline{AntiSol})$ получает по утверждению $\overline{AntiSol}$ программный код алгоритма $\operatorname{Sol}(..., ...)$ и аргумент $s_{max}$, запускает $\operatorname{Sol}(\overline{AntiSol}, s_{max})$, переводит каждый шаг его работы в строки доказательства и в итоге получает доказательство результата его работы, а на базе этого – и доказательство для утверждения $AntiSol$ или для его отрицания.

Насчёт аргумента $s_{max}$ при работе $\operatorname{DoIt}(\overline{AntiSol})$ есть один нюанс: данный аргумент не генерируется, а его наличие эмулируется в силу его крайней примитивности. И при запуске $\operatorname{Sol}(\overline{AntiSol}, s_{max})$ (эмуляции работы) при каждом обращении к ячейке памяти, где должен находится $s_{max}$ возвращается символ «1». Поэтому времени на «создание» $s_{max}$ тратится не больше, чем уходит шагов $N_{Sol}$ на работу $ Sol(\overline{AntiSol}, s_{max})$ – каким бы гигантским по своим размерам не был этот $s_{max}$.

На самом деле в последнем равенстве Свойства 1 можно заменить $s_{max}$ на $s_i$,

где $i = |\operatorname{DoIt}(\overline{AntiSol})|$ и $s_i = (1, \operatorname{ArcY_{max}}(i))^*$

Понятно, что здесь $\operatorname{ArcY_{max}}(...)$ – это функция, обратная к $Y_{max}(...)$, из-за чего $\operatorname{ArcY_{max}}(i) < i$.

При этом $i$ оказывается в полиномиальных пределах относительно размера $|\overline{AntiSol}|$ и величины $N_{Sol}$.

и в конце Свойства 1 будет тогда такое равенство:

$\operatorname{Ls}(\overline{AntiSol}, \overline{\operatorname{Sol}(..., ...)}, s_i, y) = 1$

Но для этой замены в п. 6 потребуется поменять $s = ss(S)$ на:

$i \le |ss(S)| \wedge s = (1, i)^*$, что не нарушит свойств языка, а только расширит их.

Определение.

Алгоритмы $p_1(x_1, ... x_n)$ и $p_2(y_1, ... y_m)$ имеют одинаковый уровень полиномиальности своих результатов тогда и только тогда, когда имеются такие полиномы

$p_{1+}(...)$ и $p_{2+}(...)$, что верно:

$p_{1+}( p_1(x_1, ... x_n)) \ge p_2(y_1, ... y_m)$ и

$p_{2+}( p_2(y_1, ... y_m)) \ge p_1(x_1, ... x_n)$ – при любых аргументах в данных алгоритмах.

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

Из Свойства 1 видно, что не время работы алгоритма-решения

$\operatorname{Sol}(\overline{AntiSol}, s_{max})$

Зависит от размера слова, с которым оперирует алгоритм проверки

$\operatorname{Ls}(\overline{AntiSol}, \overline{\operatorname{Sol}(..., ...)}, s_i, y)$,

Но как раз наоборот – размер слова зависит от времени работы алгоритма-решения.

При этом заранее известно –

Свойство 2.

Остановка следующего алгоритма-решения с результатом 1 является ошибочным:

$\operatorname{Sol}(\overline{AntiSol}, s) = 1$ – не корректная работа при произвольном $s$.

Что означает, что при выполнении данного утверждения будет верным:

$\forall x \forall y \operatorname{Ls}(\overline{AntiSol}, x, s, y) = 0$

То есть, необходимое условие для корректности алгоритма-решения $\operatorname{Sol}(..., ...)$ является истинность утверждения:

$\forall s \operatorname{Sol}(\overline{AntiSol}, s) = 0$.

При этом данное утверждение вовсе не является достаточным для соответствия результата $0$ алгоритма-решения $\operatorname{Sol}(\overline{AntiSol}, ...)$ и непринадлежности слова $(\overline{AntiSol}, s_{max})$ языку $LS$ - что видно из Свойства 1.

И даже если $\operatorname{Sol}(\overline{AntiSol}, ...)$ проработает очень долго, но «примитивно» (будет пустой цикл крутить, например), то и в этом случае возникнут последствия, аналогичные Свойству 1.

Свойству 2 соответствует следующая информация от алгоритма проверки:

Свойство 3.

$\forall s \forall y \operatorname{Ls}(\overline{AntiSol}, \overline{\operatorname{Sol}(..., ...)}, s, y) = 0$, при этом $N_{\exists} \le p_{\exists}(|\overline{AntiSol}|)$, где

$N_{\exists} = N_{\operatorname{IsAnti}(t, a)}$, а последнее означает время работы (количество шагов) алгоритма проверки тогда, когда первый аргумент (проверяемое утверждение) совпадает с одним из «антиутверждений» для второго аргумента – содержащего программный код алгоритма, которому соответствует его «антиутверждение». Аргумент $s$ в этом случае не используется алгоритмом проверки – так как и без этого ясно, что алгоритм $\operatorname{Sol}(..., ...)$ не сможет стандартным способом подтвердить истинность $\overline{AntiSol}$ (не сможет выдать $1$ в качестве подтверждения принадлежности слова $\overline{AntiSol}, s$ языку $LS$).

Ранее я останавливался на свойстве 3 в своём доказательстве и видел достигнутую цель:

Алгоритм проверки выдаёт быстрый ответ о том, какой результат у алгоритма-решения (произвольного!) будет единственно правильным для некоторого конкретного утверждения – это Свойство 3. Но выдать этот результат, корректно данный алгоритм-решение может лишь за неполиномиально огромное количество шагов (зависящее от $s_{max}$ – неполиномиально большого относительно «быстрого» $N_{\exists})$ – это Свойство 1.

То есть – проверка решения оказывается неполиномиально быстрей самого решения и это – для произвольного алгоритма-решения. Это и есть «первопричина» появления красивой формулы $\mathbb{NP} \ne \mathbb{P}$, от красоты которой была забыта первоначальная цель найти язык с «трудными задачами», неразрешимыми полиномиально быстро (относительно времени проверки) никаким алгоритмом-решением.

Однако, по ходу формализации обнаружились (вроде бы) дефекты в самой постановке вопроса о сводимости класса $\mathbb{NP}$ к классу $\mathbb{P}$, аналогичные тем дефектам, которые обнаружились в постановке вопроса о способе разрешить логическую теорию. Эти обнаруженные дефекты были тогда представлены в теоремах Гёделя о неполноте. И, вроде бы, по аналогичным причинам можно всё-таки доказать и неравенство $\mathbb{NP} \ne \mathbb{P}$. Что я и попытаюсь в общих чертах сделать ниже (и из-за чего дополнительно «торможу» - дополнительно к недавнему отчётному периоду).

Аксиома рефлексии:

Собственный программный код алгоритма необходимо рассматривать в качестве данных, которыми этот алгоритм располагает, наряду и, в не меньшей степени, чем данные, которые он получает в своих аргументах.

Совершенно очевидная аксиома, которой мы пользуемся по 100 раз на дню, решая те задачи, которые адресованы именно нам и от которых зависимы именно мы, но при этом данная аксиома не была формализована в математике. Вот и исправим это упущение.

Заметим, что свойство 3 построено на базе свойства 2 и тесно связано с тем, что результат

$\operatorname{Sol}(\overline{AntiSol}, s) = 1$ - заведомо некорректен. Откуда корректным может быть только результат:

$\operatorname{Sol}(\overline{AntiSol}, s) = 0$.

Из аксиомы рефлексии мы видим, что алгоритм-решение:

$\operatorname{Sol}(\overline{AntiSol}, s)$

Располагает всей следующей информацией:

$\overline{AntiSol}, \overline{\operatorname{Sol}(..., ...)}, s$

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

$N_{\exists} \le p_{\exists}(|\overline{AntiSol}|)$,

означает, что данное «слово, которого нет» в языке $LS$ имеет вид:

$\overline{AntiSol}, \overline{\operatorname{Sol}(..., ...)}$ (будем называть его далее «персональным словом алгоритма $\operatorname{Sol}(..., ...)»)$

И на этом основании, если алгоритм $\operatorname{Sol}(..., ...)$ сводит язык $LS$ к классу $\mathbb{P}$ он должен дать ответ:

$\operatorname{Sol}(\overline{AntiSol}, s) = 0$ за время $N_{\exists +} \le p_{\exists +}(|\overline{AntiSol}|)$.

Но при этом возникает коллизия со словом:

$\overline{AntiSol}, s_{max}$ (будем называть его далее «общим словом»)

Которое в силу Свойства 1 при достаточно большом размере $|\overline{AntiSol}|$ должно принадлежать языку $LS$. В самом деле, условие:

$q_{Anti}(|\overline{AntiSol}|, N_{Sol}) \le Y_{max}(|s_{max}|)$

будет выполнено для достаточных больших $|\overline{AntiSol}|$, так как там же (Свойство 1):

$s_{max} = (1, \exp(Len_S(\overline{AntiSol})))^*$

И правая часть неравенства у нас тут растёт экспоненциально быстрее левой (где $N_{Sol} \le p_{\exists +}(|\overline{AntiSol}|)$), что неизбежно сделает неравенство истинным начиная с какого-то момента.

Но, в чём состоит коллизия? В том, что с точки зрения принадлежности языку $LS$ слова

$\overline{AntiSol}, s_{max}$

Алгоритм-решение:

$\operatorname{Sol}(\overline{AntiSol}, s_{max})$

Должен вернуть $1$?

Это «должен» опирается на условные договорённости о соответствии тому классу $\mathbb{P}$, в котором алгоритм проверки для принадлежащего языку слова всегда выдаёт $1$. Что, кстати, вовсе не является единственным способом построения класса, в котором за полиномиальное количество шагов от размера слова можно вычислять (не)принадлежность слова языку. А как обстоят дела с точки зрения не условных договорённостей, а логики?

А логика говорит вот что (из Свойства 1):

$( \operatorname{Sol}(\overline{AntiSol}, s_{max}) = 0 \wedge q_{Anti}(|\overline{AntiSol}|, N_{Sol}) \le Y_{max}(|s_{max}|) )$

$\Rightarrow (\overline{AntiSol}, s_{max}) \in LS$

То есть, при достаточно быстрой работе $\operatorname{Sol}(\overline{AntiSol}, s_{max})$ его результат $0$ может означать только одно – принадлежность слова $\overline{AntiSol}, s_{max}$ языку $LS$. И это – логика, а не условные договорённости. А логика – выше условных договорённостей. $\operatorname{Sol}(\overline{AntiSol}, s_{max})$ не ищет «со стороны» ответ о (не)принадлежности слова $\overline{AntiSol}, s_{max}$ языку $LS$, а делает нечто противоположное: Алгоритм-решение $\operatorname{Sol}(\overline{AntiSol}, s_{max})$ делает («насильственно», а не констатирует как «сторонний наблюдатель») слово $\overline{AntiSol}, s_{max}$ принадлежащим или не принадлежащим языку $LS$.

И у нас правая часть импликации (заключение) вовсе не независима от левой (посылки) – если правая часть станет противоположной, то и левая часть тоже превратиться в своё отрицание (в соответствии с правилом контрапозиции):

$(\overline{AntiSol}, s_{max}) \notin LS \Rightarrow ( \operatorname{Sol}(\overline{AntiSol}, s_{max}) = 1 \vee q_{Anti}(|\overline{AntiSol}|, N_{Sol}) > Y_{max}(|s_{max}|) )$.

Разумеется, причинно-следственные связи в детерминированном мире имеют смысл только в контексте переменной на месте $\overline{\operatorname{Sol}(..., ...)}$. Ведь в детерминированном мире всё является в некотором смысле окончательным и различие можно понять лишь в плане сравнения. И вот для разных $\overline{\operatorname{Sol}(..., ...)}$ и соответствующих им $\overline{AntiSol}$ мы и имеем то, что можно назвать причинно-следственными связями. Но для каждого конкретного $\overline{\operatorname{Sol}(..., ...)}$ никаких вариаций в детерминированном мире нет. А вот для множества $\overline{\operatorname{Sol}(..., ...)}$ есть вполне определённые закономерности.

То есть, при быстром ответе логика требует от нас считать результат $0$ алгоритма-решения $\operatorname{Sol}(\overline{AntiSol}, s_{max})$ признаком принадлежности слова $(\overline{AntiSol}, s_{max}) \in LS$ – при корректном значении $s_{max}$, разумеется (пояснения в следующем абзаце). И для слова $\overline{AntiSol}, s_{max}$ действительно появляется доказательство в этом случае. Но, разумеется, результат $0$ расходится с тем, что изначально требовалось для сведения нашей задачи к классу $\mathbb{P}$.

Оговорка про «при корректном значении $s_{max}$» довольна интересна. Отчасти проверка оказывается «внешней» по отношению к алгоритму $\operatorname{Sol}(..., ...)$ в разбираемом случае – но это очевидно уже по тому, что в отношении «специального слова» результат $0$ теперь несёт «специальный» смысл. При всём при этом полиномиальность времени проверки – с учётом «внешней» части – относительно размера $|\overline{AntiSol}|$ не нарушается, вообще говоря. В обсуждении Свойства 1 было сказано:

$\operatorname{Ls}(\overline{AntiSol}, \overline{\operatorname{Sol}(..., ...)}, s_i, y) = 1$

где $i = |\operatorname{DoIt}(\overline{AntiSol})|$ и $s_i = (1, \operatorname{ArcY_{max}}(i))^*$.

При этом $i$ оказывается в полиномиальных пределах относительно размера $|\overline{AntiSol}|$ и величины $N_{Sol}$.

А поскольку и $N_{Sol} \le p_{\exists +}(|\overline{AntiSol}|)$ в полиномиальных пределах относительно размера $|\overline{AntiSol}|$ при корректной работе $\operatorname{Sol}(..., ...)$, то всё оказывается в полиномиальных пределах относительно этого $|\overline{AntiSol}|$.

Мы рассмотрели случай, когда решение алгоритма $\operatorname{Sol}(..., ...)$ нацелено на персональное слово и результат получен полиномиально быстро относительно его размера. Тогда для персонального слова соблюдены условности в понимании смысла $1$ (слово принадлежит языку) и $0$ (слово не принадлежит языку). А для общего слова эти условности тогда отменены логикой. И по этой причине алгоритм $\operatorname{Sol}(..., ...)$, нацеленный на персональное слово, не может стать алгоритмом проверки языка $LS$ – если бы язык $LS$ принадлежал классу $\mathbb{P}$.

Если же решение нацелено на общее слово, то ответ получается неполиномиально долгим относительно размера персонального слова (очевидно из Свойства 1) и это - факт, который ничто не отменяет. И в этом случае алгоритм $\operatorname{Sol}(..., ...)$ оказывается не способным давать ответы за время, полиномиальное относительно размера персонального слова. То есть – тоже не может стать алгоритмом проверки языка $LS$ – если язык $LS$ принадлежит классу $\mathbb{P}$. При этом такое «затягивание времени» принципиальным образом изменяет ситуацию в сравнении со случаем полиномиально быстрого ответа относительно размера персонального слова – общее слово перестаёт принадлежать языку $LS$.

В предыдущих 2-х абзацах мы рассмотрели все возможные варианты ответа алгоритма $\operatorname{Sol}(..., ...)$ которые можно было «подозревать» как допускающие сводимость языка $LS$ к классу $\mathbb{P}$ посредством алгоритма $\operatorname{Sol}(..., ...)$ и убедились в обратном.

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

Проще, конечно, было бы, если бы результат $\operatorname{Sol}(\overline{AntiSol}, s) = 0$ так же прямо приводил к $(\overline{AntiSol}, s_{max}) \in LS$, как $\operatorname{Sol}(\overline{AntiSol}, s) = 1$ приводит к $(\overline{AntiSol}, s_{max}) \notin LS$. Но и вариант с 2-мя словами приводит к невозможности для $\operatorname{Sol}(..., ...)$ выполнить все требования, которые необходимо выполнить, чтобы считать его алгоритмом проверки языка класса $\mathbb{P}$.

Впрочем, нельзя не отметить гораздо более принципиальный и интересный результат, чем $\mathbb{NP} \ne \mathbb{P}$. Это – аксиома рефлексии. И она позволяет понять, кстати, какой из вариантов ответа $\operatorname{Sol}(\overline{AntiSol}, s) = 0$ является правильным в принципе, а не с точки зрения соответствия классу $\mathbb{P}$ (оба не соответствуют):

1. Быстрый ответ, основанный на размере персонального слова или

2. Медленный ответ, нацеленный на то, чтобы слово $(\overline{AntiSol}, s_{max}) \notin LS$ и соответствовало результату $\operatorname{Sol}(\overline{AntiSol}, s) = 0$.

Правильным, безусловно, является 1-й вариант. (20 тыс. знаков не хватило на последние абзацы, но они и не имеют прямого отношения к сказанному)

[dmitgu]

Всё-таки допишу остаток.

Правильным, безусловно, является 1-й вариант. Потому что он не нарушает требований на скорость ответа относительно максимально возможной (полиномиальной) скорости относительно достаточной для решения истинной информации. А нарушение условностей о смысле, придаваемым результатам $1$ и $0$ оправдано требованиями логики. А вот факт скорости работы никакая логика отменить не в силах. Логика выше условностей, но факты – выше логики (если есть несоответствие с действительными фактами, то ошибки в теории, а не в фактах).

Приведу пример:

«Можно ли завести в крепость нужные запасы и людей до подхода неприятеля?» Если этот вопрос стоит перед комендантом и в рамках его полномочий возможностей не хватает, то он может, конечно, довести дело до неготовности крепости и сдать её. Тогда ответ на вопрос, который должен дать комендант, совпадёт с тем, что скажут все остальные – «Крепость было невозможно спасти» (подразумевая «… с таким комендантом»). А если он заявит о собственной неспособности подготовить крепость в рамках своей компетенции, то «увы» - вмешаются более высокопоставленные лица и вопрос, видимо, будет решён, а крепость - спасена. Но его личный ответ (о неспособности защитить крепость) при этом окажется «ошибочным» в сравнении с результатом. Но зато его ответ был оперативным и правильным в отношении своих возможностей – а это настолько более срочно и приоритетно, насколько приоритетней возможность быть «глупее некоторых» и живым в сравнении с тем, чтобы стать расстрелянным «умником».

Если алгоритм-решение не игнорирует «своё» персональное слово, создавая «специфический» смысл для собственного результата $0$ в отношении общего слова, то это не мешает, ему, кстати, предсказывать правильное доказательство для общего слова: С помощью алгоритма $\operatorname{Ls}(..., ..., ..., ...)$ алгоритм $\operatorname{Sol}(\overline{AntiSol}, s_i)$ вполне мог предсказать, какое доказательство для утверждения $AntiSol$ будет построено после того, как он выдаст логичный в данном случае результат $0$. Так же и мы умеем точно предсказывать последствия своих действий, если исходим из правильных посылок, думаем логично и действуем по плану.

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

[Xaositect]

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

Теперь – о свойствах языка $LS$.

Насколько я помню, мы в прослый раз так и не разобрались, что за язык $LS$ такой. Вы написали, что язык $LS$ "соответсвует алгоритму $\mathrm{Ls}$", но я так и не понял, каким образом соответствует.
Напишите четко, из каких слов состоит язык $LS$.

[dmitgu]

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

Насколько я помню, мы в прослый раз так и не разобрались, что за язык $LS$ такой. Вы написали, что язык $LS$ "соответсвует алгоритму $\mathrm{Ls}$", но я так и не понял, каким образом соответствует.
Напишите четко, из каких слов состоит язык $LS$.

Слова:
$t, s$ - "общие слова". (в п. 6 им соответствовали слова $t, S, \overline{-}, s$). Здесь $t$ - утверждение, доказуемое в Пеано доказательством в пределах допустимого размера, $s$ - параметр размера доказательства (доказательство может быть ещё больше, но лишь полиномиально)

$t, a, s$ - "персональные слова". (в п. 6 им соответствовали слова $t, S, a, s$). Здесь $a$ - программный код "алгоритма-решения", к которому эти "персональные слова" относятся

И - важный нюанс, слова "персональные", которые не принадлежат и имеют специальный вид:

$\overline{AntiSol}, \overline{Sol(..., ...)}$ - для того, чтобы их отвергнуть, алгоритму проверки "не интересен" аргумент $s$, так как $Sol(..., ...)$ заведомо не способен подтвердить результатом 1 доказуемость $AntiSol$. Это в п. 6 я не формулировал.

[dmitgu]

Я допустил опечатки, указывая лишний (в соответствующем контексте нужно 3, а не 4 аргумента) аргумент в алгоритме $\operatorname{Ls}(..., ..., ...)$ – лишний аргумент $\overline{\operatorname{Sol}(..., ...)}$ – в 4-х местах. Привожу правильные варианты:

1. При обсуждении Свойства 1 -

и в конце Свойства 1 будет тогда такое равенство:

$\operatorname{Ls}(\overline{AntiSol}, s_i, y) = 1$

2. В Свойстве 2 -

Что означает, что при выполнении данного утверждения будет верным:

$\forall x \forall y \operatorname{Ls}(\overline{AntiSol}, x, s, y) = 0 \wedge \operatorname{Ls}(\overline{AntiSol}, s, y) = 0$

3. Когда ссылался на Свойство 1 при обсуждении специфического смысла 0 и «внешней проверки» $s_{\max}$ -

... В обсуждении Свойства 1 было сказано:

$\operatorname{Ls}(\overline{AntiSol}, s_i, y) = 1$

4. В предпоследнем абзаце -

... С помощью алгоритма $\operatorname{Ls}(..., ..., ...)$ алгоритм $\operatorname{Sol}(\overline{AntiSol}, s_i)$ вполне мог предсказать, ...

-- 13.11.2017, 12:24 --

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

Что я пока что понял: у нас есть некоторый язык из $L_1$ из $NP$ (состоящий из пар слов), есть алгоритм $V$, распознающий $L_1$ с подсказкой, и есть множество (?) $T_1$ таких слов, что $V$ отвергает любую тройку вида $(t_1 \in T_1, s, y)$ за полиномиальное от $t_1$ время. Так?
В этом случае $T_1 \in coNP$ (причем можно подобрать $L_1$ такой, что $T_1$ будет $coNP$-полным).

Гм... Нет, не $coNP$, вроде. В $T_1$ алгоритм проверки работает аналогично классу $P$ - что частный случай и для $NP$ и для $coNP$. И отвергнутая тройка из $T_1$ - соответствует невозможности соответствующего алгоритма-решения подтвердить соответствующую двойку. То есть алгоритм-решение становится аналогичен сертификату и его результат $0$ означает "не могу подтвердить, что слово $w \in LS$", а не "слово $w \notin LS$".

[dmitgu]

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

отвергнутая тройка из $T_1$

Вообще-то это двойка $\overline{AntiSol}, \overline{\operatorname{Sol}(..., ...)}$, так как аргументами $s, y$ в данном случае $Ls(..., ..., ..., ...)$ "не интересуется". И это "персональное слово" для $\operatorname{Sol}(..., ...)$, которое соответствует невозможности для него подтвердить результатом $1$ ни для какого $s$ что:

$(\overline{AntiSol}, s) \in LS$, для чего должен был бы найтись $y$: $Ls(\overline{AntiSol}, s, y) = 1$. Но такой $y$ заведомо не найдётся, если $\operatorname{Sol}(\overline{AntiSol}, s) = 1$ (Свойство 2).

[mihaild]

dmitgu, давайте договоримся, что вы всё-таки не будете писать тексты длиннее трех абзацев. Пока что я не помню ни одного случая, чтобы вы написали столько и не возникло вопросов - а текст, идущий после места, к которому есть вопрос, всё равно бесполезен.

Зафиксировано: post1256513.html#p1256513

Обсуждается
Определение языка $LS$ (про который потом будет сказано, что он принадлежит $NP \setminus P$).

-- 13.11.2017, 12:13 --

Что я пока что понял:
язык $LS$ строится как $(A \cup B) \setminus C$, где
$A$ состоит из слов вида $\overline{t, s}$, где $s$ - строка из единиц, $t$ - теорема арифметики, для которой существует доказательство не длиннее $|s|^n$ ($n$ - некоторая мировая константа)
$B$ состоит из слов вида $\overline{t, a, s}$, где $\overline{t, s} \in A$, $a$ - некоторый алгоритм. От $a$ что-то здесь зависит, или любой алгоритм сойдет?
$C$ состоит из слов вида $\overline{AntiSol, Sol(\ldots, \ldots)}$ (что это такое - я пока не понимаю, если с $A$ и $B$ согласны - напишите, пожалуйста, минимальное количество информации про них, необходимое для определения - например, хотя бы что это такое - алгоритмы? утверждения? что-то еще?)