NP≠P. Док-во от противного-контрпример алгоритмов из NP

[Xaositect]

Ну, это неинтересно. Я говорил именно о языке, утверждение о принадлежности которого к $\mathbf{P}$ независимо от нашей формальной системы. Насколько мне известно, конструкции такого языка никто пока не предлагал.

[dmitgu]

Xaositect в сообщении #1202722 писал(а):

Ну, это неинтересно. Я говорил именно о языке, утверждение о принадлежности которого к $\mathbf{P}$ независимо от нашей формальной системы. Насколько мне известно, конструкции такого языка никто пока не предлагал.

Не понял в каком смысле "независимо от нашей формальной системы".

Но если речь о неразрешимости вопроса о принадлежности к $P$ (отсутствие положительного теста), то это вроде легко (придумал? :)

Тоже берем проблему остановки и для каждого проверяемого "слова" кроме "обычной" проверки смотрим ещё не остановился ли некий алгоритм за число шагов, равное длине "слова". И если вдруг остановится - начинаем безобразничать! ) Тянем время экспоненциально и т.д. А поскольку проблема остановки неразрешима, то и общего способа сказать - принадлежит ли такой язык $P$ или в какой-то момент начнутся "безобразия" - невозможно.

[Xaositect]

dmitgu в сообщении #1202728 писал(а):

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

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

[dmitgu]

Xaositect в сообщении #1202734 писал(а):

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

Так это могут быть разные языки. Есть же языки не из $P$. Вот если событие остановки случилось - язык с этих размеров "слов" становится совсем другим. А способа определить - произойдёт ли такая "метаморфоза" нет - в общем случае.

[Xaositect]

А хотя да, Вы правы, вроде работает. Возьмем языки $L_1 \in \mathbf{P}$ и $L_2 \notin \mathbf{P}$ и сделаем язык $L_M$, состоящий из слов $w \in L_1$, для которых машина $M$ не останавливается за $|w|$ шагов, и слов $w \in L_2$, для которых $M$ останавливается за $|w|$ шагов. Тогда $L_M = L_1 \Leftrightarrow M \text{ не останавливается}$, и $L_M$ отличается от $L_2$ на конечном числе входов, если $M$ останавливается.
Странно, что эта конструкция нигде не упоминается.

[dmitgu]

Xaositect в сообщении #1202740 писал(а):

А хотя да, Вы правы, вроде работает. Возьмем языки $L_1 \in \mathbf{P}$ и $L_2 \notin \mathbf{P}$ и сделаем язык $L_M$, состоящий из слов $w \in L_1$, для которых машина $M$ не останавливается за $|w|$ шагов, и слов $w \in L_2$, для которых $M$ останавливается за $|w|$ шагов. Тогда $L_M = L_1 \Leftrightarrow M \text{ не останавливается}$, и $L_M$ отличается от $L_2$ на конечном числе входов, если $M$ останавливается.
Странно, что эта конструкция нигде не упоминается.

Спасибо - красиво и понятно в Вашем оформлении ) Я как начинаю в $\LaTeX$ писать - сто раз путаюсь как что обозначается ))

[mihaild]

dmitgu в сообщении #1202697 писал(а):

Не только:

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

dmitgu в сообщении #1202697 писал(а):

У нас даже способа нет отличить пустой язык от непустого

Ну да, мы в $PA$ не можем доказать, пустой этот язык или нет. Ну и что?
Если в какой-то расширенной теории можно доказать, что он пустой, то в ней же будет легко доказать, что он принадлежит $P$.
Один и тот же язык можно задавать многими разными способами, но какие способы задают один и тот же язык - зависит от модели.

Как это связано с $NP$-полнотой $3-SAT$, которая доказывается явным предъявлением сведения?

Xaositect в сообщении #1202740 писал(а):

Странно, что эта конструкция нигде не упоминается.

Может быть потому что все кому она была нужна ее придумывали по месту?
(я, прочитав ваше предложение про неразрешимость принадлежности $P$ подумал взять язык из пар $(x, y)$, таких что существует доказательство противоречивости $PA$ длины не больше $\log |x|$, а $y \in L \in EXPTIME-complete$ - это, кажется, сводится к вашему примеру если взять $M$, ищущую противоречия в $PA$)

(Оффтоп)

В списке P versus NP есть три доказательства того, что равенство $P$ и $NP$ не зависит от $PA$.

