June 3rd, 2014

ёжик

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

Начало - Часть 1 из 4, Остальные части: Часть 2 из 4, Часть 3 из 4, Часть 4 из 4.
Сохраню тут мое сообщение с dxdy.ru, и там есть его окончание.
Раздел 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 Нумерация алгоритмов и вычислимых функций, Подраздел «Вычислимые функции».
Collapse )
ёжик

Док-во 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$). В некотором смысле мы хотим повторить идею доказательства неразрешимости диофантовых уравнений - путь и далеко не буквально.
Три технических решения
Collapse )
ёжик

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

Продолжение. Начало тут: Часть 1 из 4, Предыдущая часть: Часть 2 из 4, Данная часть: Часть 3 из 4, Окончание: Часть 4 из 4.
Сохраняю тут мое сообщение с dxdy.ru, и там есть его окончание.
Замечание 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$
Collapse )
ёжик

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

Окончание. Начало тут: Часть 1 из 4, Предыдущие части: Часть 2 из 4, Часть 3 из 4, Данная часть: Часть 4 из 4.
Сохраняю тут мое сообщение с dxdy.ru, и там есть его окончание.
Доказательство $\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})$
Collapse )