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

[dmitgu]

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

Непонятно - вы предлагаете вместо задачи "существует ли выполняющий набор для данной КНФ" решать задачу "выдает ли данный алгоритм выполняющий набор для данной КНФ"?

Я разбираю не КНФ. И к КНФ "авторизуемые задачи" не сводятся:

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

4.6. И не сводится потому, что получая алгоритм проверки – алгоритм-решение должен «понять», нет ли «персональной информации» для него. А это уже выбор – на основе терма. А к логике высказывания индивидные переменные и символы не сводятся.

КНФ - не является $\mathbb{NP}$-полной задачей, если "авторизуемые задачи" являются задачами из класса $\mathbb{NP}$.

Работа алгоритма имеет свое представление в языке - если это язык теории Пеано. И определённые "сертификаты" алгоритм не может сгенерировать в принципе. И для любого алгоритма есть такие нерешаемые задачи. Есть "слова", которые данный конкретный алгоритм заведомо не может подтвердить сертификатом. Если речь идёт о детерминированных алгоритмах - а именно их решение нас и интересует, чтобы свести $\mathbb{NP}$ к $\mathbb{P}$.

[mihaild]

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

КНФ - не является $\mathbb{NP}$-полной задачей, если "авторизуемые задачи" являются задачами из класса NP.

О как. Т.е. вы доказываете что-то не про известный класс $NP$, а про какой-то другой? Потому что $3-SAT$ является широко известным примером $NP$-полной задачи. Или в доказательстве ошибка?)

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

[dmitgu]

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

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

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

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

Я же пытаюсь реализовать программу Гильберта, а когда он и другие (Гёдель в частности) стал рассматривать доказательства о доказательствах - результат получился неожиданный. И я рассматриваю такие "сертификаты", которые строятся на базе доказательств. А в качестве "слов" беру утверждения теории 1-го порядка.

А теории 1-го порядка в состоянии "представлять" алгоритмы, их работу и утверждения о них.

[mihaild]

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

Да, в доказательстве ошибка

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

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

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

Так, для начала - формальные определения понятия "алгоритм", "машина Тьюринга", "время работы", "классы $P$ и $NP$" вам хорошо известны?

Доказательство теоремы Кука заключается примерно в том, что для любой МТ и любого числа $n$ можно построить "кодирующую" МТ, которая по слову $X$ за полиномиальное от длины $X$ время генерирует КНФ (длина автоматически получается полиномиальной от длины $X$), которая выполнима тогда и только тогда, когда МТ принимает $X$ за время, не превосходящее $|X|^n $. Что и означает, что задача $SAT$ является $NP$-полной.
(на самом деле генерировать формулу можно даже равномерно по всем МТ - получится полиномиальная по длине кода МТ и экспоненциальная по $n$ сложность - но это не нужно)

Вы не согласны с возможностью построения такой МТ? (можете привести конкретную пару МТ, $n$, для которых такую "кодирующую" МТ построить нельзя?) Или с чем?

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

И я рассматриваю такие "сертификаты", которые строятся на базе доказательств.

Одна из важных идей в этой области - сертификат может быть устроен как угодно.

[dmitgu]

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

Доказательство теоремы Кука заключается примерно в том, что для любой МТ и любого числа $n$ можно построить "кодирующую" МТ, которая по слову $X$ за полиномиальное от длины $X$ время генерирует КНФ (длина автоматически получается полиномиальной от длины $X$), которая выполнима тогда и только тогда, когда МТ принимает $X$ за время, не превосходящее $|X|^n $

Да, а если есть отдельная часть $X$, неполиномиально меньшая, чем сам $X$? :) И алгоритм проверки «Сфинкс», для некоторых алгоритмов-решений создающий свою подзадачу на основе именно части $X$, а не целого?

Вот смотрите, разберём переход от описания для слов:

$\operatorname{Sph}(\overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ..., ..., ...)}, \overline{-}, ..., ..., ...)}, t_{Oed, S}, S, s, y) = 0$

или

$\operatorname{Sph}(d_{Oed}, t_{Oed, S}, S, s, y) = 0$

к описанию подзадачи.

2ой частью слова тут является утверждение: $t_{Oed, S} = \overline{\operatorname{AntiOed_S}() = 0}$.

А 1ой частью слова является тут «избранный» алгоритм-решение «Эдип» с конкретным аргументом долга:

$d_{Oed} = \overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ..., ..., ...)}, \overline{-}, ..., ..., ...)}$

