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

[dmitgu]

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

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

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

Это неправда. Существует алгоритм, получающий доказательство того, что задача лежит в $\mathrm{NP}$, и выдающий полиномиальный алгоритм ее решения.

Гм... Вроде я про это же говорил, но только в терминах текста? Я же исхожу из существования текста алгоритма-решения для $NP$ полной задачи.

Тогда - у нас есть полиномиальное преобразование, позволяющее из текста $\widehat{R_{L_0}(x)}$ - решения некоторой $NP$-полной задачи с предикатом $L_0(x, y)$- получать решение для произвольной задачи $L_i(x, y)$ из $NP$ (есть такая теорема). Проcто есть алгоритм $T(a, b)$, полиномиальный по времени своей работы, который из текста $a$ решения для NP-полной задачи делает текст решения для той задачи, текст которой представлен в $b$:
$[z=\widehat{R_ {L_0}(x)}] \Rightarrow [T(z, \widehat{L_i(x, y)}) = \widehat{R_{L_i}(x)} ] $
где шляпа над обозначением для алгоритма обозначает текст данного алгоритма (ну или его Гёделев номер - что по сути то же самое).
Притом это без всякого значка «существование» в левой стороне импликации - там может быть любой z, который является текстом решающего алгоритма (там могут быть разные решения). И алгоритм $T$ тоже вполне конкретный. Мы знаем, как преобразовать решение $NP$-полной задачи в решение любой задачи $NP$, даже не зная самого решения $NP$-полной задачи.
Так вот, если у нас решена $NP$-полная задача $L_0(x, y)$, то:
1. $ (\exists z) z=\widehat{R_ {L_0}(x)}$ - существует текст решающего ее алгоритма;
2. $[z=\widehat{R_ {L_0}(x)}] \Rightarrow [T(z, \widehat{L_i(x, y)}) = \widehat{R_{L_i}(x)} ]$ (это преобразование разобрано раньше);
3. $[(\exists z) z=\widehat{R_ {L_0}(x)}] \Rightarrow [T(z, \widehat{L_i(x, y)}) = \widehat{R_{L_i}(x)} ]$ - из п. 2 по правилу вывода для квантора $\exists$ (по крайней мере в «Основаниях математики» Гильберта и Бернайса это правило вывода, в других книгах это иногда выводится из другого набора аксиом);
4. $[T(z, \widehat{L_i(x, y)}) = \widehat{R_{L_i}(x)} ]$ - из пп. 1 и 3 по правилу вывода $MP$
Последний пункт и есть тот алгоритм, который находит текст алгоритма-решение за полиномиальное время для любой задачи из $NP$. И он выведен из предположения 1. Поэтому п. 4 - это необходимое условие для случая $NP = P$.

[dmitgu]

Ой, с п. 3 иначе (надо разорвать взаимозависимость частей импликации по $z$):
3. $[z=\widehat{R_ {L_0}(x)}] \Rightarrow [(\exists z)T(z, \widehat{L_i(x, y)}) = \widehat{R_{L_i}(x)} ]$ - это из п. 2, тавтологии: $W(z) \Rightarrow (\exists z) W(z) $ и силлогизма
4. $[(\exists z) z=\widehat{R_ {L_0}(x)}] \Rightarrow [(\exists z)T(z, \widehat{L_i(x, y)}) = \widehat{R_{L_i}(x)} ]$ - из п. 3 по правилу вывода для квантора $\exists$ (по крайней мере в «Основаниях математики» Гильберта и Бернайса это правило вывода, в других книгах это иногда выводится из другого набора аксиом);
5. $[(\exists z)T(z, \widehat{L_i(x, y)}) = \widehat{R_{L_i}(x)} ]$ - из пп. 1 и 4 по правилу вывода $MP$
Последний пункт и есть тот алгоритм, который находит текст алгоритма-решение за полиномиальное время для любой задачи из $NP$. И он выведен из предположения 1. Поэтому п. 5 - это необходимое условие в случае $NP = P$.

[Xaositect]

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

Тогда - у нас есть полиномиальное преобразование, позволяющее из текста $\widehat{R_{L_0}(x)}$ - решения некоторой $NP$-полной задачи с предикатом $L_0(x, y)$- получать решение для произвольной задачи $L_i(x, y)$ из $NP$ (есть такая теорема).

Не знаю такой теоремы. Даже если кроме текста программы для $L_i$ дается еще полином, ограничивающий длину сертификатов, у меня все равно только экспоненциальный алгоритм получается.

[dmitgu]

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

Не знаю такой теоремы. Даже если кроме текста программы для $L_i$ дается еще полином, ограничивающий длину сертификатов, у меня все равно только экспоненциальный алгоритм получается.

Это Теорема Кука. - я смотрю в книге «Теория алгоритмов» (для ВУЗов - а не та, что для среднего проф. образ.) В.И. Игошин Раздел 8.3. Основы теории $NP$-полных массовых проблем Подраздел «$NP$-полнота проблемы выполнимости для формул логики высказываний», Теорема 8.3.18.
Там за основу берется задача из $NP$ - проблема выполнимости формул алгебры высказываний (назовем ее ВЫП). И доказывается ее $NP$-полнота. Которая в книге определяется как такая задача, к которой может быть сведена любая другая так, что слово из другой будет отображаться полиномиально быстрой функцией на слово из $NP$-полной и будет проходить проверку тогда и только тогда, когда соответствующее ему слово в $NP$-полной будет проходить проверку.
А доказательство строится на заведении кучи логических переменных, которыми описывается работа алгоритма проверки $L$ сводимой $NP$-задачи. То есть - ими переписываются инструкции машины Тьюринга, начальные данные, переходы и т.п. Описывается, что она не может быть сразу в двух состояниях и т.д. И поскольку алгоритм $L$ полиномиален, то и конструкция оказывается такой же. Ну и получается, что всякую единичную задачу из массовой задачи $NP$ можно свести к ВЫП за полиномиальное время, решить - если решение ВЫП есть - и узнать результа для этой единичной задачи за полиномиальное время в итоге. Вот такое доказательство - в общих чертах.

