dmitgu (dmitgu) wrote,
dmitgu
dmitgu
Categories:

Док-во 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 Нумерация алгоритмов и вычислимых функций, Подраздел «Вычислимые функции».
Определение 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$ и еще к более частному случаю. А Ю.В. Матиясевич нашел конструкцию построения искомого полинома по свойствам перечислимомго множества при помощи последовательности чисел Фибоначи.
(продолжение - в следующей записи)
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