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

[mihaild]

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

Чего тут "угадывать"?

Ну я же не знаю, какие непонятно что значащие слова можно игнорировать, а какие нет:)

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

Да. Написано же:

Высказывание "утверждение с текстом в $t$" имело бы смысл, если бы $t$ было множеством текстов.

Давайте вы не будете сопротивляться попыткам привести ваше рассуждение в хоть сколь-нибудь читаемый вид?

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

Да всё просто - каждому $Sol$ и $S$ соответствует свой $AntiSol_S$ - по их текстам "вычисляется" текст $AntiSol_S$ и сравнивается с тем, что передано в аргументе $t$

Извините, так нельзя. У вас написано

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

$a$ – текст (программный код) некоторого алгоритма типа $\overline{\operatorname{Sol}(... , ... , ...)}$ или же текст $\overline{-}$;

К этому моменту $\operatorname{Sol}$ уже должен быть определен. Или там вообще произвольный алгоритм? Тогда это пишется как например "$a$ - текст некоторого алгоритма $\operatorname{Sol}$". Или "$a$ - текст некоторого алгоритма; далее будем обозначать этот алгоритм $\operatorname{Sol}$".

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

Да выписаны же:

Читайте внимательнее, эти условия я перечислил. "Еще какие-то" - это ваш пункт 6.1.

Ладно, попробуем так.

Верно ли, что вы хотите явно построить язык, который принадлежит $P$, но не $NP$?
Верно ли, что этим языком является язык, состоящий из троек $(t, S, s)$ и четверок $(t, S, a, s)$, удовлетворяющих

(условиям)

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

$S$ – число, записанное в позиционном виде (например, в десятичном – вроде 3001) :
$s = \operatorname{ss}(S)$, где алгоритм $\operatorname{ss}(S)$ возвращает строку длиной $S$, состоящую только из символов «1»;
$a$ – текст (программный код) некоторого алгоритма типа $\overline{\operatorname{Sol}(... , ... , ...)}$ или же текст $\overline{-}$;
$t$ – текст некоторого утверждения на языке теории Пеано;
$y$ – текст некоторого доказательства на языке теории Пеано;
$|y|$ – размер текста y ограничен: $|y| \le q_S(S) - |a|$, где $q_S(S) = 1000 \cdot S^n$, $n$ – некоторая фиксированная степень, и, разумеется, условие на размер нарушено, если $ q_S(S) \le |a|$;

.
Если нет - то что из удовлетворяющего этим условиям не лежит в языке и/или что из не удовлетворяющего - не лежит?
(обратите внимание, что мы говорим о языке, а не об алгоритме)
Если да - едем дальше.

[dmitgu]

Для начала повторю п. 6 в начале странице для удобства обсуждения и копирования - с исправленными опечатками

