P vs NP .

[Ioda]

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

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

Так ,это хорошее предложение , тогда мне придется передоказать лемму 2 ,да?

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

Ну потому что есть "похожие" на $P$ и $NP$ множества языков, которые заведомо не равны. Значит любое доказательство равенства должно заведомо содержать этап, разваливающийся при замене этих классов на "похожие" - а для этого где-то должно использоваться какое-то свойство, которым обладает наш класс, но не обладает "похожий".

Да , действительно, довольно прозрачная идея.

(Оффтоп)

Не об этом ли статья ,которую вы мне предложили?

А мне было бы интересно увидеть примеры "похожих" классов , наверно ,опроверг(ли) бы лемму 2.

[mihaild]

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

Так ,это хорошее предложение , тогда мне придется передоказать лемму 2 ,да?

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

Если хотите переделать - наверное лучше всего начинать с самого начала.

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

А мне было бы интересно увидеть примеры "похожих" классов , наверно ,опроверг(ли) бы лемму 2.

Ну вот например есть оракул, относительно которого $P \neq NP$ ("на пальцах" он довольно простой: подсказка содержит запрос к оракулу, на который он отвечает, принадлежит ли слово языку; т.к. детерменированная МТ, работающая за полином, делает не очень много запросов к оракулу, то для каждой такой МТ мы можем найти слово и запрос, который она не делает на этом слове - и выбрав нужный ответ оракула получить что эта МТ не распознает получающийся язык).

[Ioda]

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

Если хотите переделать - наверное лучше всего начинать с самого начала.

Хорошо.
Далее я буду использовать как ваши ,так и свои обозначения . В частности, это :

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

$t_M(x)$ - время работы МТ $M$ на входе $x$

Так обозначим класс всех конечных мультимножеств ,состоящих из слов ,принадлежащих языкам класса $P$ ,в котором мы введем следующее отношение эквивалентности:

$$x\sim y \Leftrightarrow t_{M_x}(x)=t_{M_y}(y)=1$$

,где $M_x$ и $M_y$ - машины ,распознающие языки ,которым принадлежат $x$ и $y$ ,как $X_P$ . Также определим данный класс для класса $NP$ ,обозначим $X_{NP}$ . Определим операцию $\sqcup : X_P^2 \to X_P$ так ,что для всех $\{x\},\{y\} \in X_P$:

$$\{x\} \sqcup \{y\} = \{x,y\}\ne \{y,x\} = \{y\} \sqcup \{x\}$$

Соответственно данная операция определяется для $X_{NP}$ . Определим следующую краткую запись:

$$nx:=\{x,\dots ,x\} =\bigsqcup_{i=1}^n\{x\}$$

,где $n$ натуральное, и другую краткую запись:

$$\frac{x}{n}:=\{e\}$$

,где $e$ такое ,что $t_{M_e}(e)=1$ ,если $t_M(x)=n$ ,и :

$$\frac{x}{n}:=ke$$

,где $k$ такое ,что $t_M(x)=nk$ ,при естественных ограничениях на $n$ и $k$ .

(Оффтоп)

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

Определим на $X_P$ функцию $T_M : X_P \to \mathbb{N}$ такую ,что :

$$T_M(\{x\})=t_M(x)$$

Лемма 1. Функция $T_M$ удовлетворяет следующим соотношениям:

$$T_M(\{\varepsilon\})=0$$

$$T_M(\{x\} \sqcup \{y\})=T_M(\{x\}) \sqcup T_M(\{y\})$$

$$T_M(nx)=nT_M(\{x\})$$

,где $\varepsilon$ - пустое слово , $x,y\in P$
Доказательство.
1) Следует из тривиальности распознавания пустого слова.
2) Рассмотрим требуемое равенство ,следуя определению $T_M$ :

$$T_M(\{x\}) \sqcup T_M(\{y\})=t_{M_1}(x)+t_{M_2}(y)$$

