P vs NP .

[mihaild]

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

[Ioda]

Если я не ошибаюсь, то оценка данного полинома есть $O(n^n)$ ,что не есть гуд.

-- 13.01.2019, 00:06 --

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

[Ioda]

Теорема .

$$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$ ,что и требовалось доказать.
Оцените пожалуйста ,укажите на ошибки . Я считаю ошибкой в своем доказательстве то ,что не имея алгоритма перебора языков определенного класса сложности их просто нельзя перечислить. Это верно?

[mihaild]

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

Рассмотрим последовательность многоугольников $\gamma_k=[L_0,L_{1k},\dots,L_{n_kk}]$ в пространстве $P$

Что такое "многоугольник в пространстве $P$", что такое $L_{ij}$ и что символизирует набор языков в квадратных скобках?
(пока не появится определений этих понятий дальше читать бесполезно, и я и не пытался)

[Ioda]

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

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

Набор вершин многоугольника.

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

что такое $L_{ij}$

$i$-тая вершина $j$-ого многоугольника.

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

Что такое "многоугольник в пространстве $P$"

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

[mihaild]

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

[Ioda]

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

Тогда дальше - что такое конъюнкция графов?

Это не конъюнкция ,это букет графов.

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

и еще зачем-то $P$ назвали пространством)

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

[mihaild]

А что такое букет? И в каком смысле понимается его равенство $P$?
Попроовал прочитать дальше, всё еще ничего непонятно. Вы, видимо, рассматриваете какие-то отображения на самом множестве $P$. Что вы из этого хотите получить - загадка.

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

$|P|=|NPC|$ ,что равносильно равенству $P=NP$

Что вы тут понимаете под $|P| = |NPC|$? Совпадение мощностей? Оно очевидно, но из него равенство самих множеств еще не следует.

[Ioda]

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

А что такое букет?

Дизъюнктное объединение пространств с минимальным отношением эквивалентности на них ,отождествляющим некоторые отмеченные точки данных пространств.

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

И в каком смысле понимается его равенство $P$?

Изоморфность данного букета пространству $P$ .

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

Совпадение мощностей?

Да.

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

Оно очевидно, но из него равенство самих множеств еще не следует.

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

[mihaild]

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

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

А что вас удивляет? Есть куча разных счетных множеств.

[Ioda]

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

А что вас удивляет?

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

[Ioda]

Теорема . $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)$ и в силу линейности получаем требуемое.
Так как правая часть неравенства оценивается полиномиально ,очевидно ,что левая часть также возрастает полиномиально ,что и требовалось доказать.
Хотелось бы обсудить ещё одно доказательство.

[mihaild]

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$.

[Ioda]

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

Для непустого множества не существует множества всех мультимножеств, состоящего из его элементов.

Это исправляется тем ,что мы определим $X_P$ и $X_{NP}$ как классы ,а не как множества.

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

(разные МТ одно и то же слово распознают за разное время).

Так ,как же тогда определить время распознавания языка?

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

Что такое $\sqcup$?

Дизъюнктное объединение.

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

Это заведомо сделать не получится.

Не знаю , я оптимист .

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

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

(Оффтоп)

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

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

Например - какое место в ваших рассуждениях разваливается если заменить $NP$ на $EXPTIME$?

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

[mihaild]

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

Так ,как же тогда определить время распознавания языка?

Как написано в любом учебнике: машина МТ распознает язык $L$ за время $f(n)$, если для любого слова $x$ она за время, не большее $f(|x|)$ выдает $1$, если слово принадлежит языку, и $0$ иначе.

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

Дизъюнктное объединение.

А что такое дизъюнктное объединение слов?
(если брать стандартное определение слова как множества - функцию из отрезка натурального ряда в алфавит - то объединение двух слов не обязано быть словом)

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

Не знаю , я оптимист .

Да причем тут оптимизм. Это теорема (т.к. существует оракул $A$ такой что $P^A \neq NP^A$, то любое доказательство должно быть принципиально нерелятивизуемым).