P vs NP .

[Ioda]

Можно попробовать перестроить $M$ . Пусть она работает следующим образом : сначала проходит все точки шара радиуса 1 ,попутно проверяя не являются ли они подсказкой , если среди них нет искомого ,переходит к точкам шара радиуса 2 также подставляя значения ,и так далее ,пока полученное значение не окажется подсказкой. Данная машина должна работать лишь полиномиальное время. Также она лишена недостатка приведенного вами.

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

шара фиксированного (не зависящего от входа) радиуса

[mihaild]

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

Данная машина должна работать лишь полиномиальное время

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

[Ioda]

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

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

Но дойдет на каком-то шаге ,ведь длина слова ограниченна какой-то константой.

[mihaild]

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

[Ioda]

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

Дойдет на каком-то, но время работы этого поиска уже не будет ограничено полиномом от длины входа

Разве лемма 1 не про обратное? Или она неверна?

[mihaild]

Верна (вроде), но из нее нужного утверждения не следует. Следовало бы, если бы радиус шара не зависл от входа, но он зависит.
У нас есть язык $L$ из $NP$ и число $m$, такие что подсказки для слова длины $n$ имеют длину не больше чем $m \cdot n^m$. Попробуйте явно выписать, среди каких слов вы собираетесь искать подсказку.

[Ioda]

Среди слов множества - шара $B_m(x)$ . Далее в теореме 1 ,я пытаюсь доказать, что мощность $B_m(x)$ возрастает быстрее ,чем длина подсказки . Теорема 1 ,вроде ,про утверждаемое.

[mihaild]

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

Среди слов множества - шара $B_m(x)$

Для какого $m$?
Если $m < |x|$, то подсказка может существовать, но лежать вне этого шара. Иначе число элементов шара получается не ограниченным никаким полиномом от $|x|$.

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

Теорема 1 ,вроде ,про утверждаемое

Теорема 1 про что-то невнятное. Если она вам нужна - сформулируйте, явно указав кванторы по всем используемым переменным.
(доказательство ее, кстати, еще более невнятное - например

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

$$O(n^m)=O(\left\lvert u(x) \right\rvert)$$

не является обратным к

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

$$O(n^m)=O(\left\lvert u(x) \right\rvert)$$

).

[Ioda]

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

Теорема 1.

$$O(\left\lvert u(x) \right\rvert)=O(n^m)$$

Того что вы утверждаете не обнаружено. К тому же я повторил формулировку.

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

Теорема 1.
mihaild в сообщении #1367982

писал(а):
Пусть $L$ - язык из $NP$, $M$ - распознающая его МТ. Определим функцию $u(n)$, ограниченную полиномом, такую что для любого слова $x$ оно принадлежит языку тогда и только тогда, когда существует подсказка длины не больше чем $u(|x|)$
... . Тогда длина данной подсказки возрастает не более ,чем полином $n^m$ ,где $m$ - параметр ,который равен радиусу шара с центром в $x$ . То есть :

$$O(u(|x|))=O(n^m)$$

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

Для какого $m$?

Для которого условие .

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

Пусть она работает следующим образом : сначала проходит все точки шара радиуса 1 ,попутно проверяя не являются ли они подсказкой , если среди них нет искомого ,переходит к точкам шара радиуса 2 также подставляя значения ,и так далее ,пока полученное значение не окажется подсказкой.

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

Теорема 1 про что-то невнятное.

Чуть выше требуемая формулировка.

[mihaild]

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

где $m$ - параметр ,который равен радиусу шара с центром в $x$

Есть много шаров с центром в $x$. Про какой из них речь?
Ну и ладно, длина подсказки действительно ограничена полиномом от длины входа, чисто из определения $NP$. Дальше что? У вас оказывается, что подсказка лежит в шаре полиномиального от длины входа радиуса. Это конечно правда, но число элементов в этом шаре не полиномиально от размера входа.

[Ioda]

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

Это конечно правда, но число элементов в этом шаре не полиномиально от размера входа.

Я в этом не уверен. Например ,можно показать ,что количество точек шара полиномиально зависит от размера входа (лемма 2 об этом). Либо я вас не так понял.

[mihaild]

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

количество точек шара полиномиально зависит от размера входа (лемма 2 об этом).

Это было бы если бы радиус шара был фиксирован.
А тут у вас длина входа $n$, радиус шара $p(n)$, и соответственно по вашей лемме получается оценка $O(n^{p(n)})$ на число элементов.

[Ioda]

Хорошо . Посмотрим ,как работает новая версия $M$ (отсюда http://dxdy.ru/post1368024.html#p1368024). На первом шаге предстоит пройти $n+3$ точек ,на втором ,если он будет, порядка $O(n^2)$ точек , и ,я полагаю вы согласитесь с тем ,что ,далее ,на $m$-ом шаге, количество точек будет порядка $O(n^m)$ . Если нет ,то мне следует это доказать?

[mihaild]

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

далее количество точек будет порядка $n^m$

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

А то пока что у вас получается, что любая функция ограничена полиномом. Возьмем функцию $f(n)$, напишем $f(n) = n^{\log_n f(n)}$, обозначим $m = \log_n f(n)$, получим $f(n) = n^m$.

[Ioda]

Параметр $m$ независим ,и его можно узнать ,только найдя подсказку. На каком $m$ найдем подсказку ,таким $m$ и ограничивается время работы $M$ (в смысле $T_M(x)=O(n^m)$) .