[dmitgu]

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

Ну да, мы в $PA$ не можем доказать, пустой этот язык или нет. Ну и что?

А то, что вопрос о неравенстве $NP \ne P$ - это вопрос о неразрешимости. А формализм "языка" вообще не чувствует неразрешимость. И как Вы хотите с негодным инструментом решать интересующий вопрос?

Теперь я понимаю в некоторых деталях, почему в теории алгоритмов дело зашло в тупик. И почему

Xaositect в сообщении #1202740 писал(а):

Странно, что эта конструкция нигде не упоминается.

Потому, что тогда видна неадекватность формализма языка для решения вопросов неразрешимости, а отказываться от такого упрощения очень не хочется. Но придётся

[mihaild]

dmitgu в сообщении #1202846 писал(а):

А то, что вопрос о неравенстве $NP \ne P$ - это вопрос о неразрешимости.

Что это вообще значит?
$P$ и $NP$, по определению, множества языков. Попытки ее решить в любом "другом формализме" (что такое "формализм языка"?) должны содержать (и желательно начинаться с) связь со стандартными определениями.

[dmitgu]

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

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

Интересно узнать:
1. Если для бесконечного количества некоторых слов $(S, s)$ время поиска $p_M(|S|, |s|)$ сертификатов алгоритмом $M(S, s)$ неполиномиально дольше времени $p_{\exists}(|S|)$ проверки $R(S, s, y)$ тех же некоторых слов $(S, s)$, то $M(S, s)$ это - решение?

2. А если в целом у $R(S, s, y)$ время работы ограничено $p_{\forall}(|S|, |s|)$ ?

И как в терминах "языка" Вы выразите, что случай 1 тоже - не решение, даже если имеет место случай 2?

[mihaild]

dmitgu в сообщении #1202883 писал(а):

это - решение?

Решение чего?
Проблемы $P$ vs $NP$? Нет конечно. То, что существует медленный алгоритм поиска сертификатов - неинтересно. Интересно, существует ли быстрый.

Но вообще фраза "алгоритм $M$ - решение $P$ vs $NP$" мне кажется настолько странной, что я скорее всего не понял ваш вопрос. Можете написать подробнее?

[dmitgu]

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

Проблемы $P$ vs $NP$? Нет конечно.

А почему "нет"? Алгоритм $M(S, s)$ вполне себе полиномиален для общего $p_{\forall}(|S|, |s|)$. Где в Ваших терминах есть место для $p_{\exists}(|S|)$ ? На что Вы опираетесь в своём "нет"? На то, чего нет в терминах Вашего формализма?

[mihaild]

dmitgu, давайте уточним. У вас есть алгоритм проверки $R$, время работы которого ограничено полиномом $p_\forall$, время работы его на каком-то подмножестве $\mathbb{S}$ ограничено полиномом $p_\exists$. У вас есть алгоритм генерации сертификатов $M$, который на $\mathbb{S}$ работает сверхполиномиально по сравнению с $p_\exists$ (что эквивалентно просто "сверхполиномиально от длины входа"). Так?

(Оффтоп)

Только мне очень режет глаз использование кванторов в индексах?

[dmitgu]

Нет. Неполиномиально быстро от длины входа работает алгоритм проверки для некоторых $S$ Игнорирует $y$ (это вообще типично для всех алгоритмов проверки и больших сертификатов) и $s$.

[Xaositect]

dmitgu в сообщении #1202846 писал(а):

А то, что вопрос о неравенстве $NP \ne P$ - это вопрос о неразрешимости. А формализм "языка" вообще не чувствует неразрешимость. И как Вы хотите с негодным инструментом решать интересующий вопрос?

Никакой это не вопрос о неразрешимости. Если зрить в корень, это вопрос о существовании для некоторой вполне конкретной задачи (распознавание языка $\mathrm{SAT}$) алгоритма решения, который обладает хорошим свойством, а именно всегда завершается за время $n^k$, где $n$ - длина входа.
Вот если для какого-то $k$ такой алгоритм существует - то $\mathbf{P} = \mathbf{NP}$. А если нет таких алгоритмов ни для какого $k$ - то не равно.
И вот это несуществование и хочется доказать. И для такого доказательства надо как-то рассматривать все алгоритмы решения одной задачи и для всех них доказать, что они плохие. И как это сделать - никто не знает, это основная проблема теории сложности.