6. Для тех, кто решил читать заметку с этого пункта, дадим сводную информацию. Язык $LS$ из класса $\mathbb{NP}$ соответствует следующему алгоритму проверки (по которому язык $LS$ и можно отнести к классу $\mathbb{NP}$) – $\operatorname{Ls}(t, S, a, s, y)$. В неисключительных случаях (об исключительных будет в п. 6.1) аргументы «не подтвердят» слово языка и результат будет $0$ (Ноль), если не будет исполнено хоть одно из следующих условий:
$S$ – число, записанное в позиционном виде (например, в десятичном – вроде 3001) :
$s = \operatorname{ss}(S)$, где алгоритм $\operatorname{ss}(S)$ возвращает строку длиной $S$, состоящую только из символов «1»;
$a$ – текст (программный код) некоторого алгоритма типа $\overline{\operatorname{Sol}(... , ... , ...)}$ или же текст $\overline{-}$;
$t$ – текст некоторого утверждения на языке теории Пеано;
$y$ – текст некоторого доказательства на языке теории Пеано;
$|y|$ – размер текста y ограничен: $|y| \le q_S(S) - |a|$, где $q_S(S) = 1000 \cdot S^n$, $n$ – некоторая фиксированная степень, и, разумеется, условие на размер нарушено, если $ q_S(S) \le |a|$;
Утверждение с текстом в $t$ доказывается доказательством с текстом в $y$ в рамках теории Пеано (или любой другой заранее оговорённой теории арифметики, если она более полная и удобная для наших целей, чем теория Пеано);
Если случай не из пункта 6.1 и перечисленные условия выполнены, то:
$\operatorname{Ls}( t, S, a, s, y) = 1$.
Ещё мы условились, что записи вида $\overline{AntiSol_S}$ или $\overline{\operatorname{Sol}(... , ... , ...)}$ обозначают текст утверждения $AntiSol_S$ на заранее оговоренном языке логики и программный код (тоже текст, фактически) алгоритма $\operatorname{Sol}(..., ..., ...)$, записанный оговорённым способом представления алгоритмов в выбранной за основу языка $LS$ теории первого порядка (теория Пеано способна представлять алгоритмы, но не очень наглядно – тут есть что улучшать для практических нужд).
И, разумеется, мы пользуемся не «гёделевыми номерами», которые дают неполиномиально огромное представление для информации (число 10, например, имеет вид «1111111111»), а принятым в «человеческом» и «компьютерном» мире представлением в виде текстов и чисел в позиционном (десятичном, например) представлении.
Теперь – о времени работы алгоритма проверки для разных случаев, словах языка $LS$, сертификатах, их размере и исключениях:
6.1. Для случаев, подходящих под шаблон
$\operatorname{Ls}(\overline{AntiSol_S}, S, \overline{\operatorname{Sol}(... , ... , ...)}, ... , ...)$ количество шагов работы – в пределах полинома $p_{\exists}(|t|, |S|, |a|)$. В силу того, что в данном случае $t = \overline{AntiSol_S}$, чей размер полиномиально зависит от размера $|a| = |\overline{\operatorname{Sol}(... , ... , ...)}|$ и от размера $|S|$, а при этом $|\overline{\operatorname{Sol}(... , ... , ...)}| < |\overline{AntiSol_S}|$, то в $p_{\exists}(|t|, |S|, |a|)$ можно заменить $|a|$ на $|t|$ и ограничивающий алгоритм останется ограничивающим (количество шагов работы алгоритма проверки не превысит результат данного ограничивающего алгоритма) и при этом он останется полиномиальным. И его тогда можно переписать в виде:
$p_{\exists}(|\overline{AntiSol_S}|, |S|)$ (что равно $p_{\exists}(|t|, |S|)$).
Проверку под шаблон 6.1 алгоритм $\operatorname{Ls}(t, S, a, s, y)$ проводит в первую очередь и – если соответствие обнаружено – возвращает $0$ в пределах указанного времени (количества шагов).
Кстати, многоточия в конце $\operatorname{Ls}(\overline{AntiSol_S}, S, \overline{\operatorname{Sol}(... , ... , ...)}, ... , ...)$ стоят потому, что аргументы $s, y$ в данном случае не используются и тут алгоритм зависит, фактически, от трёх аргументов, возвращая $0$: $\operatorname{Ls}(\overline{AntiSol_S}, S, \overline{\operatorname{Sol}(... , ... , ...)}, ... , ...) = 0$.
И, напомню, случай 6.1 относится к тому слову (словам!), принадлежность которого отвергается и смысл этого отказа такой: «Алгоритм $\operatorname{Sol}(\overline{AntiSol_S}, S, ...)$ не может найти доказательство для утверждения $AntiSol_S$». Можно было бы добавить «…в пределах доказательств допустимого размера», но найти доказательство для утверждения $AntiSol_S$ алгоритм $\operatorname{Sol}(\overline{AntiSol_S}, S, ...)$ не может в принципе. Поэтому не может «вообще» и, в силу этого, «…в пределах доказательств допустимого размера» в том числе. Подробнее:
Алгоритм-решение $\operatorname{Sol}(\overline{AntiSol_S}, S, s)$ решает вопрос о принадлежности языку $LS$
слова вида 1: $\overline{AntiSol_S}, S, s$; с сертификатом вида 1: $a, y$.
При этом сам алгоритм-решение в этом решении соответствует части сертификата $a = \overline{\operatorname{Sol}(... , ... , ...)}$ и из пункта 6.1 за количество шагов в пределах $p_{\exists}(|\overline{AntiSol_S}|, |S|)$ можно узнать от алгоритма проверки $\operatorname{Ls}(\overline{AntiSol_S}, \operatorname{Sol}(... , ... , ...), ... , ...) = 0$, что никакого подтверждающего сертификата с такой частью $a$ для данного слова найти невозможно – что соответствует тому факту, что алгоритм $\operatorname{Sol}(\overline{AntiSol_S}, S, s)$ не может корректно подтвердить (выдать в качестве результата $1$) слово $\overline{AntiSol_S}, S, s$ (оно построено в соответствии с теоремой о неопределимости для данного алгоритма-решения).
При этом в языке $LS$ помимо слов вида 1, есть и
слова вида 2: $t, S, a, s$; с сертификатом вида 2: $y$.
И данный ответ алгоритма проверки из пункта 6.1:
$\operatorname{Ls}(\overline{AntiSol_S}, \operatorname{Sol}(... , ... , ...), ... , ...) = 0$
соответствует отсутствию в языке $LS$
слов вида 2: $\overline{AntiSol_S}, S, \overline{Sol(…, …, …)}, s$; с сертификатами вида 2: $y$.
То есть, хоть алгоритм-решение $\operatorname{Sol}(... , ... , ...)$ должен решать вопрос о принадлежности языку $LS$ слов вида 1, но при $\operatorname{Sol}(\overline{AntiSol_S}, S, s) = 0$ он даёт правильный ответ с точки зрения непринадлежности языку $LS$ слова вида 2: $\overline{AntiSol_S}, S, \overline{Sol(…, …, …)}, s$. Но непринадлежность языку данного слова вида 2 соответствует как раз невозможности найти подтверждающий сертификат с частью $a = \overline{\operatorname{Sol}(... , ... , ...)}$ для слова вида 1: $\overline{AntiSol_S}, S, s$.
В случае 6.1 ограничивающий алгоритм $p_{\exists}(|t|, |S|)$ не зависит от $s$, $y$. Но от них не зависит и работа $\operatorname{Ls}(\overline{AntiSol_S}, \operatorname{Sol}(... , ... , ...), ... , ...) = 0$ в случае, подходящем под шаблон пункта 6.1.
6.2. Для остальных случаев количество шагов работы алгоритма проверки – в пределах $p_{\forall}(|t|, |S|, |s|)$, впрочем, и пункт 6.1 соответствует пункту 6. Но случай 6.1 является более жёстким ограничением – неполиномиально более жёстким, так как в случае 6.2 членом полинома является размер $|s|$, растущий экспоненциально относительно размера $|S|$.
Случай 6.2. в равной степени относится к словам вида 1 и 2, не попадающими под шаблон пункта 6.1:
слова вида 1: $t, S, s$; с сертификатом вида 2: $a, y$.
слова вида 2: $t, S, a, s$; с сертификатом вида 2: $y$.
Для слов вида 1 суммарный размер сертификата ограничен (требование корректности) алгоритмом
$1000 \cdot S^n$, где $n$ – некоторая фиксированная степень:
$|a| + |y| \le 1000 \cdot S^n$, что повторяет сказанное в начале пункта 6 про размер доказательства $|y|$:
$|y| \le q_S(|s|) - |a|$,
а последнее ограничение соответствует сертификату вида 2. Для обоих вариантов, как видим, ограничение сертификата является полиномиальным относительно размера слова.
И кроме специальных случаев из 6.1 – при котором соответствующие слова языку $LS$ как раз не принадлежат – в остальном принадлежность слов вида 1 и вида 2 языку $LS$ (при корректных $a$) ничем не отличаются друг от друга. Такая «одинаковость» (кроме спец. случая) связана с тем, что в языке $LS$ мы учитываем только ту ограниченность возможностей алгоритмов-решений, которая следует из теоремы о неопределимости. Но эта ограниченность полностью исчерпывается специфическими случаями (хоть их и бесконечное количество для каждого алгоритма-решения) из пункта 6.1.
6.3. Если алгоритм-решение $\operatorname{Sol}(\overline{AntiSol_S}, S, s)$ для слова из специального случая 6.1 возвращает $1$ при корректном $s = \operatorname{ss}(S)$:
$\operatorname{Sol}(\overline{AntiSol_S}, S, s) = 1$ (случай 1),
то доказательства для утверждения $AntiSol_S$ нет, и, напротив, имеется доказательство для его отрицания. То есть, ответ данного алгоритма-решения на данном слове в этом случае заведомо не корректен.
Если же алгоритм-решение $\operatorname{Sol}(\overline{AntiSol_S}, S, s)$ для слова из специального случая 6.1 возвращает $0$ при корректном $s = \operatorname{ss}(S)$:
$\operatorname{Sol}(\overline{AntiSol_S}, S, s) = 0$ (случай 2),
то логическое доказательства для утверждения $AntiSol_S$ имеется, но, вопрос – соответствует ли размер данного доказательства допустимым размерам:
$|y| \le q_S(|s|) - |a|$.
Но если размер данного доказательства соответствует указанному пределу, то ответ данного алгоритма-решения на данном слове и в этом случае оказывается не корректным.
Если же алгоритм-решение $\operatorname{Sol}(\overline{AntiSol_S}, S, s)$ для слова из специального случая 6.1 не возвращает никакого ответа при корректном $s = \operatorname{ss}(S)$ (случай 3), то данное слово действительно не принадлежит языку $LS$ и это подтверждается при любых сертификатах алгоритмом проверки. То есть, и в данном случае работа алгоритма-решения $\operatorname{Sol}(\overline{AntiSol_S}, S, s)$ оказывается не корректной.
Значит, единственный случай, при котором алгоритм-решение $\operatorname{Sol}(\overline{AntiSol_S}, S, s)$ может выдать корректный результат – случай 2. И результат этот должен быть $0$. И этот результат соответствует результату работы алгоритма проверки $\operatorname{Ls}(\overline{AntiSol_S}, S, \overline{\operatorname{Sol}(... , ... , ...)}, ... , ...) = 0$ за полиномиальное количество шагов работы – в пределах $p_{\exists}(|\overline{AntiSol_S}|, |S|)$ (что равно $p_{\exists}(|t|, |S|)$).
Поэтому при сведении нашей задачи из класса $\mathbb{NP}$ в класс $\mathbb{P}$ полиномиальность времени проверки для случая 2 $p_{\exists}(|t|, |S|)$ должна превратиться в полиномиальность времени на обнаружение решения (или невозможности решения) вида $p_{\exists +}(|t|, |S|)$.
И вот идея доказательства для $\mathbb{NP} \ne \mathbb{P}$:
Здесь очевидно, что при достаточно больших $S$ данное предельное время работы алгоритма-решения из случая 2 экспоненциально мало по сравнению с допустимым размером доказательств: $|y| \le q_S(|s|) - |a|$, так как размер $|s| = |\operatorname{ss}(S)|$ экспоненциально велик по сравнению и с размером $|a|$, и с аргументами в $p_{\exists +}(|t|, |S|)$ при достаточно больших $S$.
А это значит, что для достаточно больших $S$ среди допустимых доказательств найдётся и то, в котором будет вывод и для случая 2: $\operatorname{Sol}(\overline{AntiSol_S}, S, \operatorname{ss}(S)) = 0$, и для вытекающего из него утверждения $AntiSol_S$. А это и будет означать, что алгоритм $\operatorname{Sol}(\overline{AntiSol_S}, S, \operatorname{ss}(S))$ не смог подтвердить истинность утверждения $AntiSol_S$ для которого есть доказательство среди доказательств допустимого размера.
А поскольку алгоритм $\operatorname{Sol}(..., ..., ...)$ произвольный, то это будет означать отсутствие корректных алгоритмов-решений, делающих язык $LS$ языком класса $\mathbb{P}$. То есть – оказывается доказанным неравенство $\mathbb{NP} \ne \mathbb{P}$.
Конечно, в нескольких абзацах выше изложено доказательство $\mathbb{NP} \ne \mathbb{P}$ в общих чертах, а детали – как строить вывод для утверждения $AntiSol_S$ при корректном времени работы алгоритма-решения $\operatorname{Sol}(\overline{AntiSol_S}, S, \operatorname{ss}(S)) = 0$ и почему размер вывода будет допустимого размера – изложены в следующем разделе.

