P vs NP .

[mihaild]

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

И решать $P =? NP$ я тоже не умею. Но сильно подозреваю, что решение должно очень существенно использовать их определения, а не сводиться к простым утверждениям, применмым почти к любым множествам языков.

(Оффтоп)

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

[Ioda]

(Оффтоп)

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

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

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

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

Но то что вы не можете это сформулировать

Я попытаюсь сформулировать внятно : перенумеруем $P$ (беря пары МТ и язык) и потребуем от всех языков ,которые возьмём в наше множество ,непустоты и пустого пересечения со всеми остальными языками рассматриваемого множества ,и именно с этим множеством (мною построенным) будем работать. Думаю , сейчас имеет место разговор о времени работы ,так как теперь каждое слово принадлежит лишь одному языку множества и распознает его только одна из рассматриваемых машин.

[mihaild]

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

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

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

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

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

всего ,что написано там мало

Смотря для чего. Естественно человечество знает про сложность вычислений гораздо больше, чем написано в любой одной книге. Только за сегодня на архиве 6 новых статей по этой теме.

[Ioda]

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

Сойдет?

Думаю ,да. Но с $NP$ мы не сможем так выбирать МТ для языка ,чтобы время распознавания обязано было быть полиномиальным ,в предположении неравенства данных классов сложности.

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

Вы кажется хотите получить какую-то функцию на словах.

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

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

можно получить абсолютно любую функцию, растущую не медленнее чем линейно от длины слова.

Так подходят и экспоненциально растущие функции ,поэтому не совсем ясно ,что вы имели ввиду ,или я вас не так понял.

[mihaild]

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

Но с $NP$ мы не сможем так выбирать МТ для языка ,чтобы время распознавания обязано было быть полиномиальным

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

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

Так подходят и экспоненциально растущие функции ,поэтому не совсем ясно ,что вы имели ввиду ,или я вас не так понял.

Я имел в виду именно это.
Возьмем произвольную функцию $f(x)$ такую что $f(x) > |x|$. Для каждого слова $x$ зададим язык $L(x) = \{x\}$ и распознающую его МТ $M(x)$, работающую так: она сначала за $|x|$ операций проверяет, передали ей на вход $x$ или нет. Если нет - то тут же возвращает $0$. Если да - то спит $f(x) - |x|$ раундов, и потом возвращает $1$. Легко проверяется что $T(M, x) = O(|x|)$.
В итоге ваша функция $T(x)$ будет равна $f(x)$.

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

[Ioda]

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

Если да - то спит $f(x) - |x|$ раундов, и потом возвращает $1$.

Так ,слово $x$ мы взяли в наше множество ,значит оно принадлежит языку ,принадлежащему классу $P$ . Примем ,что $f(x)=2^{|x|}$ (из того ,что вы утверждали произвольность функции),тогда слово $x$ явно не принадлежит $P$ ,так как ,по вашему построению , время распознавания данного слова равно $2^{|x|}-|x|$ ,что явно растет быстрее полинома ,то есть слово $x$ не принадлежит $P$ . Противоречие. Или я не так вас понял.

[mihaild]

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

значит оно принадлежит языку ,принадлежащему классу $P$

Ну да. Любое слово принадлежит какому-то языку, принадлежащему $P$.

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

тогда слово $x$ явно не принадлежит $P$

Ну да, слово $x$ естественно не принадлежит $P$. Отдельные слова вообще не принадлежат $P$, это множество языков. А вот язык $\{x\}$ принадлежит $P$.

[Ioda]

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

Любое слово принадлежит какому-то языку, принадлежащему $P$.

Нет . Как пример ,слова языков класса $EXPTIME$ .

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

Ioda в сообщении #1385812

писал(а):
тогда слово $x$ явно не принадлежит $P$ Ну да, слово $x$ естественно не принадлежит $P$. Отдельные слова вообще не принадлежат $P$, это множество языков. А вот язык $\{x\}$ принадлежит $P$.

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

