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

[Xaositect]

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

Да, но определить, что слово не принадлежит языку можно гораздо быстрее. Если языку не принадлежат никакие слова, начинающиеся с "1111", то смотреть слово целиком - нет никакой необходимости. А оно может быть сколь угодно огромным. И "соглашение о кодировании ленты после остановки", включающее в себя "очистку" этой бездны - неприемлемо с точки зрения соответствия полиномиальности времени работы на проверку. К собственно проверке эта "очиска" не относится никак. Что тут не понятного?

А что тут не так? Без стирания получается время работы $p(n) = 4$, полиномиальное от длины входа. Со стиранием получится $q(n) = n$, тоже полиномиальное от длины входа.

-- Пт окт 06, 2017 13:46:15 --

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

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

(где $\overline{x,y}$ обозначает какой-нибудь разумный способ кодирования пар).

В нашем случае "разумный способ" - это когда за полиномиальное время можно сформировать пару, а также взять из нее первый или второй элемент. Но раз мы не хотим заморачиваться с определениями вычислимых за полиномиальное время функций и композициями, то давайте просто фиксируем кодировку пары. Например, если $x = x_1x_2\dots x_n, y = y_1y_2\dots y_m \in \{0, 1\}^*$, то пара кодируется как $\overline{\left< x, y \right>} = x_1x_1x_2x_2\dots x_n x_n 01 y_1y_1y_2y_2\dots y_m y_m$.

[dmitgu]

Someone в сообщении #1253718 писал(а):

Время очистки в вашем примере, очевидно, полиномиальное (даже пропорционально первой степени длины входа).

Это не я говорю о времени очистики )))) Эта очистка никому не нужна. Я говорю о времени работы алгоритма проверки. И это время может быть неполиномиально (да сколь угодно!) меньше, чем время очистки. С чего тогда эту очистку навязывают - понять не могу ))))

[mihaild]

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

С чего тогда эту очистку навязывают - понять не могу

С того, что язык "распознается с очисткой" за полиномиальное время тогда и только тогда, когда он за полиномиальное время "распознается без очистки".
Но никто не навязывает. Если вас устраивает мое определение (с поправкой Xaositect) - давайте возьмем его. Если не устраивает - предложите свое.

[dmitgu]

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

А что тут не так? Без стирания получается время работы p(n) = 4, полиномиальное от длины входа. Со стиранием получится $q(n) = n$, тоже полиномиальное от длины входа.

Проблема в том, что "длина входа" вообще-то включает в себя и сертификат. И полиномиальность от длины сертификата - это отсутствие ограничений относительно размера слова. Да, про сертификат $y$ пишут типа $|y| < p(|w|)$, что не отменяет того факта, что его надо как-то отвергнуть при чрезмерном размере. И что затем - чистить? Ведь никто вообще не рассматривает то, что за пределами предельной длины, тем более с "ластиком" )

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

Впрочем, это неважно, мы уже договорились, что стирать ничего не будем

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

[mihaild]

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

Проблема в том, что "длина входа" вообще-то включает в себя и сертификат.

Сертификат - это уже "более высокоуровневое" понятие по сравнению со временем работы и длиной входа. Когда мы определяем класс $P$, мы никакой структуры на входе не задаем.

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

Да, про сертификат $y$ пишут типа $|y| < p(|w|)$, что не отменяет того факта, что его надо как-то отвергнуть при чрезмерном размере.

Не обязательно. Если вы посмотрите на определение $NP$, то увидите, что происходящее на слишком длинных сертификатах на определяемый язык никак не влияет (важно лишь чтобы слишком длинные сертификаты всё еще обрабатывались за полиномиальное от общей длины входа (включая сертификат) время).

[dmitgu]

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

Сертификат - это уже "более высокоуровневое" понятие по сравнению со временем работы и длиной входа. Когда мы определяем класс $P$, мы никакой структуры на входе не задаем.