-- 02.10.2017, 16:04 --

А теперь - на вопросы:

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

утверждение с текстом в $t$" имело бы смысл, если бы $t$ было множеством текстов

Там речь об аргументе алгоритма проверки. У аргумента есть значение и это значение - текст. А когда речь о слове - то $t$ обозначает ту его часть, которая тоже содержит текст утверждения. Но раз слово языка, то это должно быть истинное в теории Пеано утверждение.

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

Или там вообще произвольный алгоритм?

Да, произвольный. Или $\overline{-}$. Разумеется, для $\overline{-}$ нет никакого $AntiSol_S$ и при $a = $\overline{-}$ условия п. 6.1 никогда не выполнены.

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

Верно ли, что этим языком является язык, состоящий из троек $(t, S, s)$ и четверок $(t, S, a, s)$, удовлетворяющих
(условиям)
dmitgu в сообщении #1252198

писал(а):
$S$ – число, записанное в позиционном виде (например, в десятичном – вроде 3001) :
$s = \operatorname{ss}(S)$, где алгоритм $\operatorname{ss}(S)$ возвращает строку длиной $S$, состоящую только из символов «1»;
$a$ – текст (программный код) некоторого алгоритма типа $\overline{\operatorname{Sol}(... , ... , ...)}$ или же текст $\overline{-}$;
$t$ – текст некоторого утверждения на языке теории Пеано;
$y$ – текст некоторого доказательства на языке теории Пеано;
$|y|$ – размер текста y ограничен: $|y| \le q_S(S) - |a|$, где $q_S(S) = 1000 \cdot S^n$, $n$ – некоторая фиксированная степень, и, разумеется, условие на размер нарушено, если $ q_S(S) \le |a|$;