[Xaositect]

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

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

Это правда. А вот построить по алгоритму проверки сертификата полиномиальный алгоритм решения - это уже не полиномиальная конструкция.

[dmitgu]

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

Это правда. А вот построить по алгоритму проверки сертификата полиномиальный алгоритм решения - это уже не полиномиальная конструкция.

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

[Xaositect]

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

[dmitgu]

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

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

Потому что прописан метод преобразования решения из решения для $NP$-полной задачи в решение произвольной. И он строится на:
1. выписывании полиномиальной по размеру конструкции из текста заданного для решения алгоритма проверки задачи из $NP$ в форму задачи ВЫП (сведение данной задачи к решенной)
2. Решение выписанной задачи.
3. Обратное написание ответа (да/нет - для единичной задачи на входе).

Последовательность полиномиальных действий (пп 1-3) - полиномиальна. Притом нас интересует даже не все 1-3 пункты, а тот алгоритм, который выписывает нужную конструкцию - на основании текста данной задачи и аргумента для проверки, плюс тот, что решает. Аргумент "слово" там произвольный и не задан, но текст заданной задачи - аргумент. А сам алгоритм переписывания инструкций в задачу из ВЫП довольно примитивный и близок по количеству шагов к фиксированной степени от того, что задает ограничивающий заданную задачу полином (и фактически этот алгоритм представлен в доказательстве теоремы Кука). Происходит выписывание элементов конъюнктивной нормальной формы как одно состояние должно перейти в другое и в каждом - дизъюнкция возможных состояний на ленте, символа и текущей инструкции машины тьюринга. Но это уже работа по выписыванию, а сам алгоритм - короткий. Длина складывается из: длина обработчика текста задачи, сам текст задачи, алгоритм решения, выдача ответа. Если убрать аргумент (текст задачи), то это вообще константа. А если считать частью - то длина линейна от длина текста решаемой задачи.

[Xaositect]

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

1. выписывании полиномиальной по размеру конструкции из текста заданного для решения алгоритма проверки задачи из $NP$ в форму задачи ВЫП (сведение данной задачи к решенной)

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

[dmitgu]

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

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

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

[Xaositect]

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

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

Смотрите.
Если известно $c$, то функция "Дано слово длины $n$, сделать 1 шаг $n^c$ раз" выполняется полиномиальное время.
А общая задача: "Дано слово длины $n$ и число $c$, сделать 1 шаг $n^c$ раз" - не полиномиальна.

У нас для разных задач из $\mathrm{NP}$ будет разное $c$, поэтому оно должно быть частью входа. И значит у нас второй случай, а не первый

[dmitgu]

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

Если известно $c$, то функция "Дано слово длины $n$, сделать 1 шаг $n^c$ раз" выполняется полиномиальное время.
А общая задача: "Дано слово длины $n$ и число $c$, сделать 1 шаг $n^c$ раз" - не полиномиальна.

Гм... Я отвечал на вопрос о размере алгоритма, решающего заданную (одну из) задачу из $NP$. И размер этого алгоритма - линейный от размера текста задачи. То есть - тут все полиномиально. А решение единичной задачи всегда задает свое $n$, разумеется. И "общая задача" (массовая?) тут вроде не возникает? То есть, массовая задача имеет решающий алгоритм составленный за линейное время, а единичная вполне вписывается в ограничивающий полином с заданным в нем фиксированным $c$.

А вот для другой задачу из $NP$ будет составлен уже другой алгоритм, который будет отличаться от предыдущего только текстом решаемой задачи (включая и текст полинома). И там будет уже другой фиксированный $c$, но полиномиальность составления этого алгоритма (от размера его текста) и времени его работы на единичной задачи (от $n$) все равно будут "при нем".

[Xaositect]

Так, я начинаю чего-то не понимать.

Я думал, что мы говорим про общую машину, которой на вход дается какая-то $\mathrm{NP}$-задача, а на выходе получается полиномиальный алгоритм ее решения. И она должна работать на разных алгоритмах с разными $c$.

[dmitgu]

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

Так, я начинаю чего-то не понимать.

Я думал, что мы говорим про общую машину, которой на вход дается какая-то $\mathrm{NP}$-задача, а на выходе получается полиномиальный алгоритм ее решения. И она должна работать на разных алгоритмах с разными $c$.

А... Нет - там для каждой задачи приходится рисовать свой алгоритм. Но однообразным образом. Собственно, это "автоматически" отобразилось в формуле:

Цитата:

5. $[(\exists z)T(z, \widehat{L_i(x, y)}) = \widehat{R_{L_i}(x)} ]$ - из пп. 1 и 4 по правилу вывода $MP$

Текст $\widehat{L_i(x, y)}$ разный для разных задач. И от него зависит работа алгоритма $T$

[Xaositect]

Но Вы утверждали, что $T$ полиномиальный. А я Вам говорю, что полиномиальным от текста задачи он быть не может.