Когда мы определяем язык, мы вообще никаких классов, никакого времени работы и никаких сертификатов не задаём. Это просто "строчки" - множество каких-то слов. А вот класс - это именно алгоритм, обладающий соответствующими свойствами и который "существует" для данного языка и при этом взаимно-однозначно сопоставлен с данным языком своим принимаю/не принимаю.

Я называю подобные алгоритмы "прикладные роли языка" - за неимением какого-то общепринятого термина - хотя он нужен. И у языка может быть полно таких "прикладных ролей" - и для класса $P$, и для класса $NP$, и для сопоставления соответствия языка некому алгоритму (когда мы проверяем, соответствует данный алгоритм данному языку и свойствам класса $P$. например) и ещё полно всяких.

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

И одно из обязательных свойств этого алгоритма - полиномиальность времени работы относительно размера слова. При том, что на входе у него - еще и сертификат. Поэтому отказ от определений в духе Вашего - с "очисткой" - носит обязательный, а не условный (необходимость, а не договорённость) характер для решения вопросов теории алгоритмов.

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

-- 07.10.2017, 09:42 --

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

(важно лишь чтобы слишком длинные сертификаты всё еще обрабатывались за полиномиальное от общей длины входа (включая сертификат) время).

Откуда такая идея? Что это "важно" )))) Важно, чтобы за полиномиальное от размера слова время всё заканчивалось. Так в жизни и так у Оккама ) Ради своеего определения Вы готовы явно отказаться от полиномиальности относительно слова и для Вас это так "важно" - что Вы придумываете какие-то дополнительные "миры" где происходит обработка ненужных "хвостов" от сертификатов. Важно прямо противоположное )))

[пианист]

Можно вопрос, здесь обсуждается классическая задача $(NP \stackrel{?}{=} P)$, или какая-то оригинальная авторская постановка?
А то я запутался ;(

[mihaild]

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

А вот класс - это именно алгоритм, обладающий соответствующими свойствами и который "существует" для данного языка и при этом взаимно-однозначно сопоставлен с данным языком своим принимаю/не принимаю

Нет, и подозреваю, что вы тут не понимаете очень существенный момент.
$P$ - это именно класс языков. Для одного и того же языка может существовать счетное множество алгоритмов, его распознающих [причем если существует хотя бы один, то существует целое бесконечное неразрешимое множество]. И они могут работать разное время - какой-то линейно, какой-то за двойную экспоненту. И язык принадлежит $P$ если существует хотя бы один алгоритм, его распознающий. То, что для языка существуют распознающие его сверхполиномиальные алгоритмы, не может помешать ему принадлежать $P$ (более того, если язык принадлежит $P$, то существует и сверхполиномиальный алгоритм, его распознающий).

Вопрос $P\stackrel{?}=NP$ - это именно вопрос "верно ли, что если для языка существует алгоритм с сертификатом, то существует алгоритм и без сертификата".

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

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

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

Ну это не соответствует классическому определению $NP$ (хотя если мы определяем результат по состоянию, оставляя мусор - и эквивалентно ему - в том смысле, что задает тот же класс языков).

С моими определениями 0-4 вы согласны?
Если да, то можно взять
5'. Язык $L$ принадлежит $NP$ в том и только в том случае, если существуют языки $L^\prime$, полином $q(n)$ и МТ $A$, распознающая $L$ такие что $x \in L \leftrightarrow \exists y: \overline{x, y} \in L^\prime$, время работы $A$ полиномиально от длины входа, а на словах вида $\overline{x, y}$ еще и не превосходит $q(|x|)$.
Это определение эквивалентно предыдущему: мы можем, взяв МТ, работающую полиномиально от длины слова + длины сертификата, переделать ее так, чтобы она отвергала слишком длинные сертификаты, прочитав только их кусок, достаточный чтобы понять, что сертификат слишком длинный.

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

Откуда такая идея?

Из работы Кука, скорее всего.

[dmitgu]

пианист в сообщении #1253873 писал(а):

Можно вопрос, здесь обсуждается классическая задача $(NP \stackrel{?}{=} P)$, или какая-то оригинальная авторская постановка?
А то я запутался ;(

Вопрос не в $NP \ne P$, а в его «первопричине». Подробно отвечал тут, какой мой был практический интерес и к чему (начиная с ответа на 3 цитату):

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

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

-- 07.10.2017, 18:12 --

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

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

Вы объясняете мне то, что я объяснял Вам. Тут у нас согласие, похоже )

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

5'. Язык $L$ принадлежит $NP$ в том и только в том случае, если существуют языки $L^\prime$, полином $q(n)$ и МТ $A$, распознающая $L$ такие что $x \in L \leftrightarrow \exists y: \overline{x, y} \in L^\prime$, время работы $A$ полиномиально от длины входа, а на словах вида $\overline{x, y}$ еще и не превосходит $q(|x|)$.
Это определение эквивалентно предыдущему: мы можем, взяв МТ, работающую полиномиально от длины слова + длины сертификата, переделать ее так, чтобы она отвергала слишком длинные сертификаты, прочитав только их кусок, достаточный чтобы понять, что сертификат слишком длинный.

Вроде бы клёво, мне нравится про "кусок", характеристический алгоритм для неравенства, ограничивающего сертификат спрятан внутрь алгоритма проверки.

Это очень правильно с точки зрения того, что у нас будут слова (как раз из пункта 6.1), которые будут отвергаться и насчёт размера слов, "которых нет" в языке $LS$ иначе опять было бы долгое обсуждение. По ходу разберемся, впрочем, надеюсь.

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

И задача тысячелетия - она именно про классы языков

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

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

Из работы Кука, скорее всего.

Да и Бог с ним ) Мы и сами могём