Вы упустили вот это:

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

Утверждение с текстом в $t$ доказывается доказательством с текстом в $y$ в рамках теории Пеано (или любой другой заранее оговорённой теории арифметики, если она более полная и удобная для наших целей, чем теория Пеано);

И упустили п.6.1 - некоторые слова не "проходят" из-за него.

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

Верно ли, что вы хотите явно построить язык, который принадлежит $P$, но не $NP$?

Наоборот, конечно. Вы, наверно, опечатались. Если да - тогда дальше, но я сейчас на работе и может позже )

[mihaild]

Да, я выше написал бред. Должно было быть "язык, состоящий из троек и четверок, таких что существует $y$ такой что выполнены условия ...".

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

И упустили п.6.1 - некоторые слова не "проходят" из-за него.

Так, т.е. мы пока что строим язык, который принадлежит $NP$, но не $P$? (да, там была опечатка)
И строим мы его так: берем указанный язык из троек $(t, S, s)$ и четверок $(t, S, a, s)$ и потом что-то еще из него выкидываем?

(у вас будет как-то принципиально использоваться механизм кодирования, или "любой разумный" подойдет? если да, то предлагаю договориться не отличать алгоритмы и их код)
Давайте обозначим:
$U$ - язык из пятерок $(S, s, a, t, y)$ таких что $S$ - число (в двоичной системе исчисления), $s = 1^S$, $a$ - текст алгоритма либо $\overline{-}$, $t$ - текст некоторого утверждения в сигнатуре арифметики, $y$ - доказательство этого утверждения, $|y| \leqslant 1000S^n - |a|$ ($n$ - некоторая мировая константа)
$V_3 = \{(t, S, s) | \exists a, y: (S, s, a, t, y) \in U\}$, $V_4 = \{(t, S, a, s) | \exists y: (S, s, a, t, y) \in U\}$

В этих обозначениях, интересующий нас язык получается выкидыванием чего-то из $V_3 \cup V_4$. Так?

[dmitgu]

Давайте пока отложим Ваш последний вопрос и вернёмся к принципиальному моменту – предыдущему Вашему вопросу (опечатка исправлена мной – раз Вы её подтвердили):

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

Верно ли, что вы хотите явно построить язык, который принадлежит $NP$, но не $P$?

Я вчера на работе не подумав, поспешил сказать «да», но когда было время подумать – понял, что это не то же самое, что $\mathbb{NP} \ne \mathbb{P}$. Поэтому отвечаю так:

Нет, не верно.

$\mathbb{NP} \ne \mathbb{P}$ это просто красивое обозначение для того предположения, что не всё то, что можно проверить за время $T$ можно и найти (или выяснить, что невозможно найти) за время $p(T)$ (где $p(T)$ – полином от $T$) – вот именно это я и доказываю. Если же ответ удаётся найти лишь за неполиномиально долгое время относительно времени проверки, то это не возможность решения, а ерунда, которая вписывается именно в $\mathbb{NP} \ne \mathbb{P}$, даже если эта ерунда и может быть как-то отнесена в класс $\mathbb{P}$.

То есть – должно быть не просто соответствие между классами $\mathbb{NP}$ и $\mathbb{P}$ для соответствия обозначению «равенство» $\mathbb{NP} = \mathbb{P}$, но соответствие между «уровнями» полиномиальности соответствующих алгоритмов, относящих в класс $\mathbb{NP}$ и в класс $\mathbb{P}$ данный язык. Если же этого где-то нет, то верно не $\mathbb{NP} = \mathbb{P}$, а «неравенство» $\mathbb{NP} \ne \mathbb{P}$, независимо от того, является данный язык в каком-то «худшем» уровне полиномиальности из класса $\mathbb{P}$ или нет.

То есть, не надо из условного обозначения выводить своё ошибочное буквальное толкование ;) Это я не Вам говорю, а вообще – себе в том числе ).

Например: язык из слов

$def, any$

