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

[Xaositect]

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

Ну да, так и будет. Просто для любого приведенного диофантова уравнения есть его не приведенные аналоги какой угодно длины. И если для приведенного уравнения есть только решения с длиной больше $L^3$, то для него в нашей постановке задачи решений нет вообще, но в нашей задаче это же уравнение представлено бесконечным множеством неприведенных уравнений и это же самое решение для бесконечного большинства таких представлений будет в рамках $L^3$.

Ну хорошо, а почему эта задача будет неразрешимой?

-- Вт май 27, 2014 05:00:19 --

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

[dmitgu]

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

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

Гм... Хороший вопрос. Ясно, что в поиске решения каждой индивидуальной задачи из нашей массовой задачи из NP мы ищем среди ограниченного количества решений (с числом цифр не больше $L^3$ от длины уравнения). И в этом смысле алгоритм есть (хотя бы не полиномиальный). И тут еще вопрос - если есть разрешимость нашей задачи, то можно ли свести ее к разрешимости задачи о диофантовых уравнениях вообще. Если можно - тогда наша задача тоже неразрешима.
Тут надо подумать - может в этом и заковыка ) Я напишу в течение суток удалось или нет.

[dmitgu]

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

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

Вы, конечно правы, указав что поиск корней диофантова уравнения в неограниченной области значений переменных (как принято в просто логике) сильно отличается от поиска в областях ограниченных (в теории алгоритмов). Мои ошибочные тут шаблоны из логики меня подвели - спасибо Вам, что помогли быстрее распутаться. И все же, диофантовы уравнениях кажутся теоретически интересной задачей для понимания $\mathrm{NP}$... Вот 2 варианта (показательные) для некоторого диофантова уравнения:

1. нет решающих его значений для его переменных среди всех натуральных чисел $\mathrm{N}$,
2. нет решающих его значений для его переменных среди чисел с полиномиальным количеством цифр

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

[dmitgu]

Раздел 1. Предварительная информация о диофантовых множествах и т.п.
Чтоб опираться на единую базу, я привожу необходимые определения и теоремы с их нумерацией из книги В.И.Игошин «Теория алгоритмов: Учебное пособие». ISBN 978-5-16-005205-2 (это издание из серии «Высшее образование», есть книга с таким же названием этого автора, но для среднего проф. образования).
Раздел 10.1. Десятая проблема Гильберта, Подраздел «Диофантовы множества и их связь с перечислимыми множествами».
Определение 1. Пусть $M \subseteq \mathbb{N}$. Множество M называется диофантовым, если существует многочлен $p(x, y_1, y_2, \ldots , y_n)$ с целыми коэффициентами, такой, что для всех $x \in \mathbb{N}$ имеем:

$$ x \in M \Longleftrightarrow (\exists y_1 \in \mathbb{N})(\exists y_2 \in \mathbb{N})\ldots (\exists y_n \in \mathbb{N}) [p(x, y_1, y_2, \ldots , y_n)=0] $$

Определение 2. Перечислимые множества - это такие, которые могут быть порождены некоторым алгоритмом, или которые являются множеством значений некоторых вычислимых функций.
Приведу для справки и некоторые более базовые определения, на которые опирались изложенные выше определения:
Раздел 5.1 Нумерация алгоритмов и вычислимых функций, Подраздел «Вычислимые функции».
Определение 3. Область значений функции $f$ есть подмножество множества $\mathbb{N}$:

$$ \operatorname{Im}(f) = \{ y \in \mathbb{N} \colon (\exists x_1, x_2, \ldots , x_n) (f(x_1, x_2, \ldots , x_n) = y) \}$$

Определение 4. Функция $f(x_1, x_2, \ldots , x_n)$ называется вычислимой, если существует алгоритм, позволяющий вычислять её значения для тех наборов аргументов, для которых она определена, и работающей вечно, если функция для данного набора значений аргументов не определена.
Следующее определение соответствует Википедии (Статья «Класс NP») - оно эквивалентно определению через недетерминированную машину Тьюринга, но удобней для наших целей.
Определение 5. Язык L называется принадлежащим классу $\mathbb{NP}$, если существуют двуместный предикат $R(x,\, y)$ из класса $\mathbb P$ (то есть вычислимый за полиномиальное время) и константа $c > 0$ такие, что для всякого слова $x$ верно:

