Изменения
→Теорема
'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным, ни [[NP-полнота|NP-полным]].
== Доказательство Иллюстрация ==
# <tex>L \in \mathrm{NP}</tex> (для этого достаточно, чтобы выполнялось <tex>A \in \mathrm{P}</tex>);
Если выполнены все три свойства, то <tex>L \in \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC})</tex>.
Пусть <tex>M_1, \ldots, M_n, \ldots</tex> — все машины Тьюринга из <tex>\tilde{\mathrm{P}}</tex>(возможно, причём <tex>T(M_i(x)с повторениями) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>. Пусть <tex>f_1, \ldots, f_nрасположенные в таком порядке, \ldots</tex> — аналогичное множество полиномиальных функций: чтобы <tex>T(f_i(M_i, x)) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>.
Для простоты будем считать, что <tex>|\Sigma| === Построение 2</tex>. Построим такую ''неубывающую'' функцию <tex>g\in \tilde{\mathrm{P}}</tex> , что при <tex>A ===\{x \in \Sigma^*: g(|x|) \equiv 0 \pmod{2} \}</tex> для <tex>L</tex> выполняются три перечисленных свойства.
Положим <tex>g(0) = g(1) = 1</tex>. Для <tex>n \ge 1</tex>:построим <tex>g(n + 1)</tex> рекурсивно — с помощью <tex>g(0), g(1), \ldots, g(n)</tex>.
* Если <tex>(\log_2 n)^{g(n)} \ge n</tex>, то <tex>g(n+1) := g(n)</tex>. Иначе выполняем один из следующих пунктов.
for <tex>x</tex> : <tex>|x| \le \log_2 n</tex>
if <tex>M_i(x)</tex> and (<tex>[g(|x|) \% equiv 1 \pmod{2 = 1}</tex> or <tex>x \not \in \mathrm{SAT})]</tex>
<tex>g(n+1) := g(n)+1</tex>
return
if <tex>! M_i(x)</tex> and (<tex>[g(|x|) \% equiv 0 \pmod{2 = 0}</tex> and <tex>x \in \mathrm{SAT})]</tex>
<tex>g(n+1) := g(n)+1</tex>
return
<tex>g(n+1) := g(n)</tex>
* Пусть вычисленное значение <tex>g(n) = 2i 2 i - 1</tex>. Определим <tex>g(n+ 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)|) \% equiv 1 \pmod{2 = 1}</tex> or <tex>f_i(x) \not \in \mathrm{SAT})]</tex> <tex>g(n+1) := g(n)+1</tex>, return if <tex>x \not \in \mathrm{SAT}</tex> and (<tex>[g(|f_i(x)|) \% equiv 0 \pmod{2 = 0}</tex> and <tex>f_i(x) \in \mathrm{SAT})]</tex> <tex>g(n+1) := g(n)+1</tex>, return
<tex>g(n+1) := g(n)</tex>
* Пусть <tex>g(n)</tex> не имеет предела при <tex>n \to \infty</tex>. Значит, для любой <tex>M_i</tex> в <tex>L</tex> существует элемент, на котором <tex>M_i</tex> «ошибается»; аналогично, для любой полиномиальной функции <tex>f_i</tex> существует элемент, на котором <tex>f_i</tex> неверно сводит <tex>\mathrm{SAT}</tex> к <tex>L</tex>. Оба свойства выполнены.
* Пусть <tex>\lim\limits_{n \to \infty} g(n) = 2i</tex>. Значит, в нашем множестве существует такая машина Тьюринга <tex>M_i</tex>, распознающая <tex>L</tex>, что <tex>\forall x \Rightarrow M_i(x) = [g(|x|) \% equiv 0 \pmod{2 = 0 } \wedge x \in \mathrm{SAT})]</tex>. С одной стороны, <tex>M_i</tex> работает за полином, и <tex>L \in \mathrm{P}</tex>. С другой стороны, по определению <tex>A</tex>, <tex>L</tex> различается с <tex>\mathrm{SAT}</tex> в конечном числе элементов, значит <tex>\mathrm{SAT} \le L</tex>. Получено противоречие с предположением <tex>\mathrm{P} \neq \mathrm{NP}</tex>.
* Пусть <tex>\lim\limits_{n \to \infty} g(n) = 2i + 1</tex>. Тогда в нашем множестве полиномиальных функций существует <tex>f_i : \forall x \Rightarrow [x \in SAT] = [g(|f_i(x)|) \% equiv 0 \pmod{2 = 0 } \wedge f_i(x) \in \mathrm{SAT}]</tex>. С одной стороны, <tex>\mathrm{SAT} \le L</tex> с помощью <tex>f_i</tex>. С другой стороны, из определения <tex>A</tex> выходит, что язык <tex>L</tex> конечен, значит <tex>L \in \mathrm{P}</tex>. Снова получено противоречие с предположением.
Таким образом, при верности предположения <tex>\mathrm{P} \neq \mathrm{NP}</tex> второе и третье свойства <tex>L</tex> выполнены.
=== Время работы алгоритма ===
Проверим первое свойство — выполнение первого свойства языка <tex>L</tex>. Для этого достаточно установить полиномиальность языка <tex>A</tex>. Пусть Покажем, что <tex>T^(g, n)</tex> отличается от <tex>T(g, n - 1)</tex> не более, чем на неубывающий полином <tex>p(n)</tex> — время вычисления . Из этого будет следовать полиномиальность <tex>g</tex>: <tex>T(g, n) \le p(n) + p(n - 1) + \ldots + p(1) \le n p(n) \in poly(n)</tex>.
Заметим, что <tex>g(n) \le n</tex> по построению для <tex>n \ge 1</tex>.
<ul><li>для случая <tex>T_3g(n) = 2 i</tex>:<br/><tex>\parbox{0px}{\begin{align*}T(n) & \le c_3 n (2^{\log_2 n} (T(M_i, x) + T(g, |x|) + T(x \in \log_2 mathrm{SAT})) \le \\ & \le k_1 n (|x|^i + T(g, |x|) + 2^{|x|}|x|) \le \\ & \le k_1 n ((\log_2 n)^{g(n)} + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n)\le \\ & \le k_1 (n^2 + n^2 \log_2 n + n T(g, \log_2 n)) \le \\ & \le k_1 (2n^3 + n T(g, \log_2 n));\end{align*}}</tex></li>
<li>для случая <tex>T_3g(n) = 2 i - 1</tex>:<br/><tex>\parbox{0px}{\begin{align*}T(n) & \le 2^{\log_2 n} (T(x \in \mathrm{SAT}) + T(g, |f_i(x)|) + T(f_i(x) \in \mathrm{SAT})) \le \\ & \le k_2 n (2^{\log_2 n} \log_2 n + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n) \le c_3 \\ & \le k_2 (2n^2 \log_2 n + n T(g, \log_2 n)) \le \\ & \le k_2 (2n^3 + n T(g(, \log_2 n)).\end{align*}}</tex></li></ul>
Вычислить <tex>T_3(\log_2 n) ^{g(n)}</tex> можно за<tex>k_3 \le c_3 log_2 g(n) |(2n\log_2 n)^3 + {g(n T)}|^2 \le k_3 (g(\n) |log_2 n|))^2 log_2 n \le k_3 n^3</tex>.
Таким образом,
<tex>T(g, n) \le T(g, n-1) + k (n^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 4 + k_1 k n^5 3 + k_2 k n c (\log_2 n)^7 4 \le c n^74</tex>.
Тогда, в силу <tex>T^(g(, 1) = d \le c \cdot 1^74</tex> и неравенства строкой выше, по индукции легко доказать, что <tex>T^(g(, n)</tex> ограничено сверху <tex>c n^74</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.}}
== Источник ==