dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

Док-во 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})$
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.).
Tags: NP≠P дискуссии, ЖЖвЖЖ математика
Subscribe

  • Post a new comment

    Error

    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.
  • 4 comments