И для $\operatorname{Oed}(\overline{\operatorname{Sph}(…, …, …, …, …)}, d_{Oed}, t_{Oed, S}, S, s)$ нет проблем выдать $0$ – как и для других , $\operatorname{NotOed}(\overline{\operatorname{Sph}(…, …, …, …, …)}, d_{Oed}, t_{Oed, S}, S, s)$ но речь-то о:

$\operatorname{Oed}(\overline{\operatorname{Sph}(…, …, …, …, …)}, \overline{-}, t_{Oed, S}, S, s)$

ведь именно о нём речь у «Сфинкса» с его нулём: $\operatorname{Sph}(d_{Oed}, t_{Oed, S}, y, S, s) = 0$.

А на $\operatorname{NotOed}(\overline{\operatorname{Sph}(…, …, …, …, …)}, \overline{-}, t_{Oed, S}, S, s)$ предыдущая формула для «Сфинкса» не распространяется. Для него - $\operatorname{Sph}(\overline{-}, t_{Oed, S}, y, S, s) = 0$. И ему (не-Эдипу) остаётся «довольствоваться» обычным временем работы «Сфинкса», полиномиальным от размера всего $|X|$ (от |s| в частности).

Вот тут-то и возникает терм и невозможность свести выражение к логике высказываний (к КНФ). И для конкретно этих параметров полином для времени работы

$\operatorname{Sph}(d_{Oed}, t_{Oed, S}, y, S, s) = 0$

будет зависеть от $|S|$, но не от $|s|$. И от $|y|$ не будет зависеть. А отличие между $|S|$ и $|s|$ - неполиномиально большое (количество десятичных цифр и само число). Так я строю свою задачу в следующем разделе.

[mihaild]

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

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

$\operatorname{Sph}(\overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ..., ..., ...)}, \overline{-}, ..., ..., ...)}, t_{Oed, S}, S, s, y) = 0$

Что такое $Sph$ и $Oed$? Алгоритмы? Какие (что на вход, что на выход)? Что скрывается за многоточиями? Что означает надчеркивание? Что значат все используемые буквы?

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

Да, а если есть отдельная часть $X$, неполиномиально меньшая, чем сам $X$?

Что такое "отдельная часть $X$"?
Формула строится примерно так: мы на каждый из $p(|X|)$ шагов выделяем переменные, которые будут кодировать конфигурацию МТ на очередном шаге. Дальше нам нужно записать, что начальная конфигурация - слово $X$, конечная - принимающая, и все переходы правильные. Никакого "разбора" что "внутри" $X$ нет (и формулы с разными $X$ одной и той же длины будут отличаться друг от друга только в небольшой части, говорящей про начальную конфигурацию).

[dmitgu]

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

Что такое $Sph$ и $Oed$? Алгоритмы? Какие (что на вход, что на выход)?

Алгоритм проверки:

$Sph(d, t, S, s, y)$ - аргументы "долга" (алгоритма-решения), теоремы, аргументы размера (наибольшая длина доказательства) в виде числа и строки "11...1" длиной $S$ (иначе Сфинкс вернёт $0$), $y$ - доказательство.

Разбираемый нами алгоритм-решение.

$Oed(a, d, t, S, s)$ - первый аргумент $a$ - программный текст алгоритма проверки (задача из $NP$). Дальше как в предыдущем

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

Что скрывается за многоточиями?

Вот (не всё):

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

2.3. Пояснение к пункту 2.1 о способе подстановки аргументов в один алгоритм с получением другого алгоритма:

Алгоритм по превращению одного текста алгоритма в другой – с подставленным первым аргументом – можно изображать так: $Arg1(\overline{MyArg}, \overline{A(..., ...)})$. Мы использовали выше и продолжим использовать далее обозначения типа $B(\overline{A(..., ...)}, x), B(\overline{A(..., ...)}, ...)$ и т.п. Подразумевается, что таким образом мы используем какой-то стандартный известный способ по превращению алгоритма, зависящего от нескольких аргументов в некие другие алгоритмы – в которых часть аргументов (или даже все) исходного алгоритма уже подставлена. А можем передавать тексты алгоритмов и без подставленных аргументов, как, например $\overline{A(..., ...)}$.

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

Что означает надчеркивание?

Вот что:

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

И по поводу обозначения – фрагмент из начала раздела 4 «Предварительное замечание о программе Гильберта для теории алгоритмов» -

На самом деле, алгоритм-решение должен получать текст программы алгоритма проверки и быть вида:

$M(\overline{L(x, y)}, x)$

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

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

Никакого "разбора" что "внутри" $X$

Да никто и не разбирает :) Это как с "сертификатом" - если его размер превышает полиномиальные ограничения - он отвергается алгоритмом проверки. И время на рассмотрение его "хвоста" даже не тратится.

