dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Док-во 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$
Поскольку в исходном $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)$ вполне реальные и могут быть построены явно.
(окончание - в следующей записи)
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