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

[mihaild]

Определены термины "алгоритм распознает данный язык" и "алгоритм полиномиален".

Давайте я попробую начать рассуждение, а вы продолжить.

Пусть $T$ - алгоритм, распознающий $LS$ за полиномиальное время. Тогда существует слово $w$, такое что ...

[dmitgu]

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

Пусть $T$ - алгоритм, распознающий $LS$ за полиномиальное время. Тогда существует слово $w$, такое что ...

Такое, что этот алгоритм распознать (не)принадлежность слова $w$ языку $LS$ НЕ способен, так как:
Выдавая $1$ про слово $w$, алгоритм-решение делает слово $w \notin LS$, а выдавая $0$ – делает $w \in LS$.

Вот так всё просто – алгоритм $\operatorname{Sol}$ в принципе не может дать правильный ответ для некоторых слов языка $LS$. И не имеет значения, какой это будет ответ – $1$ или $0$ (остальные заведомо не корректны).

Собственно, само построение языка я «срисовал» из формальной логики, Новое – аксиома рефлексии. Когда за счёт слова $w’$ ($w’ \in C \wedge w = (\overline{Sol(..., ..., ...)}, \overline{Anti_{\operatorname{Sol}, S}}, S)$ для которого $Ls(w’) = 0$) «быстро» ясно, что $\operatorname{Sol}(\overline{Anti_{\operatorname{Sol}, S}}, S, s)$ не сможет подтвердить принадлежность $w = ( \overline{Anti_{\operatorname{Sol}, S}}, S, s )$ языку $LS$.

То есть – результат $1$ для $\operatorname{Sol}(\overline{Anti_{\operatorname{Sol}, S}}, S, s)$ будет не верен и это известно «быстро» (полиномиально от $|w’|$)!

Но если выдавать противоположный результат, чем $1$ с полиномиальной скоростью относительно $|w’|$, то это – $0$. И он тоже не отвечает стандартам $P$ при $\operatorname{Sol}(\overline{Anti_{\operatorname{Sol}, S}}, S, ss(S))$. А раз $\operatorname{Sol}$ – произволен, то ни один алгоритм-решение не отвечает стандартам $P$. Поэтому $NP \ne P$. Простое доказательство. Простое, после того, конечно, как найдена и использована аксиома рефлексии.

[mihaild]

Алгоритм не может "делать $w \in LS$", т.к. $LS$ уже зафиксирован и изменению не подлежит.

Вы можете явно выписать $w$ в зависимости от $T$? (ну или небольшой набор, в котором заведомо найдется "плохое" слово)

[dmitgu]

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

Алгоритм не может "делать $w \in LS$", т.к. $LS$ уже зафиксирован и изменению не подлежит.

Зафиксирован так, что 1 и 0 соответствуют $w \notin LS$ и $w \in LS$ соответственно - при соответствующей скорости ответа $T$ - который и есть $Sol$. И это соответствие - противоположно тому, что необходимо для возможности распознать слово $w$ алгоритмом $Sol$.

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

Вы можете явно выписать $w$ в зависимости от $T$?

Да:

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

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

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]

А что такое $Sol$ тут? Тот алгоритм, про который мы доказываем, что он не распознает язык?
Во втором пункте, видимо, порядок аргументов перепутан.

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

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

Я не понимаю, что это значит.

Второе слово принадлежит языку $C$. Первое, в зависимости от деталей, может принадлежать, а может не принадлежать $A$.
Например, можно взять простой алгоритм, отвергающий $C$ и принимающий всё остальное (просто применяем теорему о неподвижной точке и проверяем результат на синтаксическое равенство первому аргументу) так, чтобы это было легко доказуемо - тогда $Anti_{Sol, S}$ будет иметь короткое доказательство, первое слово будет принадлежать $A$ и приниматься - т.е. на приведенных вами двух словах алгоритм работает корректно.
(или можно попробовать взять какой-нибудь алгоритм, который сложнодоказуемо отвергает вообще всё)

[george66]