[mihaild]

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

Нет . Как пример ,слова языков класса $EXPTIME$ .

Да. Как пример - язык "все слова" принадлежит $P$. А еще любой конечный язык принадлежит $P$.

[Ioda]

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

Да. Как пример - язык "все слова" принадлежит $P$. А еще любой конечный язык принадлежит $P$.

Хорошо ,но почему? Раз для какого-то подмножества языка "все слова" мы точно знаем ,что время распознавания экспоненциально, то каким образом , данное подмножество ,по сути тоже язык , является подмножеством $P$ ?

[mihaild]

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

Хорошо ,но почему?

По определению. Для этих языков существуют распознающая их МТ, работающая за полином.

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

Раз для какого-то подмножества языка "все слова" мы точно знаем ,что время распознавания экспоненциально

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

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

данное подмножество ,по сути тоже язык , является подмножеством $P$

Язык не является подмножеством $P$. Серьезно, сколько можно путать слова, языки и классы языков?

[Ioda]

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

Язык не является подмножеством $P$. Серьезно, сколько можно путать слова, языки и классы языков?

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

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

Вы так говорите "время распознавания", как будто это характеристика слова. Это характеристика пары (машина Тьюринга, слово).

Это то понятно , но мы же рассматриваем только ДМТ ,а для них есть классы языков ,которые суть подмножества языка "все слова", для которых ДМТ работает "слишком долго".

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

Кроме того, вы говорите "время экспоненциально" как будто это характеристика одного числа. Нет, это характеристика множества чисел.

Это тоже понятно , но надо же уточнить с какой зависимостью имеем дело.

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

В частности, если у нас есть МТ, работающая полиномиальное от длины входа время, и мы поменяем время ее работы на любом конкретном слове

Возможно не понял смысла изменения. Это выглядит так:
$t(M_1,|x_0|)=p_1(|x_0|)=t_1$ и мы меняем $t_1$ на некоторое конечное $t_2$ ,тогда $t_2=p_2(|x_0|)=t(M_2,|x_0|)$ ,так? $p_1(n) ,p_2(n)$ - полиномы .

[mihaild]

Из последнего сообщения нельзя понять вообще почти ничего.
Давайте вернемся на шаг назад. Два утверждения:
1. Язык, состоящий из всех возможных слов (часто обозначается как $\{0, 1\}^*$), принадлежит $P$.
2. Для любого слова $x$ существует язык $L \in P$, такой что $x \in L$.
Понимаете ли вы, почему верно первое утверждение? А второе?
(считаем, что работаем в алфавите $\{0, 1\}$)

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

$t(M_1,|x_0|)=p_1(|x_0|)=t_1$ и мы меняем $t_1$ на некоторое конечное $t_2$ ,тогда $t_2=p_2(|x_0|)=t(M_2,|x_0|)$ ,так? $p_1(n) ,p_2(n)$ - полиномы .

Примерно. Более точно так: если $f(x) \leqslant p_1(|x|)$, где $p_1$ - полином, и $g(x) = f(x)$ при $x \neq x_0$, то существует такой полином $p_2$, что $g(x) \leqslant p_2(|x|)$.

[Ioda]

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

Язык, состоящий из всех возможных слов (часто обозначается как $\{0, 1\}^*$), принадлежит $P$.

Это следует из этого :

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

если $f(x) \leqslant p_1(|x|)$, где $p_1$ - полином, и $g(x) = f(x)$ при $x \neq x_0$, то существует такой полином $p_2$, что $g(x) \leqslant p_2(|x|)$.

?

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

Для любого слова $x$ существует язык $L \in P$, такой что $x \in L$.

Думаю ,это следует из первого.

[mihaild]

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

Это следует из этого :

Нет, это следует из того, что можно явно предъявить МТ, распознающую этот язык за полиномиальное время.

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

Думаю ,это следует из первого.

Правильно.