$$(x \in L) \Longleftrightarrow (\exists y)( (|y| < |x|^c) \And R(x,\, y))$$

где $|y|$, $|x|$ — длина (разрядность) слов $y$, $x$.
Слово $y$ называется сертификатом принадлежности $x$ языку $L$.
При заданных соответствующих предикате $R(x,\, y)$ и константе $c$ мы имеем массовую проблему (задачу) распознавания, относящуюся к классу задач $\mathbb{NP}$, а вопрос о принадлежности конкретного слова $x$ языку $L$ - это единичная задача «внутри» данной массовой задачи. Эту единичную задачу можно решить прямым перебором всех возможных сертификатов $y$ с разрядностью $(|y| < |x|^c) $ и проверкой $R(x,\, y)$ для $\forall y (|y|<|x|^c)$, чтобы обнаружить истинность хоть на одном из таких $y$ (либо не обнаружить ни на одном, что означает тогда $x \notin L$). Но такой перебор по времени своей работы экспоненциально долгий.
Проблема равенства $\mathbb{NP}$ и $\mathbb{P}$. Вопрос состоит в том, существует ли такой способ, чтобы для любой массовой задачи из класса $\mathbb{NP}$, для любой единичной задачи из этой массовой задачи можно было за полиномиальное (от размера проверяемого слова $x$) время найти сертификат $y$ принадлежности данного $x$ к языку данной массовой задачи $L$, или выяснить, что такого сертификата нет.
Если говорить технически (опираясь на тезис Чёрча), то вопрос состоит в поиске алгоритма, на вход которому подается текст соответствующего алгоритма $R(x,\, y)$, константа $c$, проверяемое слово $x$. А на выходе через полиномиальное время работы (то есть меньшее, чем $|x|^{C_1} + C_2$, где $C_1$ и $C_2$ некоторые константы) в качестве результата получается сертификат $y$ принадлежности $x$ к языку данной массовой задачи $L$, либо признак отсутствия такого сертификата (что означает тогда $x \notin L$).
Две следующих теоремы и их номера переписаны из книги В.И.Игошин «Теория алгоритмов: Учебное пособие» (о ней сказано в начале сообщения). Раздел 10.1. Десятая проблема Гильберта, Подраздел «Диофантовы множества и их связь с перечислимыми множествами».
Теорема 10.1.1. Всякое диофантово множество является перечислимым множеством.
Теорема 10.1.2. Пусть $M \subseteq \mathbb{N}$ и M - перечислимое множество. Тогда множество M является диофантовым множеством.
Это значит, что вместо любого алгоритма мы можем получить точно те же значения что и этот алгоритм (и никаких иных значений) из некоторого диофантова уравнения $p(x, y_1, y_2, \ldots , y_n) = 0$. Где $x$ является значением алгоритма (и частью решения уравнения) тогда и только тогда, когда $(\exists y_1 \in \mathbb{N})(\exists y_2 \in \mathbb{N})\ldots (\exists y_n \in \mathbb{N}) [p(x, y_1, y_2, \ldots , y_n)=0]$
Последняя теорема позволила элементарно решить Десятую проблему Гильберта (Теорема 10.1.3. в упомянутой только что книге) о неразрешимости диофантовых уравнений. Метод доказательства:
1. Строится алгоритм $A_A$, который:
1-а. Вычисляет произвольный заданный ему алгоритм, зависящий от одной переменной $x$ при произвольных $x$ из $\mathbb{N}$ - если такое вычисление дает результат;
1-б. Выдает в качестве своего результат только тот результат заданного ему алгоритма на заданном $x$, который совпал с номером этого заданного алгоритма (номером алгоритма можно считать его текст, например). А в остальных случаях (включая неполучение результата) $A_A$ значения не выдавет (зацикливался, например).
2. Порожденное алгоритмом $A_A$ множество (значений) $A$ перечислимо, но не разрешимо, потому что его дополнение $B$ отличается от области значения каждого алгоритма хотя бы одним значением (если у алгоритма есть значение равное его номеру, то в $B$ - нет, а если у алгоритма нет такого значения, то оно есть в $B$).
3. Соответственно множеству $A$ было построено (по Теорема 10.1.2.) диофантово уравнение $p_A(x, y_1, y_2, \ldots , y_n) = 0$
4. Это уравнение неразрешимо в силу п.2.
5. Если бы диофантовы уравнения были разрешимы, то подставляя произвольное число в $x$ в уравнении $p_A(x, y_1, y_2, \ldots , y_n) = 0$, можно получить некое диофантово уравнение, и выяснять - решается ли оно и принадлежит ли $x$ множеству $A$ либо множеству $B$.
6. п.5 невозможен в силу п.4, поэтому диофантовы уравнения в общем случае неразрешимы.
Теорему 10.1.2 доказал Ю.В. Матиясевич, а базу для доказательства заложила группа американских математиков Р.Робинсон, Х.Путнам, Дж. Робинсон, М.Дэвис. Они свели задачу к доказательству диофантовости отношения $y = x^u$ и еще к более частному случаю. А Ю.В. Матиясевич нашел конструкцию построения искомого полинома по свойствам перечислимомго множества при помощи последовательности чисел Фибоначи.
Раздел 2. Построение доказательства (?) $\mathbb{NP} \ne \mathbb{P}$ через диофантову неразрешимость.
Идея доказательства
Фактически, доказательство неразрешимости диофантовых уравнений опиралось на канторову процедуру диагонализации - пусть и неявно сделанную для $B$ ($B$ является дополнением к перечислимому множеству $A$). И что интересно - диофантово уравнение «напрашивается» в качестве задачи из класса $\mathbb{NP}$ в силу своей полиномиальности по времени проверки для данных переменных. И при этом диофантово уравнение может выразить свойства даже «хитрого» (и не полиномиального) алгоритма благодаря Теорема 10.1.2.
То есть - возникает идея построить алгоритм для диагонализации полиномиальных алгоритмов (построить «антиполиномиальный алгоритм» - или короче $A_a$) и таким образом доказать $\mathbb{NP} \ne \mathbb{P}$ на примере соответствующего данному $A_a$ диофантового уравнения (обозначим его $p(x, y_1, y_2, \ldots , y_n) = 0$). В некотором смысле мы хотим повторить идею доказательства неразрешимости диофантовых уравнений - путь и далеко не буквально.
Три технических решения
Нам надо решить три технических вопроса:
Вопрос 1. Обеспечить, чтобы решения уравнения $p(x, y_1, y_2, \ldots , y_n) = 0$ были и решениями для задачи из $\mathbb{NP}$ с учетом ограничения $(|y _1|+|y_2|+ \ldots +|y_n| ) < |x|^c$ (см. Определение 5.). Ведь искомые для данного $x$ значения $y_1, y_2, \ldots , y_n $ составляют «сертификат» (решающий уравнение при данном $x$), но могут быть очень большими, выходящими за рамки заданного ограничения.
Вопрос 2. Отличить полиномиальные функции от прочих при их диагонализации.
Вопрос 3. Обеспечить уникальность всех «сертификатов» нашей задачи. Ведь процедура диагонализации должна охватить каждый полиномиальный алгоритм, но наше уравнение $p(x, y_1, y_2, \ldots , y_n) = 0$ имеет дело не с номерами алгоритмов, а с их значениями (см. Теорема 10.1.2. и комментарий за ней). А значения у разных алгоритмов могут быть одинаковыми - в отличие от их номеров.
Решения для поставленных технических вопросов следующие:
1. Достаточно в нашу задачу включить рассмотрение произвольно больших представлений данного полинома - а представление может иметь любой размер. Например, вместо полнима $x^2+y^2-z^2$ записать $x^2+y^2-z^2+0+\ldots +0$ - где операция добавления нуля стоит сколько угодно раз. И если есть какие-то огромные значения x, y, z при которых полином равен 0, то найдется и столь большое представление данного полинома, что сумма десятичных разрядов всех этих значений будет меньше длины данного представления. И условие на полиномиальную ограниченность проверяемого сертификата будет исполнена. Поэтому зададим просто еще один параметр S, который будет задавать размер нашего представления для полинома $p(x, y_1, y_2, \ldots , y_n)$ и обозначим представление с дополнительным размером S так:
$p_S(x, y_1, y_2, \ldots , y_n)$
Тогда ограничение на решения приобретет вид:
$(|y _1|+|y_2|+ \ldots +|y_n| ) < (|x|^{c_1} + |S|^{c_2})$
То есть, ограничения на размер сертификата в задачах из класса $\mathbb{NP} \ne \mathbb{P}$ всегда могут быть как угодно расширены. Принципиальным является факт наличия ограничения, что исключает возможность вечного поиска решения тогда, когда его нет. Но нас случай отсутствия корней не интересует, потому что процедуру диагонализации мы проведем при помощи явного задания значений и работать будем там, где корни у $p(x, y_1, y_2, \ldots , y_n)$ есть.
2. Для каждого алгоритма зададим множество пар вида: $(A, \operatorname{pp})$. Где $A$ - номер самого алгоритма (в качестве номера может выступать текст этого алгоритма), а $\operatorname{pp}$ - номер произвольного полинома от одной переменной. Этот произвольный полином будет ограничивать время работы $A$ и позволит нам понять - является ли $A$ полиномиальным в пределах $\operatorname{pp}$. Если алгоритм $A$ является полиномиальным, то найдется и соответствующий ему $\operatorname{pp}_A$ и это будет правильной парой, задающей номер данному алгоритму. А номер для пары взаимно-однозначно задает, например, канторовская нумерация. Не будем тут углубляться в технические детали, достаточно знать, что все операции между канторовым номером и членами пары полиномиальны по времени выполнения. Обозначим:
$c(x, y)$ - номер канторовой пары;
$A_{pp}$ - номер разбираемой в п.2 канторовой пары $(A, \operatorname{pp})$;
$l(n)$ - левый член пары с номером $n$;
$r(n)$ -правый член пары с номером $n$.
Случай, когда вместо $A$ у нас есть какой-то «нелепый» номер даже не-алгоритма, тоже рабочий для нашего «антиполиномиального алгоритм» $A_a$. В этом случае $A_a$ выдаст такое же значение, как и в случае неполучения результата от работы заданного ему алгоритма $A$ за время, посчитанное при помощи $\operatorname{pp}(x)$. Детали будут в п.3.
Таким образом, вместо одной диагонали, мы задаем целый «лес» диагоналей, «пересекающий» каждый алгоритм по всевозможным его сочетаниям с полиномами-ограничителями. Важно, что номера любых таких «пересечений» для разных алгоритмов всегда отличается между собой.
3. Для заданного номера $A_{pp}$ наш «антиполиномиальный алгоритм» $A_a(A_{pp})$ выдаст в качестве своего результата канторовский номер $c(A_{pp}, Y)$, где $Y$:
3-а. Равен 1, если за время $\operatorname{pp}(x)$ получен результат $A(A_{pp})$ и $c(A_{pp}, A(A_{pp})) \ne 1$
3-б. Равен 0, если результат от $A(A_{pp})$ за необходимый срок не удалось получить (включая случай номеров $A_{pp}$, которые не являются номерами для пар алгоритм-полином), либо $c(A_{pp}, A(A_{pp})) = 1$.
Таким образом, мы построили определенный всюду на $x \in \mathbb{N}$ алгоритм $A_a(x)$, каждое значение $n$ которого взаимно-однозначно соответствует аргументу, при котором оно было вычислено. И аргумент этот можно узнать по значению: $x= l(n)$.
Замечание 1. Построенный нами $A_a(x)$ и использованный метод «множественной диагонализации» алгоритмов по полиномам задает такое соответствие между аргументом и значениями, которое является полиномиально неразрешимым. Это в большей степени, чем «обычная» неразрешимость, подходит для задач теории алгоритмов - где угрозой является просто очень (неполиномиально) долгое время работы алгоритма. «Обычная» неразрешимость в логике разбирает менее практичную угрозу вечного вычисления.
Построение контрольной задачи из класса $\mathbb{NP} \ne \mathbb{P}$
На базе построенного нами алгоритма $A_a(x)$ строим соответствующее ему по Теорема 10.1.2. диофантово уравнение: $p(x, y_1, y_2, \ldots , y_n) = 0$
Поскольку в исходном $p(x, y_1, y_2, \ldots , y_n) = 0$ аргумент $x$ соответствуют значениям $A_a(x)$, а нам нужен аргумент $A_a(x)$, то мы можем извлечь аргумент из значения (мы так построили $A_a(x)$, чтобы иметь такую возможность). И перепишем наше диофантово уравнение в новом виде - уже с дополнительным условием:
$x = l(y_{n+1}) \And p(y_{n+1}, y_1, y_2, \ldots , y_n) = 0$
В силу того, что у данного уравнения нет никаких иных корней $y_{n+1}$, кроме значений от $A_a(x)$ и эти значения однозначно связаны с соответствующими им $x$ через $l(\ldots)$, то очевидно, что дополнительное условие никак не добавило новые и не уничтожило первоначальные корни уравнения.
Замечание 2. Конечно, $(\forall x) x \in L$ в смысле Определение 5 - мы так строили наш $A_a$, чтобы он давал уникальное значение для каждого $x$. Но пока мы рассматриваем вопрос о вычислении «сертификата» - ведь в этом состоит Проблема равенства $\mathbb{NP}$ и $\mathbb{P}$. Но если интересно, чтобы не было заведомо $x \in L$, то и этого можно добиться:
Если удастся доказать, что наша задача из класса $\mathbb{NP}$ полиномиально неразрешима, то в качестве слова языка $L$ можно будет рассматривать и пару $(x, y_{n+1})$ - благо $x$ и $y_{n+1}$ полиномиально соразмерны для случаев, когда они вместе с прочими переменными являются корнями уравнения. Поэтому ограничения на время работы проверки, заданные относительно $x$ подойдут и для случая расширения проверяемого слова компонентой $y_{n+1}$. По построению $A_a$ (см. п.3) ясно, что только одна пара $(x, y_{n+1})$ для данного $x$ будет подходящим вариантом для соответствия $x = l(y_{n+1}) \And p(y_{n+1}, y_1, y_2, \ldots , y_n) = 0$. И только одна пара $(x, y_{n+1})$ для данного $x$ - если рассматривать ее как слово - будет словом языка $L$.
Теперь строим соответствующую задачу из класса $\mathbb{NP}$:
$(x \in L) \Longleftrightarrow (\exists y_1 \in \mathbb{N})(\exists y_2 \in \mathbb{N})\ldots (\exists y_{n+1} \in \mathbb{N})$ $[ (|y _1|+|y_2|+ \ldots +|y_{n+1}|) < (|x|^{c_1} + |S|^{c_2}) ]$ $ \And x = l(y_{n+1}) \And p_S(y_{n+1}, y_1, y_2, \ldots , y_n) = 0$
Написано в соответствии с Определение 5. Константы $c_1$, $c_2$ зависят от степени полинома $p$ и скорости (полиномиальной) работы функции $l(y_{n+1})$, разумеется. Про параметр $S$ было сказано в п.1.
Замечание 3. И алгоритм $A_a(x)$, и полином $p(\ldots)$ вполне реальные и могут быть построены явно.
Окончание (доказательство) - в следующем сообщении.

