P vs NP .

[Ioda]

На множестве всех слов ${\left\lbrace 0,1\right\rbrace}^\ast$ введем топологию $2^{{\left\lbrace 0,1\right\rbrace}^\ast}$ и метрику Левенштейна $d(x,y)$ . Обозначим получившееся метрической пространство $X$ . Тогда язык $L$ в данном пространстве есть подмножество точек данного пространства. Пусть для некоторой точки $x$ ,длина последовательности которой равна $n$ , детерминированная машина Тьюринга $M_D$ последовательно проходит по точкам шара радиуса 1 с центром в точке $x$ ,далее по точкам шара радиуса 2 с тем же центром и так далее пока не пройдет все точки шара радиуса $m$ , начав свой путь в точке $x$ .
Лемма 1. Время работы $M_D$ для шара радиуса $m$ : $T(M_D)=O(n^m)$ .
Доказательство. Рассмотрим вид условия для $m=1$ ,тогда количество точек шара будет равно $n+3$ (по одному изменению символа на i-том месте, всего возможных изменений $n$ , одно удаление символа с $n$-ого места ,добавление одного из двух возможных символов на $n+1$-ое место). То есть $M_D$ обойдет $n+3$ точек и закончит работу за время $O(n)$. Пусть $m=k+1$ (делаю индуктивный переход) ,тогда так как для $m=k$ , $T(M_D)=O(n^k)$ ,то остается лишь оценить количество прибавившившихся точек.
Лемма 2. Количество точек шара радиуса $m$ зависит от полинома $r(n)$ : $r(n)=O(n^m)$ .
Доказательство. Ранее было посчитано ,что в $B_1(n)$ (подразумеваю замкнутый шар радиуса 1) количество точек равно $n+3$ . Посчитаем количество точек в шаре радиуса 2 : количество точек с длиной $n$ равно $n$ ,значит имеем $n(n+3)$ точек от них , количество точек длиной $n+1$ равно 2 ,значит имеем $2(n+1+3)$ точек, также точек с длиной $n-1$ одна точка ,значит имеем от нее $n+2$ точки . В сумме : $n^2+3n+2n+8+n+2=n^2+6n+10$ точек. Очевидно , что так как при оценивании учитывается только член высшего порядка ,то ,как легко показать ,таковым в $r(n)$ является ,при радиусе $m$ , $n^m$ с каким-то коэффициентом ,который не учитывается, поэтому $r(n)=O(n^m)$ ,ч.т.д.
Так для шара радиуса $k+1$ имеем количество точек порядка $O(n^{k+1})$ из этого следует ,что $M_D$ действительно закончит свою работу через время порядка $O(n^m)$ ,ч.т.д.
Класс языков $NP$ определяется ,как множество всех слов $x$ для которых существует слово $u : \left\lvert u \right\rvert \leqslant {\left\lvert x \right\rvert}^c$ , и машина $M_D : M_D(x , u)=1$ . Условие на $u$ можно переформулировать так:

$$\left\lvert u \right\rvert = O(n^c)$$

,где $n$ - длина $x$ . Теперь покажем, что существует машина $M_D$ ,такая что за полиномиальное время она отыскивает сертификат любого слова в $NP$ .
Теорема 1.

$$O(\left\lvert u(x) \right\rvert)=O(n^m)$$

Доказательство. Предположим обратное:

$$O(n^m)=O(\left\lvert u(x) \right\rvert)$$

Тогда заметим ,что:

$$O(n^m)=O(\left\lvert u(x) \right\rvert)=O(n^c)$$

,то есть длина сертификата не зависит от $m$ ,зато мы обязаны сделать зависимой от $m$ константу $c$ ,например так :
$c=m+\varepsilon$
,где $\varepsilon\geqslant 0$ . Таким образом, так как функция $\left\lvert u(x) \right\rvert$ не может лежать между двумя сколь угодно близкими по возрастанию полиномами ,можно заключить, что предположение в начале неверно , ч.т.д. .
Теперь построим $M_D$ . Пусть она проходит по точкам шаров от исходной точки $x$ и подставляет полученные значения. Так как подстановка занимает полиномиальное время и машина работает полиномиальное время (по лемме 1), то обязательно существует такое $m_0$ ,что в $B_{m_0}(n)$ найдется сертификат для $x$ (по теореме 1). А так как ,мы рассматривали произвольное слово $x$ произвольного языка $L \subset NP$ ,то можно заключить ,что $P=NP$ .

