Изменения

'''Теорема Ладнера''' (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>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> уже известны.

for <tex>x</tex>: <tex>|x| \le \log_2 n</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>

for <tex>x</tex>: <tex>|x| \le \log_2 n, |f_i(x)| \le \log_2 n</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_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 (\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>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>c (n-1)^7 + k_1 n^5 + k_2 n c (\log_2 n)^7 \le c n^7</tex>