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

[dmitgu]

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) «Фауст». А частью «слова» у нас является алгоритм-решение с тем, что у него подставлено в качестве аргумента долга, а не то, что у него подставлено – независимо от самого алгоритма-решения.

[Xaositect]

Нет, давайте начнем сначала, а то у меня уже по первым предложениям куча вопросов. Определяйте все понятия и обозначения.

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$ не найдет сертификат, не важен?

[dmitgu]

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}$ -Теорема построена так, что не найдёт.

[Xaositect]

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

[dmitgu]

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

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

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

[mihaild]

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$ и что надо доказывать.

[dmitgu]

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$, если я правильно Вас понял.

[mihaild]

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

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

Тем, что он не предложил формализм, а задал несколько вопросов.
А я попытался сделать большой шаг и угадать сразу пачку ответов (заодно показать, как должны выглядеть нормальные формулировки). Иногда такой подход (попробовать угадать) оказывается лучше, иногда - нет.

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

не всякий пустой язык принадлежит $NP$ или $P$.

Пустой язык ровно один, и он принадлежит и $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$ уже обычная полиномиальная МТ, никой недетерменированности/подсказок/... у нее нет.

[dmitgu]

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$. Пустой язык ровно один, и он принадлежит и $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 писал(а):

заодно показать, как должны выглядеть нормальные формулировки

[Xaositect]

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

А если там везде $0$, то что - оба из класса $NP$ или не из $NP$? По Вашему же они одинаковы.

Именно так. Задача определения по коду машины, полиномиальная она или нет - неразрешима. Возможно, существуют языки из $\mathbf{P}$ (или $\mathbf{NP}$), для которых нельзя доказать, что они принадлежат $\mathbf{P}$ (или $\mathbf{NP}$).

[dmitgu]

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

Возможно, существуют языки из $\mathbf{P}$ (или $\mathbf{NP}$), для которых нельзя доказать, что они принадлежат $\mathbf{P}$ (или $\mathbf{NP}$).

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

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

[Xaositect]

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

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

Это неверно - в $\mathbf{PA}$ можно доказать, что от изменения одного значения язык не может перестать лежать в $\mathbf{P}$. Независимо от того, можем ли мы определить это единичное значение.

[dmitgu]

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

Это неверно - в $\mathbf{PA}$ можно доказать, что от изменения одного значения язык не может перестать лежать в $\mathbf{P}$. Независимо от того, можем ли мы определить это единичное значение.

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

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

[Xaositect]

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

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

Такого быть не может. Язык по определению есть множество, то есть для каждого слова $w$ какая-то из двух альтернатив $w \in L$ или $w \notin L$ верна.

[dmitgu]

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

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

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

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

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