-- 07.10.2017, 18:24 --

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

В нашем случае "разумный способ" - это когда за полиномиальное время можно сформировать пару, а также взять из нее первый или второй элемент. Но раз мы не хотим заморачиваться с определениями вычислимых за полиномиальное время функций и композициями, то давайте просто фиксируем кодировку пары. Например, если $x = x_1x_2\dots x_n, y = y_1y_2\dots y_m \in \{0, 1\}^*$, то пара кодируется как $\overline{\left< x, y \right>} = x_1x_1x_2x_2\dots x_n x_n 01 y_1y_1y_2y_2\dots y_m y_m$.

Хм... По-моему проще (для рассуждений) считать, что каждый аргумент занимает свою половинную ленту с её начала. Тогда можно не читать другие аргументы, чтобы добраться до нужного. В принципе, можно такую "параллельность" организовать и на одной ленте: сначала 1-е 100 байтов 1-го аргумента, затем 100 байтов 2-го .... затем 2-е 100 байт первого и т.д. Тогда нам никогда не придётся "ездить в тележке" по слишком длинным аргументам целиком, когда они уже не нужны. Но фиксированное количество полулент в этом отношении проще.

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

[mihaild]

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

Вопрос не в $NP \ne P$, а в его «первопричине». Подробно отвечал тут, какой мой был практический интерес и к чему (начиная с ответа на 3 цитату):

Обсуждать "первопричину" и мотивировку - занятие неблагодарное. Просто $NP$ - это некоторое конкретное множество, и во избежание путаницы лучше другие множества обознчать как-то иначе:)

Ладно, давайте считать, что определения $P$ и $NP$ зафиксировали? (хотя непонятно зачем, если вы что-то доказываете не про $NP$, а про что-то еще)

Можете попробовать сформулировать утверждение, которое хотите доказать? С явным предварительным введением всех нужных определений (если их много - то давайте для начала первые несколько штук). Только без опоры на еще не введенные понятия, и без выражений типа "алгоритм, относящий язык куда-то туда".
Пока что мы определили, что значит "алгоритм распознает язык $L$", "алгоритм работает время $t$ на входе $x$", "алгоритм работает за время $f(n)$ от длины входа".

