2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6 ... 8  След.
 
 Re: P vs NP .
Сообщение12.01.2019, 22:28 
Заслуженный участник
Аватара пользователя


16/07/14
8346
Цюрих
Тогда время работы не ограничено полиномом от длины входа. Если ограничено - напишите какую-нибудь оценку на степень этого полинома хотя бы для простейшего примера, когда подсказка имеет ту же длину, что и слово, но записывается в другом алфавите (соответственно редакционное расстояние между входом и подсказкой в точности равно длине входа).

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


05/07/18
159
Из далекой-далекой галактики.
Если я не ошибаюсь, то оценка данного полинома есть $O(n^n)$ ,что не есть гуд.

-- 13.01.2019, 00:06 --

Кажется понял. Благодарю за дискуссию .

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


05/07/18
159
Из далекой-далекой галактики.
Теорема .
$$P=NP$$
Доказательство.
Зафиксируем во множестве языков $P$ язык $L_0$ . Рассмотрим последовательность многоугольников $\gamma_k=[L_0,L_{1k},\dots,L_{n_kk}]$ в пространстве $P$ таких ,что $n_k\leqslant n_{k+1}$. Тогда верно следующее утверждение.
Лемма 1. Множество $P$ можно представить в следующем виде:
$$\bigvee\limits_{k=1}^{\infty}\gamma_k=P$$
Доказательство.
Опишем процедуру построения данного пространства : возьмём подстановку $\pi_k$ такую ,что она будет переводить $i$-тую вершину $k$-угольника в $i+1$-ую вершину того же многоугольника. Ясно ,что вместе с обратной данной подстановке $\pi^{-1}_k$ они образуют группу с двумя элементами $G_k$. Пусть $\pi_0(L_0)=L_0$ ,далее объединим их во множество $G$ ,учитывая ,что каждая из подстановок действует из $P$ в $P$ видим ,что каждая из них полиномиально вычислима . Таким образом , имеет место представление :
$$P=\bigcup\limits_{k=0}^{\infty}G_kL_0$$
Учитывая то ,что само $GL_0$ имеет подмножествами только многоугольники рассматриваемой последовательности (это легко видеть) ,получаем требуемое.
Введем отображение $g:G\to\mathbb{P}\cup{\frac{1}{p}}  ,  p\in\mathbb{P}$
Пусть $g(\pi_0)=1$ и $g(\pi_k)=p_k$ ,где $p_k$ - $k$-ое простое число. Тогда очевидно ,что $g$ - биекция. Теперь построим тем же ,что и в лемме 1 ,образом множество $NP$-полных задач (далее NPC) :
Фиксируем $L_{0c}\inNPC$
Далее строим многоугольники, как перед леммой 1 , устанавливая на множестве их вершин подстановки . Пусть группы рассматриваемых подстановок многоугольников ,при объединении ,также образуют множество $G_c$ . Применяя лемму 1 для множества $NPC$ ,также видим ,что каждая подстановка полиномиально вычислима . Устанавливая отображение $h:G_c\to\mathbb{P}\cup{\frac{1}{p}}  ,  p\in\mathbb{P}$ ,также легко установить ,что оно биективно . Таким образом $|P|=|NPC|$ ,что равносильно равенству $P=NP$ ,что и требовалось доказать.
Оцените пожалуйста ,укажите на ошибки . Я считаю ошибкой в своем доказательстве то ,что не имея алгоритма перебора языков определенного класса сложности их просто нельзя перечислить. Это верно?

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


16/07/14
8346
Цюрих
Ioda в сообщении #1380609 писал(а):
Рассмотрим последовательность многоугольников $\gamma_k=[L_0,L_{1k},\dots,L_{n_kk}]$ в пространстве $P$
Что такое "многоугольник в пространстве $P$", что такое $L_{ij}$ и что символизирует набор языков в квадратных скобках?
(пока не появится определений этих понятий дальше читать бесполезно, и я и не пытался)

 Профиль  
                  
 
 Re: P vs NP .
Сообщение08.03.2019, 18:21 


05/07/18
159
Из далекой-далекой галактики.
mihaild в сообщении #1380620 писал(а):
что символизирует набор языков в квадратных скобках?

Набор вершин многоугольника.
mihaild в сообщении #1380620 писал(а):
что такое $L_{ij}$

$i$-тая вершина $j$-ого многоугольника.
mihaild в сообщении #1380620 писал(а):
Что такое "многоугольник в пространстве $P$"

Граф - простой цикл со множеством вершин $V=(L_0,L_{1k},\dots,L_{n_kk})$ .
Зачем-то решил назвать многоугольником.

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