проверяется по сертификатам (неважно, каким) на принадлежность к языку за время $p_1(|def|)$. И тогда его решение из класса $\mathbb{P}$ должно находить ответ о принадлежности за время $p_2(|def|)$. И там и там – полиномы. А вовсе не за время $p_3(|def|, |any|)$, где размер $|any|$ может быть экспоненциально огромным относительно размера $|def|$. И в случае $p_3(|def|, |any|)$ «решение» вовсе не является решением в классе $\mathbb{P}$ для разбираемого языка, даже если оно и относит этот язык в класс $\mathbb{P}$.

[mihaild]

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

$\mathbb{NP} \ne \mathbb{P}$ это просто красивое обозначение для того предположения, что не всё то, что можно проверить за время $T$ можно и найти (или выяснить, что невозможно найти) за время $p(T)$ (где $p(T)$ – полином от $T$) – вот именно это я и доказываю

Нет, $NP \stackrel{?}{=} P$ - это вполне конкретный вопрос про равенство двух классов языков. Двух совершенно конкретных классов.
Можно показать, что $P = NP$ эквивалентно, например, существованию полиномиального алгоритма для $3-SAT$ (или любой другой $NP$-полной задачи).

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

Я не знаю, что такое "уровни полиномиальности". Степень полинома?
Может быть, вы хотите доказать что-то вроде "существует язык $L$, распознающийся недетерменированной МТ за $O(n^k)$, но не распознающийся детерменированной за $o(n^{k+1})$"?
(я не знаю, интересный ли это результат - он явно слабее чем $P \neq NP$, но доказать его за 20 секунд я не смог)

Последнюю часть вашего ответа не понял. На всякий случай напоминаю, что по определению $NP$ размер сертификата ограничен полиномом от длины вопроса, так что полиномиальность относительно вопроса и относительно сертификата - это одно и то же.

[dmitgu]

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

Я не знаю, что такое "уровни полиномиальности". Степень полинома?
Может быть, вы хотите доказать что-то вроде "существует язык $L$, распознающийся недетерменированной МТ за $O(n^k)$, но не распознающийся детерменированной за $o(n^{k+1})$"?

Имеется в виду вот что:
Если для языка $L$ проверка принадлежности слова:
$w_1, w_2, ..., w_i, ..., w_N$ на сертификатах вида $s$ занимает время (количество шагов) в пределах полинома:

$p_1(|w_1|, |w_2|, ..., |w_i|)$ для алгоритма проверки, относящего данный язык в класс $NP$

то и от алгоритма-решения (главное слово тут "решение"), который относил бы этот язык в класс $P$ требуется, чтобы решение было получено в пределах полинома от тех же аргументов:

$p_2(|w_1|, |w_2|, ..., |w_i|)$

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

Вот $p_1(|w_1|, |w_2|, ..., |w_i|)$ и $p_2(|w_1|, |w_2|, ..., |w_i|)$ я и называю полиномами одинакового уровня - они отличаются друг от друга не более, чем полиномиально.

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

Последнюю часть вашего ответа не понял. На всякий случай напоминаю, что по определению $NP$ размер сертификата ограничен полиномом от длины вопроса, так что полиномиальность относительно вопроса и относительно сертификата - это одно и то же.

Нет, там как раз про сертификат ни буквы в формулах )

$any$ - это как раз часть слова, если брать последний пример, то часть:

$w_{i + 1}, ..., w_N$ - которая не участвует в проверках. И да, время ограничено полиномом от размера слова, но более того - оно ограничено в данном примере полиномом от части слова (как и сертификат). Это никак не нарушает требования на принадлежность к классу $NP$ - а лишь накладывает ещё более сильные ограничения.

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

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

"Другой вопрос" я выписал сейчас чуть выше: вопрос о сводимости языка из $NP$ к классу $P$, чтобы "уровень полиномиальности" проверки (из $NP$) и решения (из $P$) был один и тот же.

Вообще-то изначально весь вопрос от криптографии и он - о трудности взлома. А это означает, что при знании ключа его легко применить, но вопрос - а найти его - это тот же уровень полиномиальности - можно этого добиться?

В тех языках из $NP$, которые приводятся в учебниках с теми алгоритмами проверки ответ "нет" означает одновременно и то, что язык не принадлежит классу $P$. И отсюда красивая формула $\mathbb{NP} \ne \mathbb{P}$.

Но в основе-то - вопрос о сводимости языка из $NP$ в $P$ с тем же уровнем полиномиальности. И в моём языке удаётся (что я и хочу тут проверить) доказать, что такой сводимости нет. Не доказывая при этом, что язык не принадлежит классу $P$. То есть, я не говорю, что "принадлежит $P$", более того, я практически уверен, что не принадлежит, но я доказываю не это, а более лёгкий вопрос.

Спасибо, кстати, что спросили про непринадлежность классу $P$ - я знал, откуда вопрос про $\mathbb{NP} \ne \mathbb{P}$ и решал "первопричину". Формула $\mathbb{NP} \ne \mathbb{P}$ более распиарена, но вопрос-то изначально не в ней. Про название - я подумаю. Может надо что-то типа с "Несводимость языка класса $NP$ к классу $P$", а может, оставить как есть (если проверка не обнаружит ошибок в доказательстве, конечно), но в аннотации указать, что решается "вопрос-первоисточник". Потому что пиар с $\mathbb{NP} \ne \mathbb{P}$ заставляет людей отвлекаться от главного на производное. Но, разумеется, вопрос про $\mathbb{NP} \ne \mathbb{P}$ уже живет своей жизнью, он объявлен "задачей тысячелетия" и на его решение я не претендую. В разбираемой заметке