[dmitgu]

Доказательство $\mathbb{NP} \ne \mathbb{P}$
(Окончание предыдущего сообщения)
Теперь допустим, что имеется полиномиальный алгоритм $A(x)$, решающий построенную нами задачу из класса $\mathbb{NP}$. Для нашей задачи это значит, что при любом заданном $x$ найдется достаточно большое $S$, при котором алгоритм $A(x)$ даст результат (сертификат) в виде набора значений для переменных $y_1, y_2, \ldots , y_{n+1}$, которые вместе с $x$ решают уравнение $p(y_{n+1}, y_1, y_2, \ldots , y_n) = 0$ и при этом верно $x = l(y_{n+1})$.
Однако, имея такой алгоритм $A(x)$ мы легко строим из него алгоритм $\bar{A}(x)$, который возвращает правильное значение для $y_{n+1}$ при данном $x$. И этот алгоритм - тоже полиномиальный. То есть, имеется ограничивающий время его работы полином $\operatorname{pp}(x)$, и имеется канторовский номер $\bar{A}_{pp}$ соответствующей пары $(\bar{A}, \operatorname{pp})$. Тогда (продолжим сквозную нумерацию пунктов Раздела 2):
4. Рассчитаем $N_1 = \bar{A}(\bar{A}_{pp})$
5. Рассчитаем $N_2 = A_a(\bar{A}_{pp})$
6. В силу построения $A_a$ в п.3 имеем: $N_1 \ne N_2$
7. В составе формулы нашей задачи имеется условие $x=l(y_{n+1})$, при подстановки в которое $\bar{A}_{pp}$ на место $x$ и $N_1$ на место $y_{n+1}$ получим:
$\bar{A}_{pp} = l(N_1)$
7-а. В силу того, что для любого $x$ алгоритм $\bar{A}_{pp}(x)$ выдает такое значение для $y_{n+1}$, которое является частью правильного «сертификата», то равенство из п.7 - истинное.
8. По построению $p(y_{n+1}, y_1, y_2, \ldots , y_n) = 0$ каждый $y_{n+1}$, являющийся корнем данного уравнения (в «комплекте» с некоторыми существующими $ y_1, y_2, \ldots , y_n$) является значением $A_a(x)$ для некоторого $x$. В частности, имеется $M_1$, такой что:
$N_1 = A_a(M_1)$
9. По построению $A_a(x)$ имеем: $M_1 = l(A_a(M_1)) = l(N_1)$. В частности:
9-а. $M_1 = l(N_1)$
10. Применим к обеим частям равенства п. 9-а алгоритм $A_a$ и получим в соответствии с п. 8:
$N_1 = A_a(l(N_1))$
11. Сделаем подстановку в правой части п.10 в соответствии с п. 7:
$N_1 = A_a(\bar{A}_{pp})$
12. Заменим правую часть равенства п. 11 в соответствии с п.5:
$N_1 = N_2$
13. Пп. 12 и 6 противоречат друг другу. Поэтому предположение о наличии разрешающего нашу задачу за полиномиальное время алгоритма $A(x)$ ошибочно.
Теорема доказана.
Замечание 4. Приведенное доказательство является конструктивным. То есть в принципе можно построить алгоритм $A_a$ и соответствующее ему диофантово уравнение $p(x, y_1, y_2, \ldots , y_n) = 0$ в явном виде (см. Замечание 3.) И для каждого предполагаемого полиномиального «решения» данного уравнения можно провести в явном виде процесс его опровержения для некоторых корней (тоже поддающихся расчету), который проведен в доказательстве. Поэтому, если построение верное, то в некоторой степени есть гарантия от тонких труднонаходимых ошибок, которыми опасны не конструктивные доказательства.
Замечание 5. Диофантовы уравнения полиномиально неразрешимы (в дополнение к их «обычной» неразрешимости), если рассматривать их как задачу из NP (см. об этом Замечание 2.).

