2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 9, 10, 11, 12, 13, 14, 15 ... 26  След.
 
 Re: NP≠P. Док-во от противного-контрпример алгоритмов из NP
Сообщение18.03.2017, 23:31 
Аватара пользователя


18/05/14
215
Москва
mihaild в сообщении #1201491 писал(а):
Вот это я не могу прочитать чисто синтаксически

Сейчас отвечу на более "глобальный" вопрос, может будет понятней. Ок?

Xaositect в сообщении #1201489 писал(а):
Я, честно говоря, так и не понял, что все эти Ваши алгоритмы делают. Напишите формально, какой язык $L$ и какое отношение $R$ будут у Вашей "нехорошей" задачи?


В предлагаемом языке «слову» соответствует теорема $t$, предельный размер доказательства для неё в 2-х представлениях $S$ и $s$, и аргумент долга (текст некоторого алгоритма-решения) $d$. Слово считается подтвержденным (существует «сертификат»), если длина строки $s$ равна числу $S$, имеется доказательство $y$ размером до $S$, и если теорема не равна утверждению $\overline{Anti(d, S) = 0}$ - это утверждение построено так, что алгоритм $d$ заведомо не может найти «сертификат» для него.

Скорость работы алгоритма проверки разная для разных случаев. Если имеет место $\overline{Anti(d, S) = 0}$, то полиномиальное ограничение на время работы $p_{Anti}(|d|, |S|)$ – что неполиномиально меньше чем у «общего» $Sph(d, t, S, s, y)$, чей ограничивающий полином – $p(|d|, |s|)$. Так как $|S|$ неполиномиально меньше, чем $|s|$.

Вы понимаете, что у нас есть 2 (Два) полиномиальных ограничения на время работы? Для задачи в целом он больше (дольше), а для подзадачи $Sph(d, \overline{Anti(d, S) = 0}, S, s, y)$ – он неполиномиально меньше. Меньшее может входить в большее, поэтому подзадача соответствует «общей» задаче и её полиномиальному ограничению, но для корректного «Эдипа» при решении вопроса о $\overline{Anti(d, S) = 0}$ «существует» такая задача из класса $NP$, которая неполиномиально быстрее «общей». И не выдать соответствующий быстрый ответ – значит, быть неспособным свести эту подзадачу из класса $NP$ к классу $P$.

А выдать быстро – значит, утратить соответствие (равенство результатов) между решаемой тобой задачей, соответствующей аргументу долга $\overline{Oed(\overline{Sph(..., ..., ..., ..., ...)}, \overline{-}, ..., ..., ...)}$ и такой же задачей, но в которой иной лишь аргумент долга – равный $\overline{-}$.

Я строю задачу, в которой любые алгоритмы-решения могут решать только «свои» задачи – потому что алгоритм-решение соответствует некоторой части «слова» разбираемого «языка». Но существенным (с иным результатом и/или ограничением на время работы проверки) этот нюанс становится лишь на утверждениях типа $\overline{Anti(d, S) = 0}$.

То есть – возврат 0 «Эдипом» при поиске сертификата для $\overline{Anti(d, S) = 0}$ – соответствует «языку». Хоть «Эдип» ищет доказательство для «слова» с теоремой $\overline{Anti(d, S) = 0}$ и аргументом долга
«объективно»,

но его работа соответствует аргументу долга
«Эдип с аргументом долга «объективно»».

Потому что дело не в том, для какого аргумента долга он ищет, а в том, «кто» ищет. Аргумент долга «Сфинкса» (то есть элемент слова в предлагаемом «языке») должен соответствовать фактам а не аргументу долга внутри «Эдипа».Так как: «Но словам ведь соответствуют понятия» (c) «Фауст». А частью «слова» у нас является алгоритм-решение с тем, что у него подставлено в качестве аргумента долга, а не то, что у него подставлено – независимо от самого алгоритма-решения.

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


06/10/08
6422
Нет, давайте начнем сначала, а то у меня уже по первым предложениям куча вопросов. Определяйте все понятия и обозначения.
dmitgu в сообщении #1201652 писал(а):
В предлагаемом языке «слову» соответствует теорема $t$, предельный размер доказательства для неё в 2-х представлениях $S$ и $s$, и аргумент долга (текст некоторого алгоритма-решения) $d$. Слово считается подтвержденным (существует «сертификат»), если длина строки $s$ равна числу $S$, имеется доказательство $y$ размером до $S$, и если теорема не равна утверждению $\overline{Anti(d, S) = 0}$ - это утверждение построено так, что алгоритм $d$ заведомо не может найти «сертификат» для него.
Теоремы и доказательства в какой теории рассматриваются? Зачем нужны 2 представления для размера, если по строке можно за полиномиальное время ($O(n\log n)$) вычислить ее длину? Что такое $Anti(d, S)$? Уверены ли Вы, что проверка, не равна ли теорема $\overline{Anti(d, S) = 0}$ полиномиальна по $d$? Почему исключается ровно одна теорема? Как-то сомнительно, что если какой-то алгоритм не найдет сертификат для одной теоремы, но найдет для всех остальных. Тем более, что $d$ - это часть принимаемого слова. Или тот факт, что $d$ не найдет сертификат, не важен?

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