В последнем разделе, кстати, я намечаю план (в паре абзацев), где можно - видимо - доказать, что $LS$ не принадлежит $P$ и то же утверждение $AntiSol_S$ в этом плане играет важную роль. Но - там требуется понимание, как сжимать работу алгоритма - подобные теоремы есть в теории алгоритмов, но это было бы уже доказательство гораздо более сложное. И другие, возможно, решат это быстрее, чем я - любитель, а не проф. математик.

А мне бы хотелось сделать свои шаги в решении проблем сложности - которые и стояли изначально и могут помочь и в решении $\mathbb{NP} \ne \mathbb{P}$ тоже. Но ведь и это - совсем не "окончательный вопрос", ведь он является лишь промежуточным для доказательства существования стойкой криптографии с секретным ключом. Следующий за ним шаг по сложности - это вопрос о существовании односторонней функции. И, кстати, не факт, что $\mathbb{NP} \ne \mathbb{P}$ поможет в этом больше, чем то, что доказываю я.

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

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

Нет, $NP \stackrel{?}{=} P$ - это вполне конкретный вопрос про равенство двух классов языков. Двух совершенно конкретных классов.
Можно показать, что $P = NP$ эквивалентно, например, существованию полиномиального алгоритма для $3-SAT$ (или любой другой $NP$-полной задачи).

Ну, одно из представлений. Я, кстати, пересмотрел своё мнение о том, что мой язык не сводим к $SAT$ - после того, как получше разобрался с формализмом языков. Просто эта сводимость ничего особенного не даёт и доказывать несводимость языков из $NP$ к решению в $P$ (то, что делаю я) удобней всё равно в рамках Пеано, имхо. Про это тоже есть в заключительном разделе.

Из того, что у нас имеется ДНФ для любой единичной задачи для любого языка из класса сложности $\mathbb{NP}$, которая разрешима, вообще говоря, для алгоритмов – создаётся иллюзия, что дело именно в решении ДНФ.

Но дело не в отдельных ДНФ, а в их комплексе, а вот их комплекс как раз и соответствует утверждениям $AntiSol_S$, которые неразрешимы для соответствующего ему (взятого произвольно!) алгоритма-решения $\operatorname{Sol}(\overline{AntiSol_S}, S, ...)$ при больших $S$ в классе $P$.
..
А оперируя с алгоритмами (а не ДНФ), нам потребовалось лишь сделать кое-какие не слишком сложные построения. Видимо, это гораздо более простой путь доказательства, чем пытаться решать вопрос о несводимости ДНФ к классу $\mathbb{P}$ «в лоб», подменяя готовый набор однородных утверждений типа $AntiSol_S$ с общими свойствами на наборы соответствующих им ДНФ. Притом что аппарат для выявления неразрешимости и неполноты для утверждений теории Пеано хорошо разработан и многого достиг, в отличие от работы с "наборами ДНФ".

[mihaild]

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

Нет, там как раз про сертификат ни буквы в формулах )

Выкиньте эти формулы и возьмите правильные.

Вялый, Китаев, Шень в Классические и квантовые вычисления писал(а):

Определение 2.2. Предикат $L$ принадлежит языку $NP$, если он представим в форме $L(x) = \exists y((|y| < q(|x|)) \wedge R(x, y))$, где $q(\cdot)$ - полином, а $R(\cdot, \cdot) \in P$.

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

то и от алгоритма-решения (главное слово тут "решение"), который относил бы этот язык в класс $P$ требуется, чтобы решение было получено в пределах полинома от тех же аргументов

Не знаю, что такое "алгоритм-решение", но естественно, что язык принадлежит $P$, если существует полиномиальный (от длины входа!) алгоритм, его распознающий. Какие при этом существуют алгоритмы в других моделях вычисления - неважно.

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

да, время ограничено полиномом от размера слова, но более того - оно ограничено в данном примере полиномом от части слова (как и сертификат).

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

[dmitgu]

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

Не знаю, что такое "алгоритм-решение"

Если слово
$t, S, s$ (не)принадлежит языку $LS$ и время проверки в пределах $p_{\forall}(|t|, |S|, |s|)$ на сертификатах $a, y$, то корректный алгоритм-решение $\operatorname{Sol}(t, S, s)$, относящий $LS$ к классу $P$ должен выдать свой ответ за время в пределах $p_{\forall +}(|t|, |S|, |s|)$ о (не)принадлежности этого слова языку $LS$

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

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

Возьмите язык, которому принадлежат все слова , которые начинаются на "1111". Чтобы распознать слово любой длины как принадлежащее языку - достаточно прочитать первые 4 символа для слов такого типа.

А ещё интересней момент с тем, когда слова отвергаются - допустим, никакие слова с начальными "1111" не принадлежат - чтобы отвергнуть - хватит чтения 4-х символов.

Кстати, слишком длинные сертификаты каким образом отвергаются "быстрее чем линейно от длины входа" ? :)) Вы же не думаете, что алгоритм проверки читает их целиком, а затем время работы алгоритма проверки чудесным образом оказывается независимым от этого "чтения целиком".

Вот на возможности отвергать некоторые слова быстрее, чем полиномиально от того максимального размера, который мог бы быть при их обнаружении в языке $LS$ и строится моё доказательство.

[mihaild]

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

то корректный алгоритм-решение $\operatorname{Sol}(t, S, s)$, относящий $LS$ к классу $P$

Алгоритм не может относить язык к классу. Язык вообще нельзя отнести к классу - он ему либо принадлежит, либо не принадлежит.
Кроме того, в вашей фразе $a$ и $y$ упоминаются ровно один раз - так что непонятно, зачем они там вообще.