Докажите лучше равенство.

[dmitgu]

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

А что такое $Sol$ тут? Тот алгоритм, про который мы доказываем, что он не распознает язык?
Во втором пункте, видимо, порядок аргументов перепутан.

Да, тот самый. И он произвольный. Порядок могу и перепутать, по именам всё равно ясно. Мы договорились о порядке? Может, забыл.

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

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

Я не понимаю, что это значит.

Слово языка $C$ не принадлежит $LS$. Если $s \ne ss(S)$, то это некорректно составленное слово языка $A$, тоже не принадлежит. А для корректного по синтаксису $S$ и $s$ слова ответ $1$ от $Sol$ сделает верным $\not Anti_{Sol, S}$ и, соответственно, недоказуемым $Anti_{Sol, S}$ (язык $LS$ на базе непротиворечивой теории 1-го порядка).

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

можно взять простой алгоритм, отвергающий $C$

Мы рассматриваем алгоритм $Sol$. И будет ли иметь доказательство $Anti_{Sol, S}$ - зависит только от работы этого алгоритма (так построено утверждение). Для любого другого алгоритма $Sol_2$ есть свои утверждения $Anti_{Sol_2, S}$, которые и он не сможет "расколоть" - для достаточно большого $S$.

Про то, как ответ $0$ приводит к наличию доказательства (если ответ достаточно быстрый) - тоже было рассмотрено.

george66 в сообщении #1273793 писал(а):

Докажите лучше равенство.

Про какое равенство Вы спрашиваете?

И, наверно, пойду спать, извиняюсь если не отвечу сразу, а то завтра много работы. Хорошего! )

[george66]

Что $P=NP$. От неравенства пользы никакой.

[mihaild]

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

Мы договорились о порядке? Может, забыл

http://dxdy.ru/post1256513.html#p1256513

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

А для корректного по синтаксису $S$ и $s$ слова ответ $1$ от $Sol$

Для какого слова?

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

Про то, как ответ $0$ приводит к наличию доказательства (если ответ достаточно быстрый) - тоже было рассмотрено.

Не заметил. Можете расписать? (только желательно в строгих формулировках)

(и да, учтите, что мы требовали доказательства длины $q(n)$ в определении $A$ - а наш алгоритм может работать и дольше, лишь бы полиномиально)

[dmitgu]

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

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

писал(а):
А для корректного по синтаксису $S$ и $s$ слова ответ $1$ от $Sol$ Для какого слова?

$Anti_{Sol, S}, S, ss(S)$

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

mitgu в сообщении #1273798

писал(а):
Про то, как ответ $0$ приводит к наличию доказательства (если ответ достаточно быстрый) - тоже было рассмотрено. Не заметил. Можете расписать? (только желательно в строгих формулировках)

Да:

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

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$ для этого).

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

(и да, учтите, что мы требовали доказательства длины $q(n)$ в определении $A$ - а наш алгоритм может работать и дольше, лишь бы полиномиально)