Слова "сертификат", "подсказка" и подобные предлагаю временно запретить к использованию - вместо них явно писать, как устроен вход и о каких словах идет речь. [предполагаю, что иначе будет много путаницы]

[dmitgu]

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

Можете попробовать сформулировать утверждение, которое хотите доказать?

Да, подумаю. Просто я предполагал, что будем сначала формулировать язык класса $NP$ - что в пункте 6, но "причесать" и начинать с языка, а не с алгоритма. Но могу перестроится, только надо время, тут некоторые выходные дела запланированы )

[dmitgu]

Я устал, я не ухожу (с) почти Ельцин

Пардон, что долго молчал, но сейчас отчётный период и нет возможности сосредоточиться на математике кроме некоторых выходных. Да и трудно даётся решение вопросов не о смысле, а о форме его подачи (формализация), но это необходимо, конечно. Поэтому, чтобы не тянуть – изложу сейчас то, что готово.

Формулирую, что такое $\mathbb{NP} \ne \mathbb{P}$ – в деталях:

$\forall \operatorname{Sol}(...) \forall p_+ (...) \exists AntiSol:$

$(\forall y: L(\overline{AntiSol}, y) = 0 \& N_L \le p(|\overline{AntiSol}|) \& (\operatorname{Sol}(\overline{AntiSol}) \ne 0 \vee N_{Sol} > p_+(|\overline{AntiSol}|) ) )$

$\vee ( \exists y: L(\overline{AntiSol}, y) = 1 \& N_L \le p(|\overline{AntiSol}|) \& (\operatorname{Sol}(\overline{AntiSol}) \ne 1 \vee N_{Sol} > p_+ (|\overline{AntiSol}|) ) )$

Тут

$\operatorname{Sol}(...)$ – это алгоритм-решение, который должен был бы представлять данный язык в классе $\mathbb{P}$. $L(...,...)$ – это алгоритм проверки, который представляет данный язык в классе $\mathbb{NP}$. $N_L$ и $N_{Sol}$ – время работы соответствующих алгоритмов.

При этом:

$\forall \operatorname{Sol}(...) ... \operatorname{Sol}(a) = ...$ - это я не «доигрался» до логики 2-го порядка, а это условное сокращение для записи вида

$\forall x = \overline{\operatorname{Sol}(...)}... \operatorname{Run}(x, a) = ...$

где алгоритм $\operatorname{Run}(x, a)$ – это «универсальный алгоритм», который исполняет программный код из первого аргумента, передавая ему в качестве аргументов всё, начиная со 2-го аргумента в $\operatorname{Run}(...)$.

впрочем и последняя формула – тоже сокращение для:

$\forall x ( \operatorname{IsAlg}(x) \& ... \operatorname{Run}(x, a) = ... )$.

Где $\operatorname{IsAlg}(x)$ – это «условная компиляция», которая проверяет, действительно ли в $x$ программный код в нужном формате или нечто ошибочное.

Как побочный эффект моего исследования вопроса – был найден способ свести вопрос о $\mathbb{NP} \ne \mathbb{P}$ к второй части детального представления этого $\mathbb{NP} \ne \mathbb{P}$. А именно – Если будет доказана вторая часть $\mathbb{NP} \ne \mathbb{P}$:

$\forall \operatorname{Sol}(...) \forall p_+ (...) \exists AntiSol:$

$( \exists y: L(\overline{AntiSol}, y) = 1 \& N_L \le p(|\overline{AntiSol}|) \& (\operatorname{Sol}(\overline{AntiSol}) = 0 \vee N_{Sol} > p_+ (|\overline{AntiSol}|) ) )$

то будет доказано и $\mathbb{NP} \ne \mathbb{P}$. А $AntiSol$ построены так, что заведомо известно, что для корректного $Sol(\overline{AntiSol})$ верно:
$Sol(\overline{AntiSol}) = 0$