18/05/14
215
Москва
Xaositect в сообщении #1201662 писал(а):
Теоремы и доказательства в какой теории рассматриваются?


Например, в какой-то расширенной теории Пеано - она способна "представлять" алгоритмы.
Xaositect в сообщении #1201662 писал(а):
Зачем нужны 2 представления для размера, если по строке можно за полиномиальное время ($O(n\log n)$) вычислить ее длину?


Чтобы добиться неполиномиальной разницы между полиномиальными ограничениями для задачи в целом и подзадачи.

Xaositect в сообщении #1201662 писал(а):
Что такое $Anti(d, S)$?

Алгоритм, который запускает d с текстом данной теоремы (о себе), ждет его результата и если это доказательство - то поступает вопреки результату доказательства. А если 0 ("не нашёл доказательство") то возвращает 0 - сделав утверждение о себе истинным.

Xaositect в сообщении #1201662 писал(а):
Уверены ли Вы, что проверка, не равна ли теорема $\overline{Anti(d, S) = 0}$ полиномиальна по $d$?

Конечно. Достаточно обнаружить такое утверждение, соответствующее $d$, чтобы сразу выдать $0$. А его размер зависит от размера аргумента долга и размера $|S|$. При этом $|s|$ или $y$ рассматривать не требуется - пусть они некорректны - это всё равно $0$.

Xaositect в сообщении #1201662 писал(а):
Почему исключается ровно одна теорема?

Достаточно и одной.

Xaositect в сообщении #1201662 писал(а):
Как-то сомнительно, что если какой-то алгоритм не найдет сертификат для одной теоремы, но найдет для всех остальных.

Как показано в общих чертах выше - $\overline{Anti(d, S) = 0}$ -Теорема построена так, что не найдёт.

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


06/10/08
6422
Так, я что-то вообще ничего не понимаю. У Вас $d$ - это часть входного слова, а не сертификата. Что будет, если я подам на вход алгоритм $d$, который не завершается?

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


18/05/14
215
Москва
Xaositect в сообщении #1201668 писал(а):
Так, я что-то вообще ничего не понимаю. У Вас $d$ - это часть входного слова, а не сертификата. Что будет, если я подам на вход алгоритм $d$, который не завершается?


Для него тоже будет верным невозможность найти доказательство $\overline{Anti(d, S) = 0}$. Но $0$ он не выдаст, хоть у "Сфинкса" информация об этом имеется - и будет не корректным. Да он вообще некорректный, поэтому не может свести $NP$ к $P$ как и прочие алгоритмы.

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


16/07/14
8342
Цюрих
dmitgu в сообщении #1201652 писал(а):
В предлагаемом языке «слову» соответствует теорема $t$, предельный размер доказательства для неё в 2-х представлениях $S$ и $s$, и аргумент долга (текст некоторого алгоритма-решения) $d$
Итого, мы формально рассматриваем язык из кортежей длины $4$:
$$L = \{(t, S, s, d) | t - \text{код теоремы}, t \neq \overline{Anti(d, S) = 0}, s - \text{число в двоичной записи}$$ $$ S = 1^n, d - \text{код какого-то алгоритма}$$ $$\exists y: |y| < s, y - text{доказательство чего-то}\}$$,
Уточните, какие тут требования на $d$ и что надо доказывать.

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


18/05/14
215
Москва
mihaild в сообщении #1201691 писал(а):
$$L = \{(t, S, s, d) | t - \text{код теоремы}, t \neq \overline{Anti(d, S) = 0}, s - \text{число в двоичной записи}$$ $$ S = 1^n, d - \text{код какого-то алгоритма}$$ $$\exists y: |y| < s, y - text{доказательство чего-то}\}$$


Гм... А чем Вам не нравится формализм, который перевёл Xaositec ?

От формализма мне нужно, чтобы было указано время работы алгоритма проверки. И меня смущает:

$t \neq \overline{Anti(d, S) = 0}$

словно такая теорема даже не попадает в рассмотрение. Но у нас есть подзадача с пустым языком. Однако пустой язык - тоже подразумевает алгоритм проверки и не всякий пустой язык принадлежит $NP$ или $P$.

В отличие от логики, где неполнота теории означает отсутствие каких-то теорем и их отрицаний, в теории алгоритма "нет" - это какой-то результат проверки, а не просто отсутствие $t$, который не равен $\overline{Anti(d, S) = 0}$.

