P vs NP .

[mihaild]

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

то выберу это

Это - это какое?

Я правильно понимаю, что вы хотите ввести функцию $f(x)$, равную минимуму $t(M, x)$ по всем МТ $M$, работающим полиномиальное время и распознающих некоторый язык (автоматически из $P$), содержащий $x$?
Тогда $f(x) = 1$, т.к. есть язык $L$, состоящий из всех слов, и МТ $M$, распознающая его за один такт.

[Ioda]

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

Я правильно понимаю, что вы хотите ввести функцию $f(x)$, равную минимуму $t(M, x)$ по всем МТ $M$, работающим полиномиальное время и распознающих некоторый язык (автоматически из $P$), содержащий $x$?

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

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

Это - это какое?

Это ,то которое про биекцию между $X$ и $P$ в виде $\operatorname{pr_1}$ .

[mihaild]

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

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

Расшифруйте. Пока что я понял, что вы для каждого языка $L$ из $P$ выбрали МТ $M(L)$, распознающую этот язык за полиномиальное время. Так?
Дальше вы вроде бы хотите для каждого слова взять какое-то время. Какое?

[Ioda]

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

Расшифруйте.

Вот :

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

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

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

Дальше вы вроде бы хотите для каждого слова взять какое-то время. Какое?

Да. Я могу потребовать непересечение языков?
Если нет ,то если слово $x$ принадлежит лишь одному языку $L$ ,то время распознавания для данного слова есть $t(M(L),x)$ . Если слово $x$ принадлежит пересечению некоторого множества языков $\{L_1,\dots ,L_n\}$ ,то время его распознавания определим ,как $\min\limits_{}(t(M_1(L_1),x),\dots ,t(M_n(L_n),x))$ .

[Sender]

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

время его распознавания определим ,как $\min\limits_{}(t(M_1(L_1),x),\dots ,t(M_n(L_n),x))$ .

И как вы собираетесь добиться такого времени? Может, для $n$-ленточной МТ это и было бы справедливо, но ведь эмуляция многоленточной МТ посредством одноленточной, очевидно, несёт определённые издержки.

[mihaild]

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

Я могу потребовать непересечение языков?

Вы можете потребовать что угодно, но нужно явно выписать список требований. И потом показать, что объект, удовлетворяющий требованиям, существует.
Например так: нам нужно множество пар вида (что-то, язык из $P$), такое что:
1. Любой язык из $P$ является вторым элементом ровно одной пары.
2. Никакие два вторых элемента разных пар не пересекаются.
Очевидно, что множества, удовлетворяющего обоим этим свойствам, не существует.

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

,то время его распознавания определим ,как $\min\limits_{}(t(M_1(L_1),x),\dots ,t(M_n(L_n),x))$

Только давайте эту функцию назовем как-то иначе - уже есть функция $t(M, x)$, так называющася.
Хорошо, сойдет (только ваша запись подразумевает что множество языков, которым принадлежит $x$, конечно, что не так).
Итого формально мы по функции $M$ построили функцию на словах: $f(x) = \min\limits_{L \in P: x \in L} t(M(L), x)$. Так?
Давайте опять для простоты возьмем какую-нибудь более конкретную функцию $M$. Например возьмем язык $U$, состоящий из вообще всех слов, и скажем что $M(U)$ - МТ, которая просто останавливается за 1 такт с ответом "да". Тогда $f(x) \equiv 1$. Что дальше?

(Оффтоп)

Sender в сообщении #1386324 писал(а):

И как вы собираетесь добиться такого времени?

Да там просто какая-то функция, никакого отношения к $P$ не имеющая. Тут товарищ пытается найти какие-то закономерности в словах, принадлежащих языкам из $P$.

[Ioda]

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

Итого формально мы по функции $M$ построили функцию на словах: $f(x) = \min\limits_{L \in P: x \in L} t(M(L), x)$. Так?

Да. Хотя ,кажется я понял к чему вы клоните ,поэтому давайте не так определим . Давайте так :

$$f(x)=\lim\limits_{n\to\infty}^{}\sum\limits_{x\in \bigcap\limits_{i=1}^{n}L_i ,L_i\in P}^{}\frac{t(M_i(L_i),x)}{n}$$

Согласны ?

(Оффтоп)

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

Тут товарищ занимается совершенно безнадежным делом

Ну почему ? Отыщем ошибку ,хотя бы одному из нас точно станет легче.

[mihaild]

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

Давайте так :

$$f(x)=\lim\limits_{n\to\infty}^{}\sum\limits_{x\in \bigcap\limits_{i=1}^{n}L_i ,L_i\in P}^{}\frac{t(M_i(L_i),x)}{n}$$

Согласны ?

Да вы можете заводить любую функцию какую хотите. Правда в этом случае вам нужно показать существование предела. И как минимум для некоторых упорядочений $P$ и функций $M$ этот предел не существует, а для некоторых равен $\infty$. И вроде бы таким способом можно получить вообще любую функцию $\{0, 1\}^* \to [1; \infty)$.

UPD: почитал внимательнее, всё-таки там невнятная сумма какая-то. Видимо под пределом должно быть $\frac{\sum_{L_i: i \leqslant n, x \in L_i} t(M(L_i), x)}{\left|\{L_i: i \leqslant n, x \in L_i\}\right|}$. И если вы под $M_i(L_i)$ имели в виду $M(L_i)$, то внешний индекс не нужен, а если вы теперь вводите несколько функций от языков - то напишите, какие.