16/07/14
8346
Цюрих
Т.е. вы взяли язык, взяли еще $k$ языков, и объявили их вершинами графа? (и еще зачем-то $P$ назвали пространством)
Тогда дальше - что такое конъюнкция графов?

 Профиль  
                  
 
 Re: P vs NP .
Сообщение08.03.2019, 23:45 


05/07/18
159
Из далекой-далекой галактики.
mihaild в сообщении #1380666 писал(а):
Тогда дальше - что такое конъюнкция графов?

Это не конъюнкция ,это букет графов.
Ioda в сообщении #1380680 писал(а):
и еще зачем-то $P$ назвали пространством)

Ну ,не знаю зачем. Но то ,что $P$ можно рассматривать ,как дискретное топологическое пространство думается мне хорошим для него свойством.

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


16/07/14
8346
Цюрих
А что такое букет? И в каком смысле понимается его равенство $P$?
Попроовал прочитать дальше, всё еще ничего непонятно. Вы, видимо, рассматриваете какие-то отображения на самом множестве $P$. Что вы из этого хотите получить - загадка.
Ioda в сообщении #1380609 писал(а):
$|P|=|NPC|$ ,что равносильно равенству $P=NP$
Что вы тут понимаете под $|P| = |NPC|$? Совпадение мощностей? Оно очевидно, но из него равенство самих множеств еще не следует.

 Профиль  
                  
 
 Re: P vs NP .
Сообщение09.03.2019, 00:46 


05/07/18
159
Из далекой-далекой галактики.
mihaild в сообщении #1380689 писал(а):
А что такое букет?

Дизъюнктное объединение пространств с минимальным отношением эквивалентности на них ,отождествляющим некоторые отмеченные точки данных пространств.
mihaild в сообщении #1380689 писал(а):
И в каком смысле понимается его равенство $P$?

Изоморфность данного букета пространству $P$ .
mihaild в сообщении #1380689 писал(а):
Совпадение мощностей?

Да.
mihaild в сообщении #1380689 писал(а):
Оно очевидно, но из него равенство самих множеств еще не следует.

То есть из того ,что множество $NP$-полных языков равномощно множеству языков $P$ не следует равенство классов $P$ и $NP$ ? Печально.

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


16/07/14
8346
Цюрих
Ioda в сообщении #1380697 писал(а):
То есть из того ,что множество $NP$-полных языков равномощно множеству языков $P$ не следует равенство классов $P$ и $NP$ ?
А что вас удивляет? Есть куча разных счетных множеств.

 Профиль  
                  
 
 Re: P vs NP .
Сообщение09.03.2019, 11:57 


05/07/18
159
Из далекой-далекой галактики.
mihaild в сообщении #1380700 писал(а):
А что вас удивляет?

Не удивляет . Но я учту это .

 Профиль  
                  
 
 Re: P vs NP .
Сообщение31.03.2019, 21:39 


05/07/18
159
Из далекой-далекой галактики.
Теорема . $P=NP$
Сформулируем в эквивалентной форме: любой язык принадлежащий классу $NP$ распознаваем за полиномиальное время.
Определение 1. Расширенным классом для класса $P$ (соответственно $NP$) назовем множество $X$ (соответственно $Y$) такое ,что $2^P\subset X$ и содержит все мультимножества состоящие из элементов $P$ (соответственно для $NP$).
Определим функцию $T_M:X\to\mathbb{N}$ , соответственно для $NP$,которая возвращает некоторому входному слову $x$ время его распознавания на детерминированной машине Тьюринга. Примем следующее соотношение:
$$x\sqcup\varepsilon=\varepsilon\sqcup x=x$$
,где $\varepsilon$ - пустое слово.
И примем ,что:
$$nx=\left\lbrace x,\dots,x\right\rbrace=\bigsqcup\limits_{i=1}^nx$$
,где посередине - мультимножество с одним и тем же иксом $n$ раз. Также :
$$x\sqcup y=y \sqcup x =\left\lbrace x,y \right\rbrace$$
Лемма 1. Функция $T_M$ удовлетворяет следующим свойствам :
$$T_M(\varepsilon)=0$$
$$T_M(x\sqcup y)=T_M(x)+T_M(y)$$
$$T(nx)=nT_M(x)$$
Доказательство. Первое равенство следует из тривиальности распознавания пустого слова. Второе равенство легко понять : пусть машина приняла слово $x$ и только закончив работу на нем приняла на вход слово $y$ ,тогда требуемое тривиально ,так как она проработала $n_1+n_2$ тактов ,где $n_1$ и $n_2$ - количество тактов на входах $x$ и $y$ соответственно. Третье равенство - частный случай второго ,если принять за $y$ $x$ и воспользоваться индукцией. Таким образом $T_M$ задаёт норму как на $X$ ,так и на $Y$.
Определим оператор $A:X \to Y$ ,такой что :
$$А(ax\sqcup by)=aA(x)\sqcup bA(y)$$
$$A(P)=NP$$
Также примем ,что он ограничен. Тогда докажем следующее.
Лемма 2. Для оператора $A$ верно ,что существует $c\geqslant 0$ такое,что:
$$T_M(Ax)\leqslant cT_M(x)$$
,для всех $x \in X$
Доказательство. Так как $A$ ограниченный оператор ,он переводит единичный шар в ограниченное множество . Тогда существует $c\geqslant 0$ такое ,что $T_M(Ax)\leqslant c$ , для всех $T_M(x)\leqslant 1$ . Пусть $x\ne\varepsilon$ ,тогда :
$$T_M(A\frac{x}{T_M(x)})\leqslant c$$
Домножаем все на $T_M(x)$ и в силу линейности получаем требуемое.
Так как правая часть неравенства оценивается полиномиально ,очевидно ,что левая часть также возрастает полиномиально ,что и требовалось доказать.
Хотелось бы обсудить ещё одно доказательство.

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