Я извиняюсь что не сразу ответил и не очень качественно - у меня сейчас отчёты навалились (я бухгалтер) и не могу сконцентрироваться на хобби. А после общения с Вами и Xaositec удалось кое-что более ясно понять (спасибо Вам и Xaositec) - и в терминах языка (а не задачи) понятнее соответствие поиска ответа и его проверки. Возникли вроде интересные мысли, постараюсь разобраться - когда работа уменьшится. Ещё раз извиняюсь, что до конца марта могу сильно тормозить с ответами.

P.S. Кстати, у меня $S$ означает число, а $s$ - строка. Привычка из программирования где с маленьких $s$ часто начинаются строковые переменные или функции. И тогда $s = 1^S$, если я правильно Вас понял.

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


16/07/14
8342
Цюрих
dmitgu в сообщении #1202010 писал(а):
А чем Вам не нравится формализм, который перевёл Xaositec ?
Тем, что он не предложил формализм, а задал несколько вопросов.
А я попытался сделать большой шаг и угадать сразу пачку ответов (заодно показать, как должны выглядеть нормальные формулировки). Иногда такой подход (попробовать угадать) оказывается лучше, иногда - нет.
dmitgu в сообщении #1202010 писал(а):
не всякий пустой язык принадлежит $NP$ или $P$.
:facepalm: Пустой язык ровно один, и он принадлежит и $P$, и $NP$, и вообще любому классу, машины которого в состоянии прочитать вход и вывести ответ "нет". Язык - это просто множество слов.

dmitgu в сообщении #1202010 писал(а):
И меня смущает: $t \neq \overline{Anti(d, S) = 0}$
Ну возможно я угадал неправильно.
Определение $NP$: язык $L$ принадлежит $NP$, если существует такой полином $p$ и МТ $T$ двух аргументов, работающая полиномиальное время, что $x$ принадлежит языку $L$ в том и только в том случае, если существует слово $y$ длины не большей, чем $p(|x|)$, такое, что $T$ принимает $(x, y)$.
Полином как правило явно не выписывают (почти всегда "и так понятно", что там будет полином), а вот описать, что делает $T$, стоит.
Если я правильно вас понимаю, то в первую очередь проверяем, что слово $x$ кодирует четверку $(t, S, s, d)$ (если не кодирует - сразу отвергаем). Дальше можно уже работать с $t, S, s, d$ и $y$.
Например, проверим, что $s = 1^S$. Что еще?

Учтите, что $T$ уже обычная полиномиальная МТ, никой недетерменированности/подсказок/... у нее нет.

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


18/05/14
215
Москва
mihaild в сообщении #1202157 писал(а):
dmitgu в сообщении #1202010
писал(а):
А чем Вам не нравится формализм, который перевёл Xaositec ? Тем, что он не предложил формализм, а задал несколько вопросов.

Не только:
Xaositect в сообщении #1201483 писал(а):
Обозначение $\mathbf{NP}$ расшифровывается как "nondeterministic polynomial time", поскольку этот класс изначально определялся в терминах недерминированных машин. Однако сейчас обычно дается эквивалентное определение, использующее понятие проверяющего отношения - бинарного отношения $R \subset \Sigma^* \times \Sigma_1^*$ для некоторых конечных алфавитов $\Sigma$ и $\Sigma_1$. Каждому такому отношению мы ставим в соответствие язык в алфавите $\Sigma \cup \Sigma_1 \cup \{\sharp\}$ определяемый как $$L_R = \{w \sharp y \mid R(w, y) \},$$ где символ $\sharp$ не принадлежит языку $\Sigma$. Будем говорить, что $R$ проверяется за полиномиальное время, если $L_R \in \mathbf{P}$. Определим класс языков $\mathbf{NP}$ следующим образом: язык $L$ в алфавите $\Sigma$ принадлежит $\mathbf{NP}$ если и только если существует $k \in \mathbb{N}$ и проверяемое за полиномиальное время бинарное отношение $R$ такие, что для любого слова $w \in \Sigma^*$ $$w \in L \Leftrightarrow \exists y\,(|y| \leq |w|^k \text{ и } R(w, y)),$$ где $|w|$ и $|y|$ - длины слов $w$ и $y$ соответственно.


mihaild в сообщении #1202157 писал(а):
dmitgu в сообщении #1202010
писал(а):
не всякий пустой язык принадлежит $NP$ или $P$. :facepalm: Пустой язык ровно один, и он принадлежит и $P$, и $NP$, и вообще любому классу, машины которого в состоянии прочитать вход и вывести ответ "нет". Язык - это просто множество слов.