[rubtsov_anton]

Здравствуйте, Дмитрий.
Ну что можно сказать, те же грабли, только в профиль.
Все претензии к доказательству относятся к двум абзацам:
Определение NP-полного языка и формулировка равенства NP и P.

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

Если вы хотите сформулировать равенство NP и P в терминологии языков, то вам нужно было бы записать следующее утверждение:
$\forall L |[\exists R_{np} | \forall x \in L : \exists y | (|y|<|x|^c \& R_{np}(y,x))] : [\exists R_p | \forall x \in L : R_p(x)]$, где $R_{np}$ и $R_p$ - полиномиально вычислимые предикаты.

Вы же опровергаете утверждение:
$\exists F(R_{np}(y,x),x) | \forall R_{np} \forall x : R_{np}(F(R_{np},x),x)$, где F _ полиномиально вычислимая функция.

Пожалуйста, потратьте время и строго докажите эквивалентность этих утверждений.

[dmitgu]

rubtsov_anton в сообщении #873161 писал(а):

Вы же опровергаете утверждение:
$\exists F(R_{np}(y,x),x) | \forall R_{np} \forall x : R_{np}(F(R_{np},x),x)$, где F _ полиномиально вычислимая функция.
Пожалуйста, потратьте время и строго докажите эквивалентность этих утверждений.