Попробуйте переписать ваше определение в виде "[определяемое понятие] - это такое [что-то], что существуют такие [что-то], что [что-то еще]".

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

Возьмите язык, которому принадлежат все слова , которые начинаются на "1111". Чтобы распознать слово любой длины как принадлежащее языку - достаточно прочитать первые 4 символа для слов такого типа.

Нет, недостаточно. Классическое определение: "МТ принимает (отвергает) слово $x$ за время $t$, если на входе $x$ она останавливается за $t$ шагов, оставляя на ленте $\ldots\#\#\#1\#\#\#\ldots$ ($\ldots\#\#\#0\#\#\#\ldots$)". Из этого тривиально следует, что слово не может быть принято за время, меньшее его длины (т.к. необходимо стереть это слово).

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

Кстати, слишком длинные сертификаты каким образом отвергаются "быстрее чем линейно от длины входа" ? :))

Ну так не отвергаются они быстрее чем линейно. Посмотрите еще раз внимательно правильное определение $NP$, приведенное чуть выше. Там никто не требует анализа сертификата за время, не зависящее от его длины.

[dmitgu]

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

Алгоритм не может относить язык к классу. Язык вообще нельзя отнести к классу - он ему либо принадлежит, либо не принадлежит.

Язык - это вообще множество слов. И никакого отношения к алгоритмам он не имеет. И все эти классы $NP$, $P$ - это именно про алгоритмы, результат работы которых можно сопоставить этому языку. Поэтому про принадлежность классу языка пишут "существует алгоритм". Задавать же язык из класса $NP$ можно и любым неполиномиальным образом и через сертификаты, которые экспоненциально огромны и т.д. и т.п. Не нужно смешивать язык и классы. Алгоритм - именно относит язык в какой-то класс. И у языка может быть и алгоритм, относящий его в класс $NP$ и алгоритм, относящий его в класс $P$. Язык от этого никак не меняется.

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

"МТ принимает (отвергает) слово $x$ за время $t$, если на входе $x$ она останавливается за $t$ шагов, оставляя на ленте $\ldots\#\#\#1\#\#\#\ldots$ ($\ldots\#\#\#0\#\#\#\ldots$)". Из этого тривиально следует, что слово не может быть принято за время, меньшее его длины (т.к. необходимо стереть это слово).

Как это "следует"? Поясните, пожалуйста.
$MT$ начинает работать, когда на ленте уже есть данные. И дойдя до ерунды, она может остановится, выдав отрицательный результат.

И отвергнуть она может не стирая всё, что там написано, а записав 0 в первых 5 ячейках или там, где остановилась каретка. Это вообще совершено бессмысленное требование - про стирание.

Кстати, а как $MT$ узнает, есть ли там в бесконечности что-то не стёртое? Она что, должна вечно ленту чистить? ))))))))

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

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

писал(а):
Кстати, слишком длинные сертификаты каким образом отвергаются "быстрее чем линейно от длины входа" ? :)) Ну так не отвергаются они быстрее чем линейно.

А что там смотреть? Сертификат может быть какой угодно длины, а время работы зависит не более, чем от размера слова. Значит, сертификат не читается полностью. Не забывайте про тезися Чёрча - это вычисление и оно может быть сведено к некоторой $MT$. И раз время работы этой $MT$ не зависит от длины сертификата, то и не читает она слишком длиные.

Вот Вам чтобы отвергнуть неинтересную книгу обязательно надо "принять её на вход" целиком? )))) Вот и для $MT$ - не обязательно.

[mihaild]

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

И все эти классы $NP$, $P$ - это именно про алгоритмы, результат работы которых можно сопоставить этому языку.

$P$ и $NP$ - это классы языков. Что тот, что другой можно определять многими разными способами. Например, язык принадлежит $P$, если существует МТ, работающая полиномиальное от длины входа время и распознающая этот язык; язык принадлежит $NP$, если НМТ, работающая полиномиальное от длины входа время и распознающая этот язык.

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

И у языка может быть и алгоритм, относящий его в класс $NP$ и алгоритм, относящий его в класс $P$. Язык от этого никак не меняется.

Ну да. Язык может принадлежать одновременно и $P$, и $NP$ (более того, $P \subseteq NP$).

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

МТ начинает работать, когда на ленте уже есть данные. И дойдя до ерунды, она может остановится, выдав отрицательный результат.

Нет, не может.
Вход записывается в алфавите, не содержащем $\#$. Начальная конфигурация МТ: состояние - выделенное начальное, на ленте написано $\ldots\#\#\#\overline{x_1}x_2x_3\ldots x_n\#\#\#\ldots$, обозревается надчеркнутая ячейка. Конечная конфигурация: $\ldots\#\#\#\overline{t}\#\#\#\ldots$, $t \in \{0, 1\}$, обозревается надчеркнутая ячейка.
Упражнение: доказать, что число шагов для перехода от начального состояния к конечному не меньше чем $n - 1$.

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

А что там смотреть? Сертификат может быть какой угодно длины, а время работы зависит не более, чем от размера слова.

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

$L(x) = \exists y((|y| < q(|x|)) \wedge R(x, y))$, где $q(\cdot)$ - полином, а $R(\cdot, \cdot) \in P$.

Т.е. существует алгоритм, проверяющий сертификат, работает за полиномиальное от длины слова и длины сертификата время, и слово принадлежит языку тогда и только тогда, когда существует полиномиальной длины сертификат (легко доказывается, что можно добавить требование $\forall x \forall y: |y| \geqslant q(|x|) \rightarrow \neg R(x, y)$ и получится эквивалентное определение).

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

