2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 15, 16, 17, 18, 19, 20, 21 ... 26  След.
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение18.10.2017, 15:24 
Аватара пользователя


18/05/14
215
Москва
mihaild в сообщении #1256562 писал(а):
У любого конкретного слова есть размер.


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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение18.10.2017, 15:31 
Заслуженный участник
Аватара пользователя


16/07/14
8334
Цюрих
dmitgu в сообщении #1256572 писал(а):
И чем тогда является "часть слова" $s$ - действительно частью слова или частью сертификата?
Я вообще не понимаю, что это значит. Можете переформулировать в терминах кортежей, кодирования и т.д.?

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение18.10.2017, 15:57 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение18.10.2017, 16:11 
Заслуженный участник
Аватара пользователя


16/07/14
8334
Цюрих
dmitgu в сообщении #1256592 писал(а):
И где Ваше "кроме того" - в котором ограничение от длины слова? По логике работы алгоритма проверки он отверг слово, в котором вообще нет части $s$ или оно нулевой длины.
Вот именно для этого нужны строгие определения. Что такое "логика алгоритма"?
Если хотите - можно рассматривать только входы какого-то определенного вида (кортежи нужной длины) и оценивать время работы в терминах отдельных элементов этих кортежей. Собственно у меня так и сделано.

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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение18.10.2017, 16:20 
Аватара пользователя


18/05/14
215
Москва
mihaild в сообщении #1256595 писал(а):
можете предложить свое определение $NP$, только строго


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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение18.10.2017, 16:47 
Заслуженный участник
Аватара пользователя


16/07/14
8334
Цюрих
dmitgu в сообщении #1256602 писал(а):
Согласны, что в учебнике с их "размером слов" есть явно тёмные места?
Нет, не согласен. Собственно стандартное определение (требующее просто полиномиальности по входу) мне нравится больше, чем сформулированное мной, но они эквивалентны.
dmitgu в сообщении #1256602 писал(а):
раз слово "которого нет" может быть неопределенной длины
Я всё еще не понимаю, что такое "слово, которого нет".

(Оффтоп)

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


-- 18.10.2017, 16:58 --

dmitgu в сообщении #1256602 писал(а):
Можно считать длину условно - от того, что использует алгоритм проверки когда отвергает слово
Пока я не понимаю, что это значит. Понятие "что прочитал алгоритм", конечно, определено, но не забудьте, что т.к. мы пока говорим о языках, а не об алгоритмах, все вводимые алгоритмы должны быть связаны какими-то кванторами.

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение19.10.2017, 00:35 
Аватара пользователя


18/05/14
215
Москва
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$

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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение19.10.2017, 03:44 
Заслуженный участник
Аватара пользователя


16/07/14
8334
Цюрих
Вы тут $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$-полным).

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение10.11.2017, 06:07 
Аватара пользователя


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

Теперь – о свойствах языка $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 тыс. знаков не хватило на последние абзацы, но они и не имеют прямого отношения к сказанному)

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение10.11.2017, 07:24 
Аватара пользователя


18/05/14
215
Москва
Всё-таки допишу остаток.

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

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

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

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

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

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение10.11.2017, 10:26 
Заслуженный участник
Аватара пользователя


06/10/08
6422
dmitgu в сообщении #1263936 писал(а):
Теперь – о свойствах языка $LS$.
Насколько я помню, мы в прослый раз так и не разобрались, что за язык $LS$ такой. Вы написали, что язык $LS$ "соответсвует алгоритму $\mathrm{Ls}$", но я так и не понял, каким образом соответствует.
Напишите четко, из каких слов состоит язык $LS$.

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение10.11.2017, 10:57 
Аватара пользователя


18/05/14
215
Москва
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 я не формулировал.

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение13.11.2017, 10:41 
Аватара пользователя


18/05/14
215
Москва
Я допустил опечатки, указывая лишний (в соответствующем контексте нужно 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$".

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение13.11.2017, 11:56 
Аватара пользователя


18/05/14
215
Москва
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).

 Профиль  
                  
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение13.11.2017, 12:03 
Заслуженный участник
Аватара пользователя


16/07/14
8334
Цюрих
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$ согласны - напишите, пожалуйста, минимальное количество информации про них, необходимое для определения - например, хотя бы что это такое - алгоритмы? утверждения? что-то еще?)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 384 ]  На страницу Пред.  1 ... 15, 16, 17, 18, 19, 20, 21 ... 26  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group