dmitgu (dmitgu) wrote,
dmitgu
dmitgu
Category:

Док-во NP≠P через диофантову неразрешимость (часть 2 из 4)

Продолжение. Начало тут: Часть 1 из 4, Данная часть: Часть 2 из 4, Остальные части: Часть 3 из 4, Часть 4 из 4..
Сохраняю тут мое сообщение с dxdy.ru, и там есть егоокончание
Раздел 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)$.
(продолжение - в следующей записи)
Tags: NP≠P дискуссии, ЖЖвЖЖ математика
Subscribe

  • Post a new comment

    Error

    switch
    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
    Help
  • 0 comments