Последнее позволяет не рассматривать 1-ю часть детального представления для $\mathbb{NP} \ne \mathbb{P}$. При этом эти $AntiSol$ вовсе не какие-то заведомо недоказуемые утверждения, а как раз заведомо доказуемые при результате алгоритма-проверки $Sol(\overline{AntiSol}) = 0$, и вопрос только в размере доказательства.

Точнее: верно $Sol(\overline{AntiSol}) = 0$, а иначе будет выполнена 1-я часть детального представления (так построено утверждение $AntiSol$):

$(\forall y: L(\overline{AntiSol}, y) = 0 \& N_L \le p(|\overline{AntiSol}|) \& (\operatorname{Sol}(\overline{AntiSol}) \ne 0 \vee N_{Sol} > p_+(|\overline{AntiSol}|) ) )$

Вернемся теперь от побочной линии к основной.

Перепишем детальное представление для $\mathbb{NP} \ne \mathbb{P}$ в новом виде:

$\forall \operatorname{Sol}(..., ...) \forall p_+(..., ...) \exists s \exists t \exists a = \overline{\operatorname{Sol}(..., ...)}:$

$(\forall y: L(t, a, s, y) = 0 \& N_L \le p(|t|, |s|) \& (\operatorname{Sol}(t, s) \ne 0 \vee N_{Sol} > p_+(|t|, |s|) ) )$

$\vee ( \exists y: L(t, a, s, y) = 1 \& N_L \le p(|t|, |s|) \& (\operatorname{Sol}(|t|, |s|) \ne 1 \vee N_{Sol} > p_+(|t|, |s|) ) )$.

Мы добавили к слову часть $s$ – это ничего не меняет в принципе (просто разбили слово на 2 части, где новая часть ничего не несет, кроме возможности увеличить размер допустимых для рассмотрения сертификатов). Ещё мы обозначили здесь переменной $t$ «опровергающее утверждение» вместо обозначения $AntiSol$ – так как это обозначение потребуется нам в дальнейшем для специального случая и будет обозначать некоторые конкретные «сконструированные» утверждение. Но ещё мы включили явную зависимость алгоритма проверки от того алгоритма-решения, к которому эта проверка относится:

У нас появилась часть $a$ – содержащая программный код. Для одних слов она – сертификат, а для других – часть слова. И тоже, вроде, ничего принципиального – мы можем взять любой язык из класса $\mathbb{NP}$ с «классическим» алгоритмом проверки и добавить в этот алгоритм такую часть $a$, от которой ничего не зависит, кроме требования, чтобы к размеру сертификата (при расчете ограничений) добавлялся ещё и её размер. Но мы этим не ограничимся, разумеется, и рассмотрим язык не с таким слегка изменённым «квазиклассическим» алгоритмом проверки.

Ещё один нюанс – полиномы $p(|t|, |s|)$ и $p_+(|t|, |s|)$ могут в некоторых случаях иметь степень ноль при аргументе $|s|$, если соответствующее им слово не будет зависеть от размера $|s|$, но это будет разбираться отдельно далее. Не принципиален для дальнейшего рассмотрения вопрос о зависимости $p(|t|, |s|)$ ещё и от $|a|$: Мы будем рассматривать такие $t$, размер которых больше размера $|a|$. Поэтому ограничение в любом случае оказывается в пределах $p(|t|, |s|)$.

Напоминаю, что $\exists a = \overline{\operatorname{Sol}(..., ...)}$ в логике – это аналог подстановки, так как $\exists x = b: A(x) \Leftrightarrow A(b)$.

При этом обозначение $\exists x = b: A(x)$ я использую в качестве сокращения для более правильного (но в котором больше скобок) обозначения: $\exists x (x = b \& A(x))$.