16/07/14
8346
Цюрих
Ioda в сообщении #1385132 писал(а):
содержит все мультимножества состоящие из элементов $P$
Для непустого множества не существует множества всех мультимножеств, состоящего из его элементов.
Ioda в сообщении #1385132 писал(а):
Определим функцию $T_M:X\to\mathbb{N}$ , соответственно для $NP$,которая возвращает некоторому входному слову $x$ время его распознавания
$X$ - это же множество языков, а не слов.
Кроме того, "время распознавания" не является функцией от слова (разные МТ одно и то же слово распознают за разное время).
Кроме того, раз вы пытаетесь определить "расширенные классы" для $P$ и $NP$, то лучше явно писать индексы: $X_P$ и $X_{NP}$.
Ioda в сообщении #1385132 писал(а):
Примем следующее соотношение:
$$x\sqcup\varepsilon=\varepsilon\sqcup x=x$$
Что такое $\sqcup$?
(дальше читать бессмысленно)

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

Вообще, вы упорно пытаетесь доказать $P = NP$ из каких-то общих соображений. Это заведомо сделать не получится.
Например - какое место в ваших рассуждениях разваливается если заменить $NP$ на $EXPTIME$? А достоверно известно что $P \neq EXPTIME$.

 Профиль  
                  
 
 Re: P vs NP .
Сообщение31.03.2019, 22:14 


05/07/18
159
Из далекой-далекой галактики.
mihaild в сообщении #1385133 писал(а):
Для непустого множества не существует множества всех мультимножеств, состоящего из его элементов.

Это исправляется тем ,что мы определим $X_P$ и $X_{NP}$ как классы ,а не как множества.
mihaild в сообщении #1385133 писал(а):
(разные МТ одно и то же слово распознают за разное время).

Так ,как же тогда определить время распознавания языка?
mihaild в сообщении #1385133 писал(а):
Что такое $\sqcup$?

Дизъюнктное объединение.
mihaild в сообщении #1385133 писал(а):
Это заведомо сделать не получится.

Не знаю , я оптимист .
mihaild в сообщении #1385133 писал(а):
Ioda, признайтесь честно - вы на каком-то корпусе натренировали нейросеть и теперь постите слегка поправленные ее результаты? Я не могу придумать другого объяснения, почему вы упорно вводите кучу очень странных понятий без каких-либо определений.

(Оффтоп)

Что ж ,примите меня как нейросеть.

mihaild в сообщении #1385133 писал(а):
Например - какое место в ваших рассуждениях разваливается если заменить $NP$ на $EXPTIME$?

Быть может в существовании оператора с такими свойствами.

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


16/07/14
8346
Цюрих
Ioda в сообщении #1385136 писал(а):
Так ,как же тогда определить время распознавания языка?
Как написано в любом учебнике: машина МТ распознает язык $L$ за время $f(n)$, если для любого слова $x$ она за время, не большее $f(|x|)$ выдает $1$, если слово принадлежит языку, и $0$ иначе.
Ioda в сообщении #1385136 писал(а):
Дизъюнктное объединение.
А что такое дизъюнктное объединение слов?
(если брать стандартное определение слова как множества - функцию из отрезка натурального ряда в алфавит - то объединение двух слов не обязано быть словом)
Ioda в сообщении #1385136 писал(а):
Не знаю , я оптимист .
Да причем тут оптимизм. Это теорема (т.к. существует оракул $A$ такой что $P^A \neq NP^A$, то любое доказательство должно быть принципиально нерелятивизуемым).

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

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



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

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


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

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