Совершенно не так. Возьмём, например соотношение для некоторого $R(x, y)$. Считаем переменные записаны в "стандартной интерпретации" - то есть $x$ единиц и $y$ единиц. У нас нет, вообще говоря, способа понять, возвращает $R(x, y)$ при каком-то $x$, $y$ результат кроме $0$. Действительно, пусть при $x < y$ будет $0$, а иначе считает как $H(x+y)$, в которой $H(x+y)$ - проверяет остановится ли некий алгоритм $A()$ на $x+y$ шаге и возвращает $0$, если не остановится, а если остановится на этом шаге, то $1$, а дальше снова ноль (и проверять даже не надо). Проблема остановки неразрешима. И если $A()$ не остановится, то у нас везде будет $0$. И язык будет пустым. А если остановится - то не пустым. У нас даже способа нет отличить пустой язык от непустого. А можно ставить в зависимость не от $x+y$, а от $\exp(x+y)$. И что - это будут одинаковые задачи? А если там везде $0$, то что - оба из класса $NP$ или не из $NP$? По Вашему же они одинаковы.

mihaild в сообщении #1202157 писал(а):
заодно показать, как должны выглядеть нормальные формулировки

:wink:

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


06/10/08
6422
dmitgu в сообщении #1202697 писал(а):
А если там везде $0$, то что - оба из класса $NP$ или не из $NP$? По Вашему же они одинаковы.
Именно так. Задача определения по коду машины, полиномиальная она или нет - неразрешима. Возможно, существуют языки из $\mathbf{P}$ (или $\mathbf{NP}$), для которых нельзя доказать, что они принадлежат $\mathbf{P}$ (или $\mathbf{NP}$).

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


18/05/14
215
Москва
Xaositect в сообщении #1202699 писал(а):
Возможно, существуют языки из $\mathbf{P}$ (или $\mathbf{NP}$), для которых нельзя доказать, что они принадлежат $\mathbf{P}$ (или $\mathbf{NP}$).


Разумеется, существуют: если единичная задача зависит от остановки некого алгоритма - то если он остановится, тогда полиомиальность массовой задачи не поменяется (это просто константа в полиноме - время на работу единичной задачи - пусть гигантское время), а если не остановится - то алгоритм проверки явно не ограничен полиномом.

Но если в моём предыдущем примере у нас зависимость о $x+y$ - то этот язык из $NP$, а если зависимость от $\exp(x+y)$ - то не из $NP$ - независимо от того, пустой это язык или нет. При стандартной модели интерпретации, естественно.

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


06/10/08
6422
dmitgu в сообщении #1202706 писал(а):
Разумеется, существуют: если единичная задача зависит от остановки некого алгоритма - то если он остановится, тогда полиомиальность массовой задачи не поменяется (это просто константа в полиноме - время на работу единичной задачи - пусть гигантское время), а если не остановится - то алгоритм проверки явно не ограничен полиномом.
Это неверно - в $\mathbf{PA}$ можно доказать, что от изменения одного значения язык не может перестать лежать в $\mathbf{P}$. Независимо от того, можем ли мы определить это единичное значение.

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


18/05/14
215
Москва
Xaositect в сообщении #1202710 писал(а):
Это неверно - в $\mathbf{PA}$ можно доказать, что от изменения одного значения язык не может перестать лежать в $\mathbf{P}$. Независимо от того, можем ли мы определить это единичное значение.


Не в том случае, если это "изменение" не оказывается бесконечной работой. Значение просто исчезает.

P.S. Да и требование на ограниченность времени работы алгоритма перестаёт выполняться.

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


06/10/08
6422
dmitgu в сообщении #1202713 писал(а):
Не в том случае, если это "изменение" не оказывается бесконечной работой. Значение просто исчезает.
Такого быть не может. Язык по определению есть множество, то есть для каждого слова $w$ какая-то из двух альтернатив $w \in L$ или $w \notin L$ верна.

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


18/05/14
215
Москва
Xaositect в сообщении #1202715 писал(а):
dmitgu в сообщении #1202713

писал(а):
Не в том случае, если это "изменение" не оказывается бесконечной работой. Значение просто исчезает. Такого быть не может. Язык по определению есть множество, то есть для каждого слова $w$ какая-то из двух альтернатив $w \in L$ или $w \notin L$ верна.


Тем лучше - тогда он перестаёт быть даже языком :) У нас нет способа распознать - язык это или нет. В смысле отсутствия отрицательного теста.

P.S. Возможно, я Вас не совсем понял. Я отвечаю про отрицательный тест (узнать, что НЕ принадлежит), а Вы, видимо, про отсутствие положительного теста (узнать, что принадлежит). Тут у меня нет ответа сейчас, но, по смутным впечатлениям это можно как-то доказать....

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 384 ]  На страницу Пред.  1 ... 9, 10, 11, 12, 13, 14, 15 ... 26  След.

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



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

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


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

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