P vs NP .

[Ioda]

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

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

Значит для каждого слова $x$ функция $T_M$ возвращает время $f(|x|)$ ,для машины $M_L$ ,распознающей язык $L$ .

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

А что такое дизъюнктное объединение слов?

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

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

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

Так , $EXPTIME$ определяется ,как множество языков распознаваемых за экспоненциальное время ,значит доказательство развалится на неравенстве. В случае $NP$ такого не наблюдается.

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

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

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

[mihaild]

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

Значит для каждого слова $x$ функция $T_M$ возвращает время $f(|x|)$ ,для машины $M_L$ ,распознающей язык $L$ .

Так значит функция еще и от МТ зависит? Ладно, но для $NP$ всё другое определение нужно - там машины кроме самого слова еще подсказку берут, и время работы может зависеть от длины подсказки.

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

Так $T_M$ и определена на множествах

Да подождите с $T_M$. Что такое дизъюнктное объединение слов?
(а $T_M$ только что была определена на множествах языков, а не слов)

В общем если хотите чтобы можно было что-то понять - четко описывайте все используемые понятия и "кто на ком стоял".

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

Например ,про нерелятивизуемость

Relativizations of $\mahrm P =? \mathrm{NP}$ question

[Ioda]

Здесь

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

Примем следующее соотношение:

$$x\sqcup\varepsilon=\varepsilon\sqcup x=x$$

Я отождествил множество $\left\lbrace x \right\rbrace$ со словом $x$ ,поэтому скозноязычил насчёт дизъюнктного объединения . Естественно дизъюнктное объединение определяется классически - как для множеств . Тогда функция $T_M$ определена на множествах .

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

Ладно, но для $NP$ всё другое определение нужно - там машины кроме самого слова еще подсказку берут

Тогда пусть машина сначала ищет подсказку ,и только после этого начинает поиск ответа.

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

Relativizations of $\mahrm P =? \mathrm{NP}$ question

Спасибо ,прочту . Жаль ,что я мало понимаю английский.

[mihaild]

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

Я отождествил множество $\left\lbrace x \right\rbrace$ со словом $x$ ,поэтому скозноязычил насчёт дизъюнктного объединения .

Тогда перепишите часть до леммы нормально, без отождествления принципиально разных объектов. И без "принятий" - явно пропишите, что является определением, а что доказывается как следствие.

[Ioda]

Поправленная версия.
Определение 1. Расширенным классом $X_P$ для класса $P$ назовем класс (в смысле теории множеств $ZFC$) ,который содержит все элементы $P$ ,множество всех подмножеств $P$ ,и все мультимножества состоящие из элементов $P$.
Также определим данный класс (в т.м.) над классом $NP$ ,обозначим его $X_{NP}$ .
Далее ,пусть на обоих классах определена операция $\sqcup : X_P^2 \to X_P $ (соответственно $\sqcup : X_{NP}^2 \to X_{NP}$) такая ,что :

$$\forall \left\lbrace x\right\rbrace \in X_P ( \left\lbrace x \right\rbrace \sqcup \left\lbrace\varepsilon\right\rbrace = \left\lbrace\varepsilon\right\rbrace \sqcup \left\lbrace x\right\rbrace = \left\lbrace x\right\rbrace)$$

$$\forall \left\lbrace x\right\rbrace , \left\lbrace y\right\rbrace \in X_P ( \left\lbrace x\right\rbrace \sqcup \left\lbrace y\right\rbrace = \left\lbrace y\right\rbrace \sqcup \left\lbrace x\right\rbrace = \left\lbrace x,y \right\rbrace )$$

,где $\varepsilon$ - пустое слово ,а $x,y \in P$ . Далее определим следующее обозначение :

$$nx := \left\lbrace x,\dots ,x\right\rbrace = \bigsqcup_{i=1}^nx$$

Аналогично , то есть с сохранением всех вышеперечисленных свойств ,данная операция определяется для $X_{NP}$ . Дальше по тексту .

[Ioda]

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

$$nx := \left\lbrace x,\dots ,x\right\rbrace = \bigsqcup_{i=1}^nx$$

Последнее должно быть так:

$$\bigsqcup_{i=1}^n\left\lbrace x \right\rbrace$$

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

Тогда перепишите часть до леммы нормально

Надеюсь часть до леммы 1 вышла нормально.
Определим функцию $T_M : X_P \to \mathbb{N}$ (соответственно $T_M : X_{NP} \to \mathbb{N}$),такую что она сопоставляет каждому множеству время распознавания его элементов. Тогда докажем лемму 1.
Лемма 1. Функция $T_M$ удовлетворяет следующим соотношениям:

$$T_M(\left\lbrace\varepsilon\right\rbrace)=0$$

$$T_M(\left\lbrace x \right\rbrace \sqcup \left\lbrace y \right\rbrace)=T_M(\left\lbrace x \right\rbrace)+T_M(\left\lbrace y \right\rbrace)$$

$$T_M(nx)=nT_M(\left\lbrace x \right\rbrace)$$

Доказательство. Первое равенство следует из тривиальности распознавания пустого слова. Второе равенство рассмотрим так: пусть машина $M_1$ ,распознающая язык $L_1$ , которому принадлежит $x$ ,принимает его на вход и только после окончания работы на нем ,мы даём машине $M_2$ распознающей язык $L_2$ ,которому принадлежит $y$ ,принимает его на вход и после окончания работы мы складываем количество тактов на первой и второй машинах ,из чего тривиально следует требуемое. Третье равенство - частный случай второго ,если принять ,что $y=x$ и воспользоваться индукцией ,в рассуждениях для первого равенства (игнорируя имеющее место тривиальное повторение результата). Запишем рассуждения для третьего равенства: пусть машина $M$ приняла на вход $x$ ,когда она закончит работать ,мы дадим ей же на вход $x$ ещё раз ,и она снова повторит прошедшие такты, далее по индукции требуемое очевидно.

[mihaild]

Существует расширенный класс $X_P$, не содержащий $\{\varepsilon\}$. Так что вы можете пытаться применять $\sqcup$ к чему-то, на чем она не определена.

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

такую что она сопоставляет каждому множеству время распознавания его элементов

Что такое "время распознавания мультимножества языков"?

[Ioda]

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

Что такое "время распознавания мультимножества языков"?

Сумма количества тактов ,которые сделают машины ,распознающие языки из данного мультимножества ,распознавая языки в данном мультимножестве ,причём мы принимаем ,что для одного языка ,даже если он повторяется в мультимножестве , используется одна и та же машина. Формально :

$$T_M(\{L_1,\dots , L_n\})=\sum\limits_{i=1}^{n}f_i(|x_i|)$$

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

Существует расширенный класс $X_P$, не содержащий $\{\varepsilon\}$. Так что вы можете пытаться применять $\sqcup$ к чему-то, на чем она не определена.

Если вы имели ввиду ,что не могу ,то я просто выберу расширенный класс содержащий $\{\varepsilon\}$ .

[mihaild]

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

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

А что такое "количество тактов, которые сделает машина, распознавая язык"? Я знаю только что такое время работы МТ на данном слове.

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

Если вы имели ввиду ,что не могу ,то я просто выберу расширенный класс содержащий $\{\varepsilon\}$ .

Тогда напишите правильное определение. По текущему не для всех расширенных классов существует нужная операция.
(и вообще пихать в одно множество языки и множества языков - довольно странное занятие)

У меня возникает подозрение, что вы путаете языки, слова и множества языков. Определения $P$ и $NP$ пожалуйста напомните, на всякий случай.
(понятия МТ, "время работы МТ на данном входе" и "результат работы МТ на данном входе" считаем известными, остальные нет)

[Ioda]

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

А что такое "количество тактов, которые сделает машина, распознавая язык"?

Тоже самое ,что и время работы МТ .

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

Определения $P$ и $NP$ пожалуйста напомните, на всякий случай.

Класс языков $P$ - это множество языков для ,которых существует полином $f(n)$ такой ,что время работы МТ на входе $x$ ,не превышает $f(|x|)$ .
Класс языков $NP$ - это множество языков таких ,что существуют НМТ и полином $f(n)$ ,что время работы НМТ на входе $x$ не превышает $f(|x|)$ .
,или
Класс языков $NP$ - множество языков таких ,что :

