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

[dmitgu]

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

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

Ну, в "Основаниях математики" Гильберта и Бернайса где всё это аккуратно строится, используется "стандартная модель интерпретации" для арифметики. А в ней как раз унарное представление и вот эти наборы счётных палочек позволяет по своему количеству отыскать формулу. Перемножение простых чисел! Это как раз задача из числа предположительно не сводимых к классу $P$. Тут даже и при позиционном представлении будешь искать - что это за формула - неполиномиальное время )

Повторю обсуждаемый п.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$ и почему размер вывода будет допустимого размера – изложены в следующем разделе.

[mihaild]

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

И какая же тогда тут ограниченность работы от размера слова?

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

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

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

Есть разные определения, если мы говорим о вопросе P vs NP, то можно брать любое из полиномиально эквивалентных определений. Например, есть теорема, что если какой-то язык распознается двуленточной МТ за время $t(n)$, то он распознается одноленточной за $O(t^2(n))$. Т.к. степень полинома может зависеть даже от небольших изменений в модели (например, двуленточная МТ умеет распознавать полиномы за линейное время, а одноленточная - нет), то за ней обычно не следят.

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

Ладно, давайте зафиксируем:
0. В определении МТ фиксируем два выделенных состояния начальное состояние и два финальных - принимающее и отвергающее.
1. МТ распознает язык $L \subseteq \{0, 1\}^*$, если для любого слова из $L$ она приходит в принимающее состояние, а для любого слова не из $L$ - в отвергающее.
2. МТ называется полиномиальной, если существуе такой полином $p(n)$, что для любого входа $x$ время ее работы на входе $x$ не превосходит $p(|x|)$.
3. $P$ - множество языков, для которых существует полиномиальная распознающая их МТ.
4. Язык $L$ принадлежит $NP$ в том и только в том случае, если существуют язык $L^'$, принадлежащий $P$ и полином $q(n)$ такие что $x \in L \leftrightarrow \exists y: |y| < q(|x|) \wedge \overline{x,y} \in L^'$ (где $\overline{x,y}$ обозначает какой-нибудь разумный способ кодирования пар).

Согласны?

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

[Karan]

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

Повторю обсуждаемый п.6 в начале новой страницы:

Не надо, всегда можно поставить ссылку.

dmitgu. Я честно попытался прочитать Ваш текст, но я не понимаю уже в первом параграфе, какое соотвествие имеется в виду. А потом начинают использовать разные обозначения типа $AntiSol$, которые, возможно, вводились в предыдущих параграфах.

Я предлагаю такой режим работы:
Сначала мы фиксируем все стандартные определения, как предложил mihaild. Эти определения мы фиксируем, чтобы все думали об одном и том же и называли одними и теми же словами одни и те же вещи. Если они Вам не нравятся - давайте свой вариант, с двухленточными машинами или как-нибудь еще, главное, чтобы было эквивалентно.
Далее: Вы пишете часть текста, не больше пары абзацев, который опирается на зафиксированные ранее определения. Собеседники отмечают в этой части непонятные термины и делают другие замечания. Вы их учитываете и текст правите. После нескольких итераций мы его фиксируем и переходим к следующему фрагменту.

[dmitgu]

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

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

То есть, Вы согласны, что принять/отвергнуть слово в некоторых случаях можно за меньшее количество шагов, чем размер полученных данных?

С остальным - я реально трудно воспринимаю новые языки/формализмы. Так что наверно утром попробую понять. Вы слишком формализуете - на примере "определения" результата работы $MT$ c идеей очистки всего - это довольно очевидно ) Может, попробуете понятней излагать? Я к Вашим определениям теперь буду с осторожностью относиться )))

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

1. МТ распознает язык $L \subseteq \{0, 1\}^*$, если для любого слова из $L$ она приходит в принимающее состояние, а для любого слова не из $L$ - в отвергающее.

Это алгоритм $Ls$ или $Sol$? Для $NP$ вроде не похоже - нет сертификатов и слово принимается/отвергается только на основании самого себя. То есть - это алгоритм, относящий язык в $P$ ? Судя по следующиим пунктам - да

С остальным вроде, согласен. Но, наверно, до завтра отложу общение...

-- 04.10.2017, 22:31 --

Karan в сообщении #1253113 писал(а):

Я предлагаю такой режим работы:

Я подумаю, ок. Но завтра, ладно? )

[mihaild]

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

То есть, Вы согласны, что принять/отвергнуть слово в некоторых случаях можно за меньшее количество шагов, чем размер полученных данных?

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

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

Это алгоритм $Ls$ или $Sol$?

Не знаю. Я полностью согласен с предложением Karan, так что я как минимум временно забыл, что такое $Ls$ и $Sol$ (хотя кажется я никогда этого и не знал).

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

То есть - это алгоритм, относящий язык в $P$ ?

Нет, в п.1 про время еще вообще ничего не говорится.

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

Вы слишком формализуете - на примере "определения" результата работы $MT$ c идеей очистки всего - это довольно очевидно

А без формализации можно потратить еще 16 страниц и так ни до чего не дойти.

Если что-то в моих сообщениях непонятно - спрашивайте, конечно.
(но учтите, что формальная часть важнее "объяснения")

-- 04.10.2017, 22:01 --

(Оффтоп)

И это форум, тут никто не ставит никаких ограничений по срокам ответов. Вполне можно писать их когда удобно, без дополнительных уведомлений.