,где $M_1$ и $M_2$ - машины ,распознающие языки ,которым принадлежат $x$ и $y$ . Тогда ,пусть для распознавания $\{x,y\}$ мы сначала дадим на вход $M_1$ $x$ и только после того ,как получим $M_1(x)$ ,дадим на вход $M_2$ $y$ и получим $M_2(y)$ ,тогда требуемое равенство следует из расписанного так ,как время работы суммируется .
3) Третье равенство - частный случай второго , надо лишь принять $x=y$ и $M_1 \equiv M_2$ (надеюсь тут понятно в каком смысле тождественность) и воспользоваться индукцией и алгоритмом из второго случая .
Замечание. Лемма доказывается аналогично для $X_{NP}$ .
Теперь наши классы ,в каком-то смысле ,"нормированны".
Определим оператор $A : X_P \to X_{NP}$ удовлетворяющий следующим условиям:

$$A(X_P)=X_{NP}$$

$$A(ax \sqcup by) = aA(\{x\}) \sqcup bA(\{y\})$$

Также пусть он будет ограниченным. Тогда докажем следующее утверждение.
Лемма 2. Для оператора $A$ верно ,что существует $c\geqslant 0$ такое ,что:

$$T_M(A(\{x\})) \leqslant cT_M(\{x\})$$

,для всех $x \in X_P$
Доказательство.
Так как $A$ ограничен ,он переводит единичный шар в ограниченное множество. Тогда существует $c\geqslant 0$ такое ,что $T_M(A(\{x\}))\leqslant c$ ,для всех $T_M(\{x\})\leqslant 1$ . Пусть $x\ne \varepsilon$ ,тогда :

$$T_M(A(\frac{x}{T_M(\{x\})}))\leqslant c$$

Домножая на $T_M(\{x\})$, в силу линейности получаем требуемое.
Расписав в явном виде получаем:

$$t_M(A(\{x\}))\leqslant ct_M(x)$$

Отсюда следует утверждение теоремы.

[mihaild]

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

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

$M_x$ и $M_y$ - машины ,распознающие языки ,которым принадлежат $x$ и $y$ ,как $X_P$

Одно и то же слово может принадлежать куче языков, а каждый язык распознаваться кучей машин, так что по слову машина не восстанавливается, и соответственно говорить про время нельзя.

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

$$\{x,y\}\ne \{y,x\}$$

Если фигурные скобки у вас используются в стандартном смысле - то так не бывает. Если в своем, то 1) укажите явно, в каком; 2) (желательно) возьмите другое обозначение.

[Ioda]

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

Если фигурные скобки у вас используются в стандартном смысле

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

-- 02.04.2019, 19:59 --

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

Одно и то же слово может принадлежать куче языков, а каждый язык распознаваться кучей машин

Тогда мы возьмём язык которому принадлежат оба слова и уже для него будем говорить про машину его распознающую .

[mihaild]

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

Наверняка к этой части будет много придирок

Это не придирки. То, что вы пишете, вообще ничего не означает. Самые частые ошибки не следите, на каких множествах действуют какие функции, и говорите "где $x$ - что-то", при этом свойство не однозначно определяет $x$, а дальше $x$ используется так, что разные объекты, удовлетворяющие этому свойству, дадут разные результаты.
Подобные моменты встречаются и в книгах и в статьях - только там легко их исправить, потому что "итак понятно". Раз у вас с этим проблемы - лучше прописывать явно. В частности давайте не будем использовать переменные в индексах: вместо $t_M(x)$ будем писать $t(M, x)$, вместо $M_x$ писать $M(x)$ (и тут явно видно, что нам нужна функция) и т.д.

(круглые скобки кстати тоже неудачная идея, будут путаться с аргументами)

-- 02.04.2019, 20:06 --

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

Тогда мы возьмём язык которому принадлежат оба слова и уже для него будем говорить про машину его распознающую .

