2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 8  След.
 
 P vs NP .
Сообщение12.01.2019, 02:43 


05/07/18
159
Из далекой-далекой галактики.
На множестве всех слов ${\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$ .

 Профиль  
                  
 
 Re: P vs NP .
Сообщение12.01.2019, 16:12 


05/07/18
159
Из далекой-далекой галактики.
Предмет обсуждения в данной теме : критика полученного результата и возможное продолжение дискуссии.

 Профиль  
                  
 
 Re: P vs NP .
Сообщение12.01.2019, 16:46 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
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).
Расстояние Левенштейна между словом и сертификатом может зависеть от слова.

 Профиль  
                  
 
 Re: P vs NP .
Сообщение12.01.2019, 17:01 


05/07/18
159
Из далекой-далекой галактики.
mihaild в сообщении #1367968 писал(а):
Нет, не так. Как минимум класс $NP$ является множеством языков, а не слов.

Согласитесь, что язык - это множество слов ,а на них и налагается условие принадлежности языку.
mihaild в сообщении #1367968 писал(а):
Что такое $u(x)$ и что такое $m$?

$u(x)$ - сертификат для слова $x$ , $m$ - радиус $B_m(n)$ .
mihaild в сообщении #1367968 писал(а):
Расстояние Левенштейна между словом и сертификатом может зависеть от слова.

Согласен ,но данное условие подразумевается ,когда упоминается зависимость длины сертификата от слова $x$ .
mihaild в сообщении #1367968 писал(а):
А у меня получилось, что шар радиуса $1$ с центром в $01$ содержит не $5$ а $8$ точек

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

 Профиль  
                  
 
 Re: P vs NP .
Сообщение12.01.2019, 17:07 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Ioda в сообщении #1367970 писал(а):
Согласитесь, что язык - это множество слов ,а на них и налагается условие принадлежности языку
У вас написано: "класс языков $NP$ определяется как множество слов, таких что ...". Я не могу прочитать это иначе как "$NP$ - это множество (каких-то) слов". А должно быть примерно так: "$NP$ - это множество языков; язык $L$ принадлежит $NP$ тогда и только тогда, когда существует МТ $M$ и константа $c$, такие что ...".
Ioda в сообщении #1367970 писал(а):
, $m$ - радиус $B_m(n)$ .
Какого $B_m$? Напишите, пожалуйста, формулировку полностью, явно связав все переменные кванторами.
Ioda в сообщении #1367970 писал(а):
Согласен ,но данное условие подразумевается ,когда упоминается зависимость длины сертификата от слова $x$ .
Проблема в том, что если для разных слов вы рассматриваете шары разного радиуса, то число точек в шаре уже не обязано быть полиномом от длины $x$.

 Профиль  
                  
 
 Re: P vs NP .
Сообщение12.01.2019, 17:28 


05/07/18
159
Из далекой-далекой галактики.
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$ количество точек в шаре какого-то радиуса одинаково.

 Профиль  
                  
 
 Re: P vs NP .
Сообщение12.01.2019, 17:41 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Я имел в виду - напишите полностью формулировку вашей теоремы 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}$ слов)

 Профиль  
                  
 
 Re: P vs NP .
Сообщение12.01.2019, 17:58 


05/07/18
159
Из далекой-далекой галактики.
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)$$
Такая формулировка нормальна?

 Профиль  
                  
 
 Re: P vs NP .
Сообщение12.01.2019, 19:03 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Ioda в сообщении #1367985 писал(а):
где $m$ - параметр ,который равен радиусу шара с центром в $x$
Какого шара?

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

 Профиль  
                  
 
 Re: P vs NP .
Сообщение12.01.2019, 19:08 


05/07/18
159
Из далекой-далекой галактики.
mihaild в сообщении #1368002 писал(а):
Это, конечно же, неправда.

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

 Профиль  
                  
 
 Re: P vs NP .
Сообщение12.01.2019, 19:18 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: P vs NP .
Сообщение12.01.2019, 19:31 


05/07/18
159
Из далекой-далекой галактики.
mihaild
Я не совсем понял ваш пример . Пожалуйста, приведите еще пример ,чтобы я понял суть возражений.

 Профиль  
                  
 
 Re: P vs NP .
Сообщение12.01.2019, 19:33 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: P vs NP .
Сообщение12.01.2019, 19:38 


05/07/18
159
Из далекой-далекой галактики.
mihaild в сообщении #1368014 писал(а):
Расстоянием Левенштейна между входом и подсказкой в таком случае

Более конкретно, во всех подобных случаях?
mihaild в сообщении #1368009 писал(а):
Расстоянием Левенштейна между входом и подсказкой в таком случае будет длина слова $+$ длина подсказки.

Хм , одним из свойств расстояния Левенштейна является:
$$d(x,y)\leqslant\max\limits_{}(|x|,|y|)$$
В данном случае ,если верить вам ,данное не соблюдается. Значит расстояние Левенштейна не годится для работы с этим пространством?

 Профиль  
                  
 
 Re: P vs NP .
Сообщение12.01.2019, 19:43 
Заслуженный участник
Аватара пользователя


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

-- 12.01.2019, 19:58 --

Ioda в сообщении #1368018 писал(а):
В данном случае ,если верить вам ,данное не соблюдается
Тут уже я наврал, конечно - забыл про удаления. Ну да, расстоянием между словом и подсказкой будет максимум из их длин.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 113 ]  На страницу 1, 2, 3, 4, 5 ... 8  След.

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



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

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


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

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