2014 dxdy logo

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

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




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


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

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


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

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

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

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


18/05/14
215
Москва
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$-заглавная. Может, это и избыточно, но вроде, категоричности от нас никто не просит. С практической стороны, кстати, в языках программирования ситуация аналогична - в памяти, которая соответствует строке, хранится не только строка, как последовательность символов, но и отдельно от неё ещё и размер строки в бинарном виде. И время на вычисление размера строки - это время на получение этого готового числа, а не время перебора всех её символов.

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


16/07/14
8346
Цюрих
(не буду комментировать и разбираться в "идейной" части, об определениях $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 писал(а):
Между прочим, "прописная" и "заглавная" - это одно и тоже. Вы, скорее всего, имели в виду "строчная".

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


18/05/14
215
Москва
mihaild в сообщении #1273148 писал(а):
$LS = A \cup B \setminus C$
Так?


Да.

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


16/07/14
8346
Цюрих
Добавил в post1256513.html#p1256513

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

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


18/05/14
215
Москва
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$, которые сейчас приводятся в учебниках.

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


16/07/14
8346
Цюрих
dmitgu в сообщении #1273191 писал(а):
мы неявно пересмотрели то, что представляет собой неравенство $NP \ne P$ для нашего случая - если сравнивать с «обычными» языками класса $NP$, которые сейчас приводятся в учебниках
Мы так не договаривались. Мы договорились об определениях $P$ и $NP$ - post1256513.html#p1256513

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

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


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

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


16/07/14
8346
Цюрих
dmitgu в сообщении #1273204 писал(а):
Не в отдельном языке дело, а в конструкции из них )
Этого не может быть, потому что
mihaild в сообщении #1273199 писал(а):
$P$ замкнуто относительно теоретико-множественных операций

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

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

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

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


18/05/14
215
Москва
mihaild в сообщении #1273211 писал(а):
$P$ замкнуто относительно теоретико-множественных операций

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

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

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


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

-- 08.12.2017, 19:05 --

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

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


16/07/14
8346
Цюрих
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$.

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


18/05/14
215
Москва
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}$ недоказуемым.

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


16/07/14
8346
Цюрих
dmitgu в сообщении #1273227 писал(а):
он ищет ответ
Что значит "алгоритм ищет ответ"?

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

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


18/05/14
215
Москва
mihaild в сообщении #1273228 писал(а):
Термин "корректный ответ алгоритма" не определен.


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

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

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



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

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


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

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