В свете последнего детального представления для $\mathbb{NP} \ne \mathbb{P}$ отмечу, что спецификой в реализации языка $LS$ является вот что: Часть данных, соответствующих программному коду алгоритма-решения $\overline{\operatorname{Sol}(... , ...)}$, является частью одного слова и частью сертификата для другого слова. И при этом те слова вида:

$t, s$

которые алгоритм $\operatorname{Sol}(... , ...)$ может подтвердить, как принадлежащие языку $LS$, полностью соответствуют наличию подтверждающих сертификатов вида

$a, y$, где $a = \overline{\operatorname{Sol}(... , ...)}$

И, таким образом, возможность алгоритма-решения $\operatorname{Sol}(... , ...)$ подтвердить принадлежность языку $LS$ слова

$t, s$

имеется лишь тогда, когда «расширенное слово»

$t, a, s$ или слово

$t, a$

принадлежит языку $LS$.

Это «расширенное» слово отличается от слова, про которое алгоритм-решение должен дать ответ. Таким образом, удалось разделить 2 функции, которые исполняет одно и то же слово в «классическом» языке из $\mathbb{NP}$ по 2-м разным словам.

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

Далее я ввожу в рассмотрение специфическое утверждение $AntiSol$, взятое (его идея) из теоремы о неопределимости математической логики. И это такое утверждение, которое алгоритм-решение $\operatorname{Sol}(... , ...)$ не может доказать в принципе. Более того, от способа и времени получения алгоритмом $\operatorname{Sol}(... , ...)$ ответа (который в корректном случае может быть только $0$), будет зависеть размер слова
$t, s$, и, возможно, его принадлежность языку $LS$.

Поэтому ограничение для времени поиска ответа для данного конкретного случая уже не может быть $p_+(..., ...)$ – от размера искомого слова: нельзя ставить время работы в зависимость от того, что само зависит от времени его работы.

К тому же, возможности алгоритма-решения $\operatorname{Sol}(... , ...)$ описываются НЕ искомым им словом, а соответствующим ему «расширенным» словом. Ведь нам удалось разделить 2 функции, которое исполняет слово в «классическом» случае на 2 разных слова, как уже упоминалось.

Поэтому в детальном представлении для $\mathbb{NP} \ne \mathbb{P}$ появится зависимость от времени работы алгоритма проверки для специфического случая и «расширенного» слова. И это будет $p_{\exists}(\overline{AntiSol})$, а соответствующее ему ограничение для алгоритма решения будет $p_{\exists +}(\overline{AntiSol})$. Кстати, для специфического случая мы будем иметь зависимость от слова, «которого нет» в языке $LS$ и судить о его размере можно лишь по времени работы алгоритма проверки. Вот на это время и будет опираться $p_{\exists +}(\overline{AntiSol})$.

Да, в пункте 6 потребуется поменять условие $s = ss(S)$ на $|s| \le |ss(S)|$ чтобы добиться зависимости размера слова от времени работы алгоритма-решения. Сам $AntiSol$ остаётся тем же и сохраняет все свои свойства и в уточненном варианте – насколько я поверхностно проверил.

После этого будет доказано, что с такими раскладами при результате $0$ у алгоритма $\operatorname{Sol}(\overline{AntiSol}, ...)$ за время $p_{\exists +}\overline{AntiSol}$ неизбежно (при достаточно больших по размеру $|\overline{AntiSol}|$) появится доказательство у утверждения $AntiSol$ (за счёт того, что размер доказательства зависит в основном от $s$, которое не участвует в ограничивающем полиноме для времени работы).

И вот здесь ранее я останавливал своё доказательство. Я думал, что для устранения возможности появления доказательства для $AntiSol$ при результате $\operatorname{Sol}(\overline{AntiSol}, ...) = 0$ от алгоритма $\operatorname{Sol}(\overline{AntiSol}, ...)$ потребуется неполиномиально больше времени на решение, чем требуется времени на проверку того, какой результат ($0$) будет в качестве этого решения. И это доказывало как раз задачу-первоисточник для $\mathbb{NP} \ne \mathbb{P}$ – что для любого алгоритма-решения есть такие задачи, проверка решения которых на равенство правильному ответу неполиномиально проще (быстрее), чем поиск этого ответа данным алгоритмом-решением.