Ок, возьмем просто язык, состоящий из всех слов, и машину, которая сначала ничего не делает $10$ операций, а потом записывает на ленту $1$ и останавливается. Тогда никакие два слова не эквивалентны. Пойдет?

[Ioda]

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

Ок, возьмем просто язык, состоящий из всех слов, и машину, которая сначала ничего не делает $10$ операций, а потом записывает на ленту $1$ и останавливается. Тогда никакие два слова не эквивалентны. Пойдет?

Нет , думаю можно попробовать решить следующим образом. Определим бесконечное множество языков $(L_1,L_2,\dots)$ таких ,что :

$$P=\bigcup\limits_{i=1}^{\infty}L_i$$

$$L_i \cap L_j = \varnothing , i\ne j$$

Если что , объединение языков - язык содержащий все слова языков в объединении . Для данного множества зафиксируем бесконечное множество ДМТ $(M_1,M_2,\dots)$ такое ,что $L_i=L_i(M_i)$ . Теперь можно говорить о времени работы?

[mihaild]

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

Определим бесконечное множество языков $(L_1,L_2,\dots)$ таких ,что :

$$P=\bigcup\limits_{i=1}^{\infty}L_i$$

Такого множества языков не существует. У вас в объединении получится язык (множество слов). А $P$ - множество языков (т.е. множество множеств слов).

[Ioda]

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

У вас в объединении получится язык (множество слов)

Это ведь из-за этого:

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

Если что , объединение языков - язык содержащий все слова языков в объединении .

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

[mihaild]

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

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

Нет, нельзя определять объединение не как объединение!
Безусловно, для множества языков $\{L_1, L_2, \ldots\}$ можно рассмотреть множество $\{\cup L_i\}$. Правда не очень понятно зачем. И естественно это множество будет отличаться от $P$ (например потому что оно одноэлементное, а $P$ нет).

[Ioda]

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

Правда не очень понятно зачем.

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

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

И естественно это множество будет отличаться от $P$ (например потому что оно одноэлементное, а $P$ нет)

Ну да. Что если я не буду объединять эти языки из $(L_1,L_2,\dots)$ ,а просто скажу ,что это множество и есть $P$ ? Это корректно?

[mihaild]

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

Что если я не буду объединять эти языки из $(L_1,L_2,\dots)$ ,а просто скажу ,что это множество и есть $P$ ? Это корректно?

Нет, некорректно. $P$ это некоторое конкретное множество, и задача $P =? NP$ именно про него.
Можно, конечно, (неэффективно) пронумеровать все языки из $P$. Правда некоторые языки из $P$ пересекаются.

[Ioda]

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

Можно, конечно, (неэффективно) пронумеровать все языки из $P$. Правда некоторые языки из $P$ пересекаются.

Так пронумеруем, правда , "неэффективно" меня смущает . Для тех языков ,которые пересекаются - для определенности примем ,что множество слов пересечения мы будем распознавать на МТ ,распознающей язык с меньшим номером. Для $NP$ тоже так придется сделать , естественно ,если это возможно.

[mihaild]

И даже к языку МТ не привязана. Ну ладно, можно брать пары (полиномиально работающая МТ, язык).
Давайте для определенности возьмем нумерацию, в которой первым идет язык, состоящий вообще из всех слов (и МТ, которая ничего не читая сразу отвечает "да"). Соответственно что там дальше в нумерации - будет неважно. Сойдет?

(тут всё та же проблема: важны не слова сами по себе, а то, какие слова попадают в язык, а какие нет; просто случайно надергивая слова из разных языков вы теряете принципиально важную информацию, без использования которой ничего доказать уже не получится)

[Ioda]

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

(тут всё та же проблема: важны не слова сами по себе, а то, какие слова попадают в язык, а какие нет; просто случайно надергивая слова из разных языков вы теряете принципиально важную информацию, без использования которой ничего доказать уже не получится)

Согласен , это утверждение слишком важно , но, к сожалению , я не могу ввести условие ,которое дало бы нужную мне информацию. А есть ли такое условие?