$$L\in NP \Leftrightarrow \exists M & \exists c : \forall x :(x\in L \Leftrightarrow \exists u : |u|\leqslant |x|^c \wedge M(x,u)=1)$$

Если что $\wedge$ - это логическое И

[mihaild]

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

Тоже самое ,что и время работы МТ .

Время работы МТ - это функция от слова. Причем тут язык?

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

Класс языков $P$ - это множество языков для ,которых существует полином $f(n)$ такой ,что время работы МТ на входе $x$ ,не превышает $f(|x|)$ .

Неправильно. Согласно этому определению любой язык входит в $P$.
И чисто синтаксически - в ваше определение МТ входит свободно.

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

Класс языков $NP$ - множество языков таких ,что :

$$L\in NP \Leftrightarrow \exists M & \exists c : \forall x :(x\in L \Leftrightarrow \exists u : |u|\leqslant |x|^c \wedge M(x,u)=1)$$

Неправильно. Согласно этому определению любой рекурсивный язык входит в $NP$.

[Ioda]

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

Время работы МТ - это функция от слова. Причем тут язык?

Так я и определял $T_M$ над множествами слов ,а не языков .

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

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

Это вы перешли к языкам ,а не я.

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

в ваше определение МТ входит свободно.

Если вы имеете ввиду ,что я не оговорил детерминированность ,то я не оговариваю ее ,так как подразумеваю её.

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

Неправильно. Согласно этому определению любой рекурсивный язык входит в $NP$.

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

(Оффтоп)

Так-то мое доказательство слабо опирается на свойства языков и машин , но разбор в деталях - дело благородное.

[mihaild]

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

Так я и определял $T_M$ над множествами слов ,а не языков .

Нет вы. У вас $X_P$ содержит, в том числе, мультимножества языков. И $T_M$ действует на $X_P$. Соответственно вопрос - что такое $T_M$ от мультимножества языков?

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

Если вы имеете ввиду ,что я не оговорил детерминированность ,то я не оговариваю ее ,так как подразумеваю её.

Нет, вопрос не в детерменированности. Возможно, если вы напишете нормально, с кванторами по всем переменным, то ошибка станет более очевидной.

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

и это определение вы несколько страниц назад назвали правильным

Да, я в тот момент ошибся, пардон. В честь этого подсказка: не хватает еще некоторого ограничения на $M$.

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

Так-то мое доказательство слабо опирается на свойства языков и машин

Именно поэтому оно не имеет никаких шансов быть правильным - любое правильное доказательство обязано использовать свойства, при изменении которых истинность утверждения меняется.

[Ioda]

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

Соответственно вопрос - что такое $T_M$ от мультимножества языков?

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

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

если вы напишете нормально, с кванторами по всем переменным, то ошибка станет более очевидной.

Хорошо. Думаю ,что рассматриваемая МТ $M$ должна распознавать язык $L$ ,которому принадлежит слово $x$ , то есть : $L=L(M)$

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

Именно поэтому оно не имеет никаких шансов быть правильным

Мне ,вот ,ни разу не очевидно отчего так может быть.

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

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

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

[mihaild]

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

$T_M$ от мультимножества языков ,как и от любого другого бесконечного мультимножества ,равна бесконечности

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

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

Думаю ,что рассматриваемая МТ $M$ должна распознавать язык $L$ ,которому принадлежит слово $x$ , то есть : $L=L(M)$

Да, так лучше. Хотя не стоит одной и той же буквой обозначать и функцию, и ее значение на каком-то элементе (эта вредная привычка обычно появляется в матане на первых курсах, и часто так и остается).
Более точно (обозначения: $M(x)$ - результат работы МТ $M$ на входе $x$, $t_M(x)$ - время работы МТ $M$ на входе $x$):
Пусть $L$ - язык. $L \in P$ тогда и только тогда, когда существуют МТ $M$ и полином $f$, такие что: 1) $\forall x: t_M(x) \leqslant f(|x|)$; 2) $\forall x: x \in L \leftrightarrow M(x) = 1$.

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

Мне ,вот ,ни разу не очевидно отчего так может быть.

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