[Ioda]

Предмет обсуждения в данной теме : критика полученного результата и возможное продолжение дискуссии.

[mihaild]

Ioda в сообщении #1367882 писал(а):

для $m=1$ ,тогда количество точек шара будет равно $n+3$

А у меня получилось, что шар радиуса $1$ с центром в $01$ содержит не $5$ а $8$ точек: $0$, $1$, $00$, $11$, $001$, $010$, $011$, $101$. Но не принципиально.

Ioda в сообщении #1367882 писал(а):

Класс языков $NP$ определяется ,как множество всех слов $x$ для которых существует слово $u : \left\lvert u \right\rvert \leqslant {\left\lvert x \right\rvert}^c$ , и машина $M_D : M_D(x , u)=1$

Нет, не так. Как минимум класс $NP$ является множеством языков, а не слов.

Ioda в сообщении #1367882 писал(а):

Теорема 1.

$$O(\left\lvert u(x) \right\rvert)=O(n^m)$$

Что такое $u(x)$ и что такое $m$?

Ioda в сообщении #1367882 писал(а):

то обязательно существует такое $m_0$ ,что в $B_{m_0}(n)$ найдется сертификат для $x$ (по теореме 1).

Расстояние Левенштейна между словом и сертификатом может зависеть от слова.

[Ioda]

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

Нет, не так. Как минимум класс $NP$ является множеством языков, а не слов.

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

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

Что такое $u(x)$ и что такое $m$?

$u(x)$ - сертификат для слова $x$ , $m$ - радиус $B_m(n)$ .

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

Расстояние Левенштейна между словом и сертификатом может зависеть от слова.

Согласен ,но данное условие подразумевается ,когда упоминается зависимость длины сертификата от слова $x$ .

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

А у меня получилось, что шар радиуса $1$ с центром в $01$ содержит не $5$ а $8$ точек

Согласен ,просто я не учитывал вставку символов перед началом слова .

[mihaild]

Ioda в сообщении #1367970 писал(а):

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

У вас написано: "класс языков $NP$ определяется как множество слов, таких что ...". Я не могу прочитать это иначе как "$NP$ - это множество (каких-то) слов". А должно быть примерно так: "$NP$ - это множество языков; язык $L$ принадлежит $NP$ тогда и только тогда, когда существует МТ $M$ и константа $c$, такие что ...".

Ioda в сообщении #1367970 писал(а):

, $m$ - радиус $B_m(n)$ .

Какого $B_m$? Напишите, пожалуйста, формулировку полностью, явно связав все переменные кванторами.

Ioda в сообщении #1367970 писал(а):

Согласен ,но данное условие подразумевается ,когда упоминается зависимость длины сертификата от слова $x$ .

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

[Ioda]

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

Какого $B_m$? Напишите, пожалуйста, формулировку полностью, явно связав все переменные кванторами.

$\forall x : \left\lvert x \right\rvert=n$ , $B_m(x)$ - замкнутый шар радиуса $m$ с центром в $x$ (вместо $n$ написал $x$ ,потому что понял ,что зависимость от слова ,а не только от его длины , $m$ является параметром ,его мы можем изменять).

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

$NP$ - это множество языков; язык $L$ принадлежит $NP$ тогда и только тогда, когда существует МТ $M$ и константа $c$, такие что ...

... $\forall x \in L \Leftrightarrow \exists u : \left\lvert u \right\rvert \leqslant {\left\lvert x \right\rvert}^c \& M(x , u)=1$ .
Согласен, я не должен был оставлять лишь часть определения.

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

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

Почему? Ведь ,для слов $x$ и $x'$ одинаковой длины $n$ количество точек в шаре какого-то радиуса одинаково.

[mihaild]

Я имел в виду - напишите полностью формулировку вашей теоремы 1. С явной фиксацией, что рассматривается. Видимо, получится что-то типа "Пусть $L$ - язык из $NP$, $M$ - распознающая его МТ. Определим функцию $u(n)$, ограниченную полиномом, такую что для любого слова $x$ оно принадлежит языку тогда и только тогда, когда существует подсказка длины не больше чем $u(|x|)$ (такая функция существует по определению $NP$)". Продолжите или напишите с нуля, примерно в таком же духе, без введения переменных непонятно откуда.