А вот и нет ) У нас такой язык, что ответы - согласованы ( post1272430.html#p1272430 ). В этом и фишка. Мы заранее знаем, что ответ 1 невозможен для $\operatorname{Sol}(\overline{Anti_{\operatorname{Sol}, S}}, S, ss(S))$ сразу для 2-х слов и ответить должен полиномиально относительно кратчайшего из них.

Для алгоритма $\operatorname{Sol}(t, S, ss(S))$ распознать (не)принадлежность слова $w \in A \wedge w = (t, S, ss(S))$ к языку $LS$ в соответствии со стандартами алгоритма распознания языка класса $P$, это значит:
1. выдать $1$, в случае, если $w \in LS$;
2. выдать $0$, в случае, если $w \notin LS$;
3. Про время скажем отдельно.
А что касается распознания непринадлежности слова $w’ \in C \wedge w' = (\overline{Anti_{\operatorname{Sol}, S}}, \overline{Sol(..., ..., ...)}, S)$ к языку $LS$ в соответствии со стандартами алгоритма распознания языка класса $P$, это значит:
1. выдать $1$ – не вариант, заведомо не принадлежит;
2. выдать $0$, так как $w' \notin LS$;
3. Количество шагов работы программы на ответ – полиномиально относительно размера $|w’|$.
Поскольку распознание обеих слов должно быть одновременным (слова согласованы), то меньшее время во 2ом случае (при достаточно больших $S$) устанавливает требование и для 1-го случая. (Слова согласованы).

[mihaild]

Во-первых, посмотрите пожалуйста внимательно на согласованные определения - post1256513.html#p1256513 - у меня после перечитывания возникло ощущение, что что-то там не так: языки $A$ и $C$ сильно отличаются по структуре - слова из $A$ заканчиваются на унарную строку, слова из $C$ - на бинарную; язык $B$ вообще непонятно зачем нужен (и он состоит из четверок слов, а $A$ и $C$ из троек).

Во-вторых, я не знаю, что такое "согласованные ответы" или "согласованные слова".

Давайте еще медленнее.
Мы берем некоторый алгоритм $Sol$, работающий за время $p$ от длины входа. Мы хотим найти либо слово из языка $LS$ такое, что он на нем выдает $0$, либо слово не из языка $LS$, такое, что он на нем выдает $1$. Так?
Если да - то можете ли вы явно выписать небольшой набор слов, среди которых будет нужное? (пока без доказательств, просто зафиксировать, что будем доказывать дальше)

[dmitgu]

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

Мы берем некоторый алгоритм $Sol$, работающий за время $p$ от длины входа.

Не обязательно. Дело в том, что для $Sol$ нет нужды анализировать $s$, если он имеет дела с
$Anti_{Sol, S}$ и $S$. Уже по этой информации известно, что он не может найти подтверждение слова - любого из двух. То есть, с т.з информации о слове для $Sol$ оно - короткое и информация в обеих словах - об одном и том же. Они "согласованы" - т.е. несут одинаковую информацию. Пусть даже он проработает "очень" долго - полиномиально от размера:

$|(\overline{Anti_{Sol, S}}, S, s)|$
и вернёт $0$. Ничего другого при своей корректной работе он вернуть и не может. Но так это было "сразу" известно из:
$(\overline{Anti_{Sol, S}}, \overline{\operatorname{Sol}(..., ..., ...)}, S)$. И получается, что он работал неполиномиально долго относительно размера наиболее короткой полной информации.

[mihaild]

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

И получается, что он работал неполиномиально долго относительно размера наиболее короткой полной информации.

Перечитайте определение $P$. Время работы считается относительно входа, никакой "наиболее короткой информации" там нет.

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

[dmitgu]

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

Перечитайте определение $P$. Время работы считается относительно входа, никакой "наиболее короткой информации" там нет.

Да ради Бога ) Будто бы если он опирается на слово языка $C$ он будет смотреть слово языка $A$. Не давайте ему на вход $s$ - и все дела ) Чтоб ему понять, что доказательства он найти не сможет - ему нет нужды вообще смотреть $s$. А если он выдаст 1, так он вообще испортит все доказательства, "убьёт" их. Поэтому $0$ для него про слово языка $C$ - это что-то вроде "не убий" про слово языка $A$ )

А что Вы думаете, вот получил он на вход $s$, отработал слово языка $C$ за полиномиальное время от его размера, закончил, но до этого он ещё и пробежал всё слово $s = ss(S)$ ? Конечно, нет! Это неполиномиально долго и он просто не успел бы. И поэтому эта $s$ ничем не отличается от того, которое он просмотрит за полиномиальное количество шагов от размера $|S|$. И нет никакой разницы какая у входа длина, если он всё равно может быть обрезан без последствий для работы.

Поэтому думать мы всё-таки будем ))) Используя, а не "ограничиваясь" ) Я про это:

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

И давайте всё-таки ограничимся строгими формулировками

[mihaild]

Из последнего сообщения я не понял ничего, но, видимо, и не предполагалось.

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