Изменения

Перейти к: навигация, поиск

Теорема Ладнера

133 байта убрано, 12:58, 2 июня 2012
Нет описания правки
'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным и , ни [[NP-полнота|NP-полным]].
== Доказательство ==
Предположим, что <tex>\mathrm{P} \neq \mathrm{NP}</tex>. Из этого следует, что никакой <tex>\mathrm{NP}</tex>-полный язык (например, <tex>\mathrm{SAT}</tex>) нельзя свести по Карпу к полиномиальному. Будем искать язык <tex>A</tex>, удовлетворяющий следующим условиям:
# <tex>A \in \mathrm{P}</tex> (что влечёт за собой <tex>\mathrm{SAT} \cap A \in \mathrm{NP}</tex>);
=== Построение <tex>g</tex> ===
Определим <tex>g</tex> рекурсивно. Установим Положим <tex>g(0) = g(1) = 1</tex>. Для <tex>n \ge 1</tex>:
* Если Для <tex>log_2^{g(n)} n \ge n1</tex>, <tex>g(n+1) := g(n)</tex>.
* Если <tex>(\log_2 n)^{g(n)} \ge n</tex>, <tex>g(n+1) := g(n)</tex>. Иначе <tex> n > (\log_2n)^{g(n)} n \ge \log_2 n</tex>; значения <tex>g(m)</tex> для <tex>m \le \log_2 n</tex> уже известны.
* <tex>g(n) = 2i</tex>.
for <tex>x</tex>: <tex>|x| \le \log_2 n</tex>
if <tex>M_i(x)</tex> and (<tex>g(|x|) \% 2 = 1</tex> or <tex>x \not \in \mathrm{SAT})</tex>
<tex>g(n+1) := g(n)+1</tex>, return else if <tex>! M_i(x)</tex> and (<tex>g(|x|) \% 2 = 0</tex> and <tex>x \in \mathrm{SAT})</tex> <tex>g(n+1) := g(n)+1</tex>, return else <tex>g(n+1) := g(n)</tex>
* <tex>g(n) = 2i + 1</tex>.
for <tex>x</tex>: <tex>|x| \le \log_2 n, |f_i(x)| \le \log_2 n</tex>
if <tex>x \in \mathrm{SAT}</tex> and (<tex>g(|f_i(x)|) \% 2 = 1</tex> or <tex>f_i(x) \not \in \mathrm{SAT})</tex>
<tex>g(n+1) := g(n)+1</tex>, return else if <tex>x \not \in \mathrm{SAT}</tex> and (<tex>g(|f_i(x)|) \% 2 = 0</tex> and <tex>f_i(x) \in \mathrm{SAT})</tex> <tex>g(n+1) := g(n)+1</tex>, return else <tex>g(n+1) := g(n)</tex> Утверждается, что для такой функции <tex>g</tex> язык <tex>A = \{x \in \Sigma^*: g(|x|) \% 2 = 0\}</tex> является искомым.
=== Корректность алгоритма ===
* проверка неравенства:
<tex>T_1(n) \le g(n) T_*(\log_2^{g(n)} n, \log_2^{g(n)} n)</tex>
<tex>T_1(n) \le c_1 g(n) (\log_2 (\log_2^{g(n)} n))^2</tex>
<tex>T_1(n) \le c_1 g^3(n) \log_2^2 \log_2 n</tex>
<tex>T_1(n) \le c_1 n^3 \log_2^2 \log_2 n</tex>
<tex>T_1(n) \le c_1 n^5</tex>,
* <tex>g(n) = 2i</tex>:
<tex>T_2(n) \le 2^{\log_2 n} (T(M_i(x)) + T(g(|x|)) + T(x \in \mathrm{SAT}))</tex>
<tex>T_2(n) \le c_2 n (|x|^i + T^g(|x|) + 2^{|x|}|x|)</tex>
<tex>T_2(n) \le c_2 n (\log_2^{i} n + T^g(|x|) + 2^{\log_2 n} \log_2 n)</tex>
<tex>T_2(n) \le c_2 n (\log_2^{g(n)} n + T^g(\log_2 n) + n \log_2 n)</tex>
<tex>T_2(n) \le c_2 (n^2 + n^2 \log_2 n + n T^g(\log_2 n))</tex> // а не n^3 ли здесь в первом слагаемом?
<tex>T_2(n) \le c_2 (2n^3 + n T^g(\log_2 n))</tex>
* <tex>g(n) = 2i + 1</tex>:
<tex>T_3(n) \le 2^{\log_2 n} (T(x \in \mathrm{SAT}) + T^g(|f_i(x)|) + T(f_i(x) \in \mathrm{SAT}))</tex>
<tex>T_3(n) \le c_3 n (2^{\log_2 n} \log_2 n + T^g(\log_2 n) + 2^{\log_2 n} \log_2 n)</tex>
<tex>T_3(n) \le c_3 (2n^2 \log_2 n + n T^g(\log_2 n))</tex>
<tex>T_3(n) \le c_3 (2n^3 + n T^g(\log_2 n))</tex>
Таким образом,
<tex>T^g(n) \le T^g(n-1) + c_1 n^5 + c_2 (2n^3 + n T^g(\log_2 n)) + c_3 (2n^3 + n T^g(\log_2 n))</tex>
<tex>T^g(n) \le T^g(n-1) + k_1 n^5 + k_2 n T^g(\log_2 n)</tex>
Пусть <tex>T^g(1) = const = d</tex>. Существует константа <tex>c \ge d</tex>, для которой при любом <tex>n</tex> верно
<tex>c (n-1)^7 + k_1 n^5 + k_2 n c (\log_2 n)^7 \le c n^7</tex>
Тогда, в силу <tex>T^g(1) = d \le c 1^7</tex> и неравенства выше, по индукции легко доказать, что <tex>T^g(n)</tex> ограничено сверху <tex>c n^7</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.

Навигация