Ioda в сообщении #1367977 писал(а):

... $\forall x \in L \Leftrightarrow \exists u : \left\lvert u \right\rvert \leqslant {\left\lvert x \right\rvert}^c \& M(x , u)=1$ .

Почти. Правильно так: $\forall x: (x \in L \leftrightarrow \exists u: \ldots)$ (дальше у вас правильно).

Вообще, если я правильно понимаю, у вас идея в том, что подсказку можно искать в каком-то множестве полиномиального от длины $x$ размера. Это так?
Если да - напишите явно, в каком, и почему так можно.
(если скажем подсказке разрешено иметь квадратичную от длины $x$ длину, то подсказкой для слова $x$ "может" оказаться любое из больше чем $2^{|x|^2}$ слов)

[Ioda]

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

Вообще, если я правильно понимаю, у вас идея в том, что подсказку можно искать в каком-то множестве полиномиального от длины $x$ размера. Это так?

Так.

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

Если да - напишите явно, в каком, и почему так можно.

В шаре какого-нибудь радиуса ,в пространстве $X$ .
В том ,почему так можно ,заключается суть теоремы 1.
Теорема 1.

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

Пусть $L$ - язык из $NP$, $M$ - распознающая его МТ. Определим функцию $u(n)$, ограниченную полиномом, такую что для любого слова $x$ оно принадлежит языку тогда и только тогда, когда существует подсказка длины не больше чем $u(|x|)$

... . Тогда длина данной подсказки возрастает не более ,чем полином $n^m$ ,где $m$ - параметр ,который равен радиусу шара с центром в $x$ . То есть :

$$O(u(|x|))=O(n^m)$$

Такая формулировка нормальна?

[mihaild]

Ioda в сообщении #1367985 писал(а):

где $m$ - параметр ,который равен радиусу шара с центром в $x$

Какого шара?

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

[Ioda]

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

Это, конечно же, неправда.

Почему? Объясните пожалуйста.

[mihaild]

Возьмем, скажем, 3SAT, в таком виде: на вход нам подается строка вида $(\neg x123 \vee x4 \vee x7) \wedge (x9 \vee \neg x5 \vee x321)$ (прямо так, со скобками и знаками операций, т.е. строка в алфавите $()\neg\vee\wedge x 1234567890$. Подсказкой пусть будет строка в алфавите $\top \bot$ длины, равной максимальному номеру переменной в формуле. Проверять это всё понятно как. Расстоянием Левенштейна между входом и подсказкой в таком случае будет длина слова + длина подсказки.

[Ioda]

mihaild
Я не совсем понял ваш пример . Пожалуйста, приведите еще пример ,чтобы я понял суть возражений.

[mihaild]

Напишите более конкретный вопрос. Мне кажется, что всё, что я пишу, должно быть без проблем понятно любому, знакомому с основами теории алгоритмов.
Если вы с ней не знакомы - вам, скорее всего, для понимания хватит первой пары параграфов из "Классических и квантовых вычисления" Вялого, Китаева, Шеня.

[Ioda]

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

Расстоянием Левенштейна между входом и подсказкой в таком случае

Более конкретно, во всех подобных случаях?

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

Расстоянием Левенштейна между входом и подсказкой в таком случае будет длина слова $+$ длина подсказки.

Хм , одним из свойств расстояния Левенштейна является:

$$d(x,y)\leqslant\max\limits_{}(|x|,|y|)$$

В данном случае ,если верить вам ,данное не соблюдается. Значит расстояние Левенштейна не годится для работы с этим пространством?

[mihaild]

Не знаю, что такое "подобные случаи". Я привел (почти совсем строго) конкретный язык из $NP$ и машину, распознающую этот язык с подсказкой, такие что расстояние Левенштейна от слова из языка до подсказки не ограничено никакой константой. Следовательно, любые попытки искать подсказку только внутри шара фиксированного (не зависящего от входа) радиуса с центром во входе, обречены на провал.

-- 12.01.2019, 19:58 --

Ioda в сообщении #1368018 писал(а):

В данном случае ,если верить вам ,данное не соблюдается

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