Добрый день, Антон. Помогите мне понять переход от моей формулы:
$(x \in L) \Longleftrightarrow $ $ (\exists y_1 \in \mathbb{N})(\exists y_2 \in \mathbb{N})\ldots (\exists y_{n+1} \in \mathbb{N})$ $[ (|y _1|+|y_2|+ \ldots +|y_{n+1}|) < (|x|^{c_1} + |S|^{c_2}) ]$ $ \And x = l(y_{n+1}) $ $ \And p_S(y_{n+1}, y_1, y_2, \ldots , y_n) = 0$
к приведенной Вами.

Кстати, в доказательстве про эту формулу есть ошибка - я вчера понял, но хотел ещё подумать. В приведенной формуле ограничение зависит от $S$, поэтому и решение должно от него зависеть. И для достаточно большой $S$ решение задачи (если бы оно было) для фиксированного $x$ действительно совпадет с $A_a(x)$, но нас-то интересует не фиксированный $x$, а номер соответствующей канторовской пары (алгоритм решения-и-ограничивающий полином). А пара у нас при построении $A_a$ от $S$ не зависит, и при подстановке текущего $S$ в $\bar{A}_{pp}(x, S)$ и в полином $pp(x, S)$ - пара может оказаться слишком большой для данного $S$ - когда $\bar{A}_{pp}(x, S)$ еще не совпадет с $A_a(x)$. Мы опять можем увеличить $S$, но и соответствующая пара может снова "уползти за горизонт" - то есть $x$ изменится. Тут $x$ не фиксированный - он передвигается при каждой "итерации". Тут интересно подумать над этой последовательностью :) Но вообще явная ошибка - я "зевнул" один аргумент. Переел теории алгоритмов и потребуется время для восстановления ясности мышления.

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