[dmitgu]

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

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

В данном случае это принципиально. Мы рассматриваем не просто вопросы вычислимости, но для нас принципиальным является и время (его оценка с точки зрения некоторых полиномов, по крайней мере), которое уходит на вычисления. Машина Тьюринга первоначально "изобреталась" для решения вопросов только вычислимости и тезичс Чёрча, кстати, формулировался для того же. Вы отдаёте себе отчёт, что для соответствия новым требованиям теории алгоритмов нам необходимо конкретизировать то, что соответствует этим требованиям к времени работы? И Ваше определение этим требованиям - не соответствует. Покайтесь ))))

Ну, в общем - договорились в силу не условностей, а принципиальной необходимости. Ок?

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

МТ распознает язык $L \subseteq \{0, 1\}^*$

А, это означает, что слова языка $L$, которые состоят из 1 и 0. Что там не один бит, а их конечная упорядоченная последовательность - это звёздочка что ли обозначает? Ну и да, время работы тут не оговаривается (кроме конечности). Вот чем хуже сказать, что у нас некоторый язык, а слова конечные из букв и цифр? ) Ок, буду спрашивать )

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

Я полностью согласен с предложением Karan

Ок. Давайте так и попробуем сделать.

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

[пианист]

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

[quote="mihaild в [url=http://dxdy.ru/post1253123.html#p1253123]
Что там не один бит, а их конечная упорядоченная последовательность - это звёздочка что ли обозначает?

https://ru.wikipedia.org/wiki/%D0%97%D0 ... 0%BD%D0%B8

[dmitgu]

пианист в сообщении #1253670 писал(а):

Что там не один бит, а их конечная упорядоченная последовательность - это звёздочка что ли обозначает? https://ru.wikipedia.org/wiki/%D0%97%D0 ... 0%BD%D0%B8

Спасибо. Там, кстати, фраза "Широко применяется в регулярных выражениях" вносит путаницу - звёздочка там применяется сама по себе - обозначая любую строку, а не как "надмножество" какого-то $V$, написанного слева от звёздочки.

[mihaild]

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

Вы отдаёте себе отчёт, что для соответствия новым требованиям теории алгоритмов нам необходимо конкретизировать то, что соответствует этим требованиям к времени работы?

Каким требованиям-то?

Все стандартные определения (одноленточная МТ, многоленточная МТ, RAM, ...) полиномиально эквивалентны. Т.е., в частности, если некоторый язык распознается за полиномиальное время (от длины входа) в одной из этих моделей, то и в других он распознается за полиномиальное время.

Впрочем, если хотите, можете попробовать ввести другую модель вычислений. Только определите ее строго, прежде чем переходить дальше.

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

Ну и да, время работы тут не оговаривается (кроме конечности).

Не оговаривается. Это общее определение "МТ распознает язык". Про время можно уже говорить дальше - "существует МТ, работающая за $f(n)$ и распознающая язык".
Это стандартный подход в математике - мы сначала определяем разные понятия (например "МТ распознает язык" и "МТ работает за такое-то время", а потом собираем из них более сложные).

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

Вот чем хуже сказать, что у нас некоторый язык, а слова конечные из букв и цифр?

Существуют языки, которые не распознаются никакой МТ.
Сделать алфавит побольше (но всё равно фиксированным и конечным) - ничем не хуже. Если хотите, можете добавить еще символы.
Обычно с этим не заморачиваются, т.к. если мы возьмем больший алфавит и просто будем кодировать буквы из него последовательностями нулей и единиц фиксированной длины, то время распознавания исходного и нового языков отличается не более чем в константу раз.

(Оффтоп)

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

звёздочка там применяется сама по себе - обозначая любую строку, а не как "надмножество" какого-то $V$, написанного слева от звёздочки

А это зависит от синтаксиса регулярок.

perlre documentation писал(а):

* Matches the preceding element 0 or more times

[dmitgu]

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

Все стандартные определения (одноленточная МТ, многоленточная МТ, RAM, ...) полиномиально эквивалентны.

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

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

[mihaild]

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

Ваше определение не было "полиномиально эквивалентно".

Было. Полином считается от длины входа (и времени работы).

[Xaositect]

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

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

Нет, имеется в виду: если в одной модели задача решается за не более $p(n)$ шагов, где $p$ - некоторый полином, $n$ - размер входа, то существует полином $q$, для которого в другой модели эта задача решается за не более $q(n)$ шагов.

Стереть что-нибудь можно за время, пропорциональное его длине, так что полиномиальность относительно длины входа сохранится.

[Someone]

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

Ваше определение не было "полиномиально эквивалентно". Потому что идея очистки приводит к неполиномиально огромному количеству шагов там, где в реальности они не нужны.

Почему? Если МТ работала полиномиальное время и получила результат с мусором, то замусорить она могла только участок полиномиальной длины.

[dmitgu]

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

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

Да, но определить, что слово не принадлежит языку можно гораздо быстрее. Если языку не принадлежат никакие слова, начинающиеся с "1111", то смотреть слово целиком - нет никакой необходимости. А оно может быть сколь угодно огромным. И "соглашение о кодировании ленты после остановки", включающее в себя "очистку" этой бездны - неприемлемо с точки зрения соответствия полиномиальности времени работы на проверку. К собственно проверке эта "очиска" не относится никак. Что тут не понятного?

[Someone]

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