[dmitgu]

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

Вход записывается в алфавите, не содержащем $\#$. Начальная конфигурация МТ: состояние - выделенное начальное, на ленте написано $\ldots\#\#\#\overline{x_1}x_2x_3\ldots x_n\#\#\#\ldots$, обозревается надчеркнутая ячейка. Конечная конфигурация: $\ldots\#\#\#\overline{t}\#\#\#\ldots$, $t \in \{0, 1\}$, обозревается надчеркнутая ячейка.
Упражнение: доказать, что число шагов для перехода от начального состояния к конечному не меньше чем $n - 1$.
dmitgu в сообщении #1253040

писал(а):

Так как $MT$ узнаёт, когда ей заканчивать чистить ленту? )))

Вы согласны, что $MT$ может работать меньшее количество шагов, чем размер данных на ленте? Вы согласны, что можно условится, какой символ под кареткой означает "слово принято" или "слово отвергнуто"? Ну и зачем чистить тогда? Это вообще бессмысленное предложение делать то, в чём нет никакой нужды.

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

$\forall x \forall y: |y| \geqslant q(|x|) \rightarrow \neg R(x, y)$ и

Отлично, а как на уровне алгоритмов реализовать эту Вашу проверку $|y| \geqslant q(|x|)$ ? Уж не пройтись ли по $y$ до символа на $q(|x|) + 1$ месте? )))) Ну не правильная у Вас установка про обязательность "принимать целиком". Давайте Вы подумайте до завтра, а то я от работы отвлекаюсь ) И спасибо за Вашу точку зрения - свои расхождения с принятым вокруг пониманием мне иначе не понять.

[mihaild]

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

Так как $MT$ узнаёт, когда ей заканчивать чистить ленту?

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

Вход записывается в алфавите, не содержащем $\#$.

Дошли до $\#$ - слово кончилось.

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

Вы согласны, что $MT$ может работать меньшее количество шагов, чем размер данных на ленте?

Может. Но тогда она точно не вычисляет булеву функцию.

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

Ну и зачем чистить тогда?

Это стандартное определение. Я указал источник, откуда оно взято.
Если хотите - можете предложить свое. Естественно, сформулировав его хотя бы на том же уровне строгости, что и указанное и доказав, что классы языков $P$ и $NP$ по вашему и стандартному определению совпадают.
Могу предложить свое: выделяем у МТ два финальных состояния - "принимающее" и "отвергающее", требуем, чтобы она останавливалась в одном из них за полиномиальное от длины входа время - это будет $P$. $NP$ определяется через $P$ стандартным образом (для определения $NP$ через $P$ понятие алгоритма вообще не нужно).

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

Отлично, а как на уровне алгоритмов реализовать эту Вашу проверку $|y| \geqslant q(|x|)$ ?

Идем по $y$, считаем символы, сравниваем с $q(|x|)$. Это всё занимает полиномиальное по $|y| + |x|$ время. Расписывать подсчет длины на МТ не буду, извините:)

-- 04.10.2017, 17:03 --

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

свои расхождения с принятым вокруг пониманием мне иначе не понять

Попробуйте прочитать учебник, в хороших источниках все определения явно выписываются.

[dmitgu]

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

Идем по $y$, считаем символы, сравниваем с $q(|x|)$. Это всё занимает полиномиальное по $|y| + |x|$ время. Расписывать подсчет длины на МТ не буду, извините:)

Отлично - а после - чистим? )))) Весь - возможно - экспоненциально огромный сертификат? И какая же тогда тут ограниченность работы от размера слова? Тут не то что полиномиальной - тут вообще никакой нет )))

В общем, операция по очистке - бред, не имеющий никакого отношения к собственно вопросу. Как машина останавливается и что она обозначает - это вообще вопрос условный и называется "соглашение о способе кодирования на ленте в момент остановки" (Дж. Булос, Р. Джеффри "Вычислимость и логика"). Кроме стандартной машины Тьюринга есть половинная и есть многоленточная. В логике доказано, что они все эквивалентны в смысле возможностей вычисления. Но! У нас вопрос не вычислимости, а ещё и скорости. Поэтому из всех вариантов мы выбираем тот, который считает быстрее прочих. Там, где неполиномиально долго - бред, устройство приносит сложность, а не сам вопрос.

Я когда попробовал написать в журнал (в 2015 - один раз было) и там была ошибка, но до ошибки дело не дошло. Возражения были те, что я не использую Гёделевы номера. Гёделевы номера, Карл! Это где число 10 записывается как 1111111111. При том, что даже в упомянутом Дж. Булос и Р. Джеффри используется позиционный способ записи вместо гёделевых номеров. А с гёделевыми номерами никакую полиномиальность не докажешь. Вот с этими "определениями" для "конечных состояний" - та же беда. Расчётов требует не решение задачи, а соответствие определениям, которые можно сделать совершенно иными. Вот берем 2-ленточную машину. На одной данные, на другой - результат. И ничего не чистим. Довольны? Допустимое кодирование состояния. Или берем половинную ленту Тьюринга и результат пишем в самой начальной клетке. Ничего не чистим. Годится? Да.

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

[Xaositect]

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

Я когда попробовал написать в журнал (в 2015 - один раз было) и там была ошибка, но до ошибки дело не дошло. Возражения были те, что я не использую Гёделевы номера. Гёделевы номера, Карл! Это где число 10 записывается как 1111111111.

Это не геделевы номера, это называется унарная кодировка. Геделевы номера - это способ кодирования формул теории предикатов (или вообще слов в счетном алфавите) числами.