[rubtsov_anton]

Моя формула формализует вашу фразу:

Цитата:

вопрос состоит в поиске алгоритма, на вход которому подается текст соответствующего алгоритма $R(x,\, y)$, константа $c$, проверяемое слово $x$. А на выходе через полиномиальное время работы (то есть меньшее, чем $|x|^{C_1} + C_2$, где $C_1$ и $C_2$ некоторые константы) в качестве результата получается сертификат $y$ принадлежности $x$ к языку данной массовой задачи $L$, либо признак отсутствия такого сертификата (что означает тогда $x \notin L$).

Если эта формула не описывает выше понимание равенства P и NP, то напишите конкретное утверждение, которое вы опровергаете, и покажите, как оно связано с приведенным мной определением их равенства.

[dmitgu]

rubtsov_anton в сообщении #873180 писал(а):

Моя формула формализует вашу фразу:

Цитата:

вопрос состоит в поиске алгоритма, на вход которому подается текст соответствующего алгоритма $R(x,\, y)$, константа $c$, проверяемое слово $x$. А на выходе через полиномиальное время работы (то есть меньшее, чем $|x|^{C_1} + C_2$, где $C_1$ и $C_2$ некоторые константы) в качестве результата получается сертификат $y$ принадлежности $x$ к языку данной массовой задачи $L$, либо признак отсутствия такого сертификата (что означает тогда $x \notin L$).