[mihaild]

И что делает алгоритм $Sph$? Говорит, является ли $y$ доказательством чего-то про остальные аргументы - если да, то чего? Тот же вопрос про $Oed$.

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

программный текст алгоритма проверки (задача из $NP$)

Не-не-не, задача из $NP$ - это язык, а не алгоритм.

Как именно будет выглядеть задача из $NP$, которая не сводится к $SAT$? "Множество слов, на которых $Sph$ и $Oed$ что-то там"?

По остальным обозначениям вроде пока понятно.

[dmitgu]

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

что делает алгоритм $Sph$? Говорит, является ли $y$ доказательством чего-то про остальные аргументы - если да, то чего? Тот же вопрос про $Oed$

Да, проверяет - доказывается ли $t$ доказательством y алгоритмом $d$ с учётом известных (для Сфинкса) ограничений на возможности $d$ - а доказательство в пределах длины $S$. Если длина строки $|s|$ меньше числа (не размера!) $S$ - то тоже негативный ответ. Если проверку не прошла - $0$. Прошла - $1$.

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

Не-не-не, задача из $NP$ - это язык, а не алгоритм.

Это как раз очень интересно :) В 1ом разделе я как раз разбираюсь, чего вообще понимают под задачей из класса $NP$. Штука - не формализованная и программа Гильберта для неё не проводилась. Вот чтоб "решить" - превратив задачу из $NP$ в задачу из $P$ - надо же передать текст некому алгоритму-решению. А текст чего? Я считаю - программный текст алгоритма проверки. И из него уже вычислять всякие полиномиальные ограничения. А что алгоритм проверки "ходит" парой с формулой на полиномиальное ограничение сертификата? А если формула не правильная? Математический класс не может зависеть от того, знаем мы или нет какое там полиномиальное ограничение. Задача из класса $NP$ вообще не имеет разрешимого способа распознания - потому что любое конечное время работы на единичной задаче не нарушает полиномиальность, но нельзя разрешить вопрос об остановке. Поэтому и принадлежность задачи классу $NP$ - неразрешимый вопрос.

Более того, в учебниках не сказано явно в какой модели интерпретации строится метаматематика в теории алгоритмов. В стандартной? Это когда на ленте машины Тьюринга число $11000$ представлено блоком из $11000$ единиц? Так никакую оценку по размерам и времени работы нельзя провести. Поэтому проблемы построения формализма в теории алгоритмов сейчас - огромные. И не я в этом виноват :) Я как раз считаю нужным и провожу - в меру своих сил - программу Гильберта. А без этого даже инструментов нет по решению проблем сложности в теории алгоритмов. Но чтоб всё сказать - это мне надо разделы 1 и 2 сюда запостить...

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

Как именно будет выглядеть задача из $NP$, которая не сводится к $SAT$

Вчерне я обозначил её раньше - когда пара:

алгоритм долга:

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

$d_{Oed} = \overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ..., ..., ...)}, \overline{-}, ..., ..., ...)}$

и теорема:

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

$t_{Oed, S} = \overline{\operatorname{AntiOed_S}() = 0}$.

оказывались информацией для возможностей поиска "Эдипа" в отношении пары:
$\overline{-}$ и той же теоремы. И шансы "Эдипа" по этой информации - нулевые.

Вот тут "фишка" - есть "персональная подсказка", которая неполиномиально быстрее "общего" алгоритма.

Да, "Эдип" должен "понимать", но это условность. А он в любом случае должен понимать условности - хотя бы язык, на котором записан программный код. И если он быстро ответит 0 (ноль) - не могу найти доказательство, то доказательство - будет! В пределах s. А если будет "тянуть время", то выйдет за рамки полиномиальности времени получения доступной ему инфы.

[Xaositect]

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

Это как раз очень интересно :) В 1ом разделе я как раз разбираюсь, чего вообще понимают под задачей из класса $NP$. Штука - не формализованная и программа Гильберта для неё не проводилась.

Вы, может быть, официальную формулировку института Клэя прочитаете?

[dmitgu]

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

Вы, может быть, официальную формулировку института Клэя
прочитаете?

Нет. Английский и на бытовом уровне почти не знаю.

[Xaositect]

Перевел определения:

Стивен Кук (перевод мой) писал(а):