Но теперь я думаю, что имеется доказательство и для $\mathbb{NP} \ne \mathbb{P}$

Просто всё детальное представление для $\mathbb{NP} \ne \mathbb{P}$ строится из предположения о том, какие смыслы у $1$ и $0$ должны быть у корректного алгоритма-решения. Но в специфическом случае для быстрого ответа смысл выводится логически. И смысл у $0$ для алгоритма $\operatorname{Sol}(\overline{AntiSol}, ...)$ для специфического случая при быстром возврате им результата может быть только один – «доказательство есть» )))) Потому что логика выше условных договорённостей.

Но раз условные договоренности являются частью детального представления для $\mathbb{NP} \ne \mathbb{P}$ и корректный алгоритм-решение обязательно должен их нарушить – то он уже не будет соответствовать «стандартным» требованиям к алгоритму-решению из класса $\mathbb{P}$. А раз это произвольный алгоритм-решение – то нет ничего «стандартного» и при этом корректного среди алгоритмов, которые делали бы рассматриваемый язык языком класса $\mathbb{P}$ в «стандартном» понимании.

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

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

Пример из жизни. Тебя спрашивают:

«Ты можешь спрогнозировать ответ, который даст на твои слова человек-наоборот?». Понятно, что если ты скажешь «Могу», то человек-наоборот ответит «Не могу», а если ты скажешь «Не могу», то ответом тебе будет «Могу».

Из «алгоритма проверки» ты знаешь, что ты – именно ты – не можешь дать правильный ответ на поставленный вопрос. И вопрос адресуется именно тебе. Поэтому ты сообщаешь «Не могу», потому что именно такой ответ сообщает о твоей неспособности в соответствии со сведениями от «алгоритма проверки». И этот же ответ заведомо означает, что человек-наоборот ответит «Могу». И ты дал правильное сообщение (прогноз), потому что стандартное «соглашение о кодировании» твоего сообщения-прогноза не работает в данном случае в отношении «человека-наоборот».

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

И да – мы выходим на формализацию понятия рефлексии, когда алгоритму для правильного ответа надо понимать, что вопрос задан именно ему. Это – гораздо принципиальнее и интереснее, чем даже вопрос про $\mathbb{NP} \ne \mathbb{P}$, потому что открывается возможность для математической формализации принятия решений «живыми» разумными системами, которая невозможна без рефлексии. То, что мы делаем по 100 раз на дню, выделяя и решая задачи, которые стоят именно перед нами. И то, что до сих пор никаким «боком» не было формализовано в математике.

[mihaild]

Ну договаривались же

Karan в сообщении #1253113 писал(а):

Далее: Вы пишете часть текста, не больше пары абзацев, который опирается на зафиксированные ранее определения.

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

Формулирую, что такое $\mathbb{NP} \ne \mathbb{P}$ – в деталях:

Я, конечно, тоже люблю длинные формулы, из которых сложно что-то понять, но их всё равно стоит писать более понятно. Например, говорить про конкретный алгоритм для данного языка тут не нужно - можно было бы просто писать $\overline{AntiSol} \in L$ (лучше эту букву оставить для обозначения языков). А еще стоит переменные обозначать одной буквой, а уже потом говорить, что вместо них подставляется. Это всё не критично, но сильно облегчает жизнь (как минимум читающим).
Ну да ладно - вроде бы утверждение вы записали верно (только потеряв где-то кванторы по некоторым переменным).
Словами: $P \neq NP$ тогда и только тогда, когда для некоторого языка из $NP$ для любого алгоритма и полинома существует плохое слово, на котором алгоритм либо ошибается, либо долго работает.

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

Напоминаю, что $\exists a = \overline{\operatorname{Sol}(..., ...)}$ в логике – это аналог подстановки, так как $\exists x = b: A(x) \Leftrightarrow A(b)$.

(это стоило вытащить повыше, я уже написал ответ на первую встречу с таким обозначением)
А зачем такое обозначение: Можно же просто в формуле везде писать $b$ вместо $x$.

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

спецификой в реализации языка $LS$

А что такое $LS$?
Что значит "алгоритм может подтвердить что-то там"?

Давайте всё же идти по шагам, и я буду скажем в этом сообщении записывать шаги, на которых мы согласились (укажите, если вы не согласны с чем-то из пунктов 0-4 тут).

"Картину в целом" читать не буду, извините.
Итак, краткое резюме, что я понял из вашего поста: вы собираетесь построить язык, принадлежащий $NP$, такой что для любого алгоритма и любого полинома существует слово из языка, которое этот алгоритм либо не принимает, либо работает на нем дольше этого полинома. Так?

(читать после ответа на предыдущий вопрос)

Это сделать, очевидно, не получится - возьмем просто алгоритм, принимающий все слова.

Зафиксированные договоренности
0. В определении МТ фиксируем два выделенных состояния начальное состояние и два финальных - принимающее и отвергающее.
1. МТ распознает язык $L \subseteq \{0, 1\}^*$, если для любого слова из $L$ она приходит в принимающее состояние, а для любого слова не из $L$ - в отвергающее.
2. МТ называется полиномиальной, если существуе такой полином $p(n)$, что для любого входа $x$ время ее работы на входе $x$ не превосходит $p(|x|)$.
3. $P$ - множество языков, для которых существует полиномиальная распознающая их МТ.
4. Язык $L$ принадлежит $NP$ в том и только в том случае, если существуют языки $L^\prime$, полином $q(n)$ и МТ $A$, распознающая $L^\prime$ такие что $x \in L \leftrightarrow \exists y: \overline{x, y} \in L^\prime$, время работы $A$ полиномиально от длины входа, а на словах вида $\overline{x, y}$ еще и не превосходит $q(|x|)$.
$n$ - некоторая фундаментальная мировая константа
5. $A$ - язык из слов вида $t, S, s$, где $S$ - число в двоичной записи, $s$ - строка из $S$ единиц, $t$ - теорема арифметики, у которой есть доказательство не длиннее $|s|^n$
6. $B$ - язык из слов вида $t, a, S, s$, где $\langle t, S, s\rangle \in A$, $a$ - некоторый алгоритм
7. $C$ - язык из слов вида $Anti_{Sol, S}, Sol, S$, где $Sol$ - некоторый алгоритм от трех аргументов, $S$ - число в двоичной записи, $Anti_{Sol, S}$ - формула, получаемая применением леммы о диагонализации к формуле $Sol(x, S, ss(S)) = 0$ (считая $x$ свободной переменной)
8. $LS = A \cup B \setminus C$

[dmitgu]

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

4. Язык $L$ принадлежит $NP$ в том и только в том случае, если существуют языки $L^\prime$, полином $q(n)$ и МТ $A$, распознающая $L$ такие что $x \in L \leftrightarrow \exists y: \overline{x, y} \in L^\prime$, время работы $A$ полиномиально от длины входа, а на словах вида $\overline{x, y}$ еще и не превосходит $q(|x|)$.

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

[mihaild]

(поправил опечатку: было "$A$, распознающая $L$", стало "$A$, распознающая $L^\prime$)

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

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

Отмечен. Там эквивалентность. Т.е. существует $y$ - значит $x \in L$, не существует - значит, $x \notin L$.

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

полиномиально быстро относительно проверки

Какой проверки?

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

слова, которого нет

Это что такое?

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

отсутствует определённый размер в некоторых случаях

У любого конкретного слова есть размер.