Если эта формула не описывает выше понимание равенства P и NP, то напишите конкретное утверждение, которое вы опровергаете, и покажите, как оно связано с приведенным мной определением их равенства.

Отлично - я Вас понял (вроде). Но в Вашей формулировке написано $\exists R(x)$ - а откуда оно возьмется? Разве не необходим алгоритм, который бы мог по задаче из NP построить соответствующее решение? Я понимаю, что переходы междду NP полными задачами полиномиальны, но строго говоря - алгоритм должен быть. Разве нет?

[rubtsov_anton]

Нет, никакого алгоритма порождающего $R_p$ из $R_{np}$ не постулируется. Его может и не существовать, это никак не влияет на равенство классов.

[dmitgu]

rubtsov_anton в сообщении #873188 писал(а):

Нет, никакого алгоритма порождающего $R_p$ из $R_{np}$ не постулируется. Его может и не существовать, это никак не влияет на равенство классов.

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

[rubtsov_anton]

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

Если решение задачи можно быстро проверить, то для соответствующего языка существует предикат $R_{np}$.
Если задачу можно быстро решить, то для соответствующего языка существует предикат $R_{p}$.
Чему соответствует "угадывание" решения?
При чем тут "практические задачи"?

[dmitgu]

rubtsov_anton в сообщении #873206 писал(а):

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