Формально, элементами класса $\mathbf{P}$ являются языки. Пусть $\Sigma$ - конечный алфавит(то есть конечное непустое множество), содержащий по крайней мере 2 элемента, и $\Sigma^*$ - множество всех конечных слов в алфавите $\Sigma$. Язык в алфавите $\Sigma$ --- подмножество $\Sigma^*$. С любой машиной Тьюринга $M$ связан ее входной алфавит $\Sigma$. Для любого слова $w$ из $\Sigma^*$ существует вычисление машины $M$ на входе $w$. (Машина Тьюринга и вычисление определены формально в приложении.) Будем говорить, что $M$ принимает слово $w$, если в конце вычисления машина находится в принимающем состоянии. Таким образом, $M$ не принимает $w$, если вычисление завершается в отвергающем состоянии машины, или если процесс вычисления не завершается. Язык, распознаваемый машиной $M$ (обозначается $L(M)$) - это язык в алфавите $\Sigma$, определяемый как $L(M) = \{ w\in \Sigma^* \mid M \text{ принимает } w \}$. Обозначим $t_M(w)$ количество шагов вычисления $M$ на входе $w$ (см. приложение). Если вычисление не завершается, то $t_M(w) = \infty$. Для $n \in \mathbb{N}$ обозначим $T_M(n)$ время вычислений на слове длины $n$ в худшем случае, то есть $T_M(n) = \max \{t_M(w) \mid w \in \Sigma^n \}$, где $\Sigma^n$ - множество всех слов длины $n$ в алфавите $\Sigma$. Будем говорить, что машина $M$ работает полиномиальное время, если существует $k$ такое, что для любого $n$ верно $T_M(n) \leq n^k + k$. Теперь мы можем определить класс языков $\mathbf{P}$ как

$$\mathbf{P} = \{L \mid L = L(M) \text{ для некоторой машины Тьюрина $M$, которая работает полиномиальное время}\}.$$

Обозначение $\mathbf{NP}$ расшифровывается как "nondeterministic polynomial time", поскольку этот класс изначально определялся в терминах недерминированных машин. Однако сейчас обычно дается эквивалентное определение, использующее понятие проверяющего отношения - бинарного отношения $R \subset \Sigma^* \times \Sigma_1^*$ для некоторых конечных алфавитов $\Sigma$ и $\Sigma_1$. Каждому такому отношению мы ставим в соответствие язык в алфавите $\Sigma \cup \Sigma_1 \cup \{\sharp\}$ определяемый как

$$L_R = \{w \sharp y \mid R(w, y) \},$$

где символ $\sharp$ не принадлежит языку $\Sigma$. Будем говорить, что $R$ проверяется за полиномиальное время, если $L_R \in \mathbf{P}$. Определим класс языков $\mathbf{NP}$ следующим образом: язык $L$ в алфавите $\Sigma$ принадлежит $\mathbf{NP}$ если и только если существует $k \in \mathbb{N}$ и проверяемое за полиномиальное время бинарное отношение $R$ такие, что для любого слова $w \in \Sigma^*$

$$w \in L \Leftrightarrow \exists y\,(|y| \leq |w|^k \text{ и } R(w, y)),$$

где $|w|$ и $|y|$ - длины слов $w$ и $y$ соответственно.
Формулировка проблемы. Верно ли, что $\mathbf{P} = \mathbf{NP}$?

[dmitgu]

Спасибо за перевод.

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

язык $L$ в алфавите $\Sigma$ принадлежит $\mathbf{NP}$ если и только если существует $k \in \mathbb{N}$ и проверяемое за полиномиальное время бинарное отношение $R$ такие, что для любого слова $w \in \Sigma^*$

$$w \in L \Leftrightarrow \exists y\,(|y| \leq |w|^k \text{ и } R(w, y)),$$

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

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

[Xaositect]

Я, честно говоря, так и не понял, что все эти Ваши алгоритмы делают. Напишите формально, какой язык $L$ и какое отношение $R$ будут у Вашей "нехорошей" задачи?

[mihaild]

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

доказывается ли $t$ доказательством y алгоритмом $d$ с учётом известных (для Сфинкса) ограничений на возможности $d$ - а доказательство в пределах длины $S$.

Вот это я не могу прочитать чисто синтаксически (кажется, предложение не согласовано). А все разумные попытки поправить приводят к неизвестным странным терминам типа "доказательство алгоритма".

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

В 1ом разделе я как раз разбираюсь, чего вообще понимают под задачей из класса $NP$

А что разбираться? Язык принадлежит $NP$, если существует недетерменированная полиномиальная МТ, проверяющая его за полиномиальное время. Для арифметических языков (задаваемых формулой - в том числе всех перечислимых) это легко формализуется в арифметике, для произвольных - в любой теории, умеющей работать с произвольными подмножествами $\mathbb{N}$. Вполне возможно, что кто-то даже явно построил формулу.

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

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