Если решение задачи можно быстро проверить, то для соответствующего языка существует предикат $R_{np}$.
Если задачу можно быстро решить, то для соответствующего языка существует предикат $R_{p}$.
Чему соответствует "угадывание" решения?
При чем тут "практические задачи"?

"Угадывание" в данном случае - это возможность получить ответ с помощьюю полиномиального алгоритма, не зная сертификат. А чтобы получить ответ нужно иметь конкретный алгоритм. Вот почему я считаю, что должен быть алгоритм, который по тексту задачи $NP$ должен давать полиномиаально быстрый ответ для нужного $x$. Ну, или другой подход - находить по тексту задачи из $NP$ полиномиальный алгоритм $R_p$. Притом находить этот ответ должен за полиномиальное - относиительно размера алгоритма $R(y, x)$ - время. Иначе получить решающий алгоритм для произвольной задачи $NP$ - было бы неполиномиально трудной задачей без полиномиального решения. А значок "существует" $\exists R_p(x)$ затушевывает это требование. Мы же и про ответ $x \in L$ (или $x \not\in L$) можем сказать "существует", но интересно ведь - какой.

[rubtsov_anton]

В таком случае "угадывание" - это то же самое, что и решение. То есть наличие предиката $R_p$. Зачем придумывать новую сущность?

Алгоритм получения ответа для каждой конкретной задачи, разумеется должен быть. Это и есть предикат $R_p$.
При чем тут алгоритмы которые "читают задачу NP"? Мы, вроде договорились говорить о языках, а не задачах.
Чему эти алгоритмы соответствуют в терминологии языков? Функциям над пространством предикатов, как я и писал?

[dmitgu]

rubtsov_anton в сообщении #873263 писал(а):

В таком случае "угадывание" - это то же самое, что и решение. То есть наличие предиката $R_p$. Зачем придумывать новую сущность?

Алгоритм получения ответа для каждой конкретной задачи, разумеется должен быть. Это и есть предикат $R_p$.
При чем тут алгоритмы которые "читают задачу NP"? Мы, вроде договорились говорить о языках, а не задачах.
Чему эти алгоритмы соответствуют в терминологии языков? Функциям над пространством предикатов, как я и писал?

Нет, просто я привожу аргументы в пользу
$R(\widehat{L(x, y)}, x)$ (где $\widehat{L(x, y)}$ - текст алгоритма $L(x, y)$) перед $\forall L(x, y) \exists R(x)$. Вот в случае $R(\widehat{L(x, y)}, x)$ алгоритм $R$ "читает текст" алгоритма $L(x, y)$ и выдает конкретный ответ - результат функции. Вы же и сами согласны, что "Алгоритм получения ответа для каждой конкретной задачи, разумеется должен быть", но значок "существует" не означает, что у Вас есть конкретный алгоритм, куда Вы можете подставить $x$ и даже ничего не говорит, за какое время Вы можете получить этот алгоритм.