'''Теорема Ладнера''' (Ladner's Theorem) утверждает,что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык <tex>L</tex>,принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся полиномиальным и [[NP-полнота|NP-полным]].
==ИллюстрацияДоказательство ==
Определим язык <tex>A</tex> как множество таких формул <tex>\alpha</tex>Предположим,что <tex>\left\lfloor \fracmathrm{1}{2P}\log_neq \mathrm{10NP}^*|\alpha|\right\rfloor</tex> чётно.Иными словамиИз этого следует, что <tex>A</tex> — это язык формул с длинами, лежащими в промежутках <tex>\left[1,10^{10}\right),\left[\underbrace{10^{10^{\cdot^{\cdot^mathrm{10}}}NP}}_4,\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_6\right), \ldots</tex>Далее будем обозначать -полный язык (например, <tex>\underbrace{a^{a^{\cdot^{\cdot^mathrm{aSAT}}}}}_n</tex>как ) нельзя свести по Карпу к полиномиальному. Будем искать язык <tex>^{n}aA</tex>., удовлетворяющий следующим условиям:
Рассмотрим язык [[SAT]] всех удовлетворимых формул. Логично предположить, что как в # <tex>A</tex>,так и в <tex>\bar{A}</tex> лежит бесконечное множество элементов из <tex>in \mathrm{SATP}</tex>,не распознаваемых (что влечёт за полиномиальное время, поэтому собой <tex>\mathrm{SAT} \cap A \not\in \mathrm{PNP}</tex>.);Из # <tex>\mathrm{SAT} \cap A \not \in \mathrm{P}</tex> и ;# <tex>\mathrm{SAT} \in not \mathrm{NP}</tex> следует, что <tex>le \mathrm{SAT} \cap A \in \mathrm{NP}</tex>.
Осталось показатьЕсли такой язык существует, что то <tex>L = \mathrm{SAT} \cap A</tex> не является искомым примером множестваиз <tex>\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(x)) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>. Тогда из NP-полноты следует Для простоты будем считать, что <tex>|\Sigma| = 2</tex>. Построим такую неубывающую функцию <tex>g \in \tilde{\mathrm{P}}</tex>, что существует полиномиальная функция для <tex>A = \{x \in \Sigma^*: g(|x|) \% 2 = 0\}</tex> выполняются три названных свойства. === Построение <tex>g</tex> === Определим <tex>g</tex> рекурсивно. Установим <tex>g(0) = g(1) = 1</tex>. Для <tex>n \ge 1<math/tex>f: * Если <tex>log_2^{g(n)} n \ge n</mathtex>,<tex>g(n+1) := g(n)</tex>. Иначе <tex> n > log_2^{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 if <tex>! M_i(x)</tex> and (<tex>g(|x|) \% 2 = 0</tex> and <tex>x \in \mathrm{SAT} \cap A)</tex> <tex>g(n+1) := g(n)+1</tex>, return <tex>g(n+1) := g(n)</tex>.
Возьмём формулу * <tex>\varphi</tex> длиной <tex>^{4kg(n) = 2i +3}101</tex>. Она не лежит в for <tex>Ax</tex> и, следовательно, в : <tex>|x| \mathrm{SAT} le log_2 n, |f_i(x)| \cap Ale log_2 n</tex>.Функция <tex>f</tex> не может перевести if <tex>x \varphi</tex> в промежуток<tex>in \left[^mathrm{4k+4}10, ^{4k+6SAT}10\right)</tex> или дальше, так как размервыхода полиномиальной функции не может быть экспоненциально больше длинывхода. Значит, and (<tex>g(|f_i(x)|) \varphi% 2 = 1</tex> отображается в меньший промежуток, нов этом случае размер выхода экспоненциально меньше длины входа. Добавляяк этому то, что проверку на принадлежность or <tex>ff_i(x) \not \varphi)</tex> к<tex>in \mathrm{SAT} \cap A)</tex> можно осуществить за <tex>Og(n+1) := g(2^{poly}n)+1</tex>, return(это следует из её принадлежности классу if <tex>x \not \in \mathrm{NPSAT}</tex>), получаем программу,разрешающую and (<tex>g(|f_i(x)|) \varphi% 2 = 0</tex> за полином. Утверждение о том, что все формулыand <tex>f_i(x) \in \varphi</tex> длиной <tex>^mathrm{4k+3SAT}10)</tex> принадлежат классу <tex>\mathrm{P}g(n+1) := g(n)+1</tex>, скорее всего не верно, и, следовательно, язык return <tex>\mathrm{SAT} \cap Ag(n+1) := g(n)</tex> не является NP-полным.
ЗаметимУтверждается, что это объяснение не для такой функции <tex>g</tex> язык <tex>A = \{x \in \Sigma^*: g(|x|) \% 2 = 0\}</tex> является доказательством!искомым.
==Доказательство= Корректность алгоритма ===Будем искать язык <tex>A</tex>, удовлетворяющий следующим условиям:#<tex>A \in \mathrm{P}</tex> (что влечёт за собой <tex>\mathrm{SAT} \cap A \in \mathrm{NP}</tex>);#<tex>\mathrm{SAT} \cap A \not\in \mathrm{P}</tex>;#<tex>\mathrm{SAT} \not \leqslant \mathrm{SAT} \cap A</tex>.
Если такой язык Проверим выполнение второго и третьего свойств языка <tex>L = \mathrm{SAT} \cap A</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_{n \to +\infty} g(n) = 2i</tex>. Значит, в нашем множестве существуетмашина Тьюринга <tex>M_i</tex>, то распознающая <tex>L </tex>: <tex>\forall x M_i(x) = (g(|x|) \% 2 = 0 \cap x \in \mathrm{SAT} )</tex>. С одной стороны, <tex>M_i</tex> работает за полином, и <tex>L \cap 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_{n \setminus to +\infty} g(n) = 2i + 1</tex>. Тогда в нашем множестве полиномиальных функций существует <tex>f_i</tex>: <tex>\forall x (x \in SAT) = (g(|f_i(x)|) \% 2 = 0 \cap 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>\cup mathrm{P} \neq \mathrm{NPCNP}</tex> второе и третье свойства <tex>L</tex> выполнены. === Время работы алгоритма === Проверим первое свойство — полиномиальность языка <tex>A</tex>. Пусть <tex>T_g(n)</tex> — время вычисления <tex>g(n)</tex>. Заметим, что <tex>g(n) \le n</tex> по построению для <tex>n \ge 1</tex>. Время выполнения шагов составляет: * проверка неравенства: <tex>T_1(n) \le g(n) T_*(log_2^{g(n)} n, log_2^{g(n)} n)</tex>
===Утверждение 1===Можно перечислить (возможно, с повторениями) все языки из <tex>T_1(n) \mathrmle c_1 g(n) (log_2 (log_2^{Pg(n)}n))^2</tex>.
Действительно, рассмотрим последовательность всех программ, упорядоченных по длине:<tex> \tilde{p_0}, \tilde{p_1}, \ldots, \tilde{p_n}, \ldots</tex>Обозначим за <tex>p_i</tex> программу, запускающую <tex>\tilde{p_i}</tex>с таймером <tex>in^i</tex>. Тогда среди <tex>{p_i}</tex> встречаютсятолько программы из <tex>\mathrm{P}</tex>, и для каждой полиномиальной программы<tex>\tilde{p_i}</tex>, работающей за полином <tex>g_iT_1(n)</tex>, существуетномер <tex>j</tex> такой, что <tex>jn\le c_1 g^j > g_i3(n)</tex> для всех натуральных <tex>log_2^2 log_2 n</tex>и <tex>\tilde{p_j}</tex> делает то же самое, что и <tex>\tilde{p_i}</tex>.Таким образом, <tex>p_j</tex> распознает тот же язык, что и <tex>\tilde{p_i}</tex>.
===Утверждение 2===Можно перечислить все функции из <tex>T_1(n) \tilde{\mathrm{P}}le c_1 n^3 log_2^2 log_2 n</tex>.
Аналогично предыдущему доказательству, сначала построим последовательность <tex>T_1(n) \tilde{f_i}</tex>, а затем, добавив таймер <tex>inle c_1 n^i5</tex>, получим последовательность <tex>f_i</tex>.
===Описание способа построения где <tex>A</tex>===Упорядочим все слова по возрастанию длины. Разобьем всё <tex>\Sigma^{*}</tex> на множества<tex>A_i</tex> так, что:T_*<tex>\forall i<j, \forall \alpha \in A_i, \beta \in A_j: |\alpha| < |\beta|</tex> (то есть разбиение происходит по длинамa, причем <tex>A_i</tex> идут «подряд»b),*<tex>\mathrm{SAT} \cap \bigcup_{i=0}^{k} A_{2i}</tex> отличается от — время нахождения произведения чисел <tex>L(p_k)</tex> элементом <tex>x_{2k}</tex> из <tex>\bigcup_{i=0}^{2k} A_i</tex>, *для любого <tex>k</tex> существует <tex>x_{2k+1} \in \bigcup_{i=0}^{2k+1} A_i</tex>, для которого выполняются условия <tex>f_k(x_{2k+1}) \in \bigcup_{i=0}^{2k+1} A_ia</tex> и <tex>[x_{2k+1} \in \mathrm{SAT}] \ne [f_k(x_{2k+1}) \in \mathrm{SAT} \cap \bigcup_{i=0}^{k} A_{2i}]b</tex>.
[[File* <tex>g(n) = 2i</tex>:Ladner.png]]
Если мы сможем построить такие <tex>A_i</tex>, то язык <tex>L = T_2(n) \mathrmle 2^{SATlog_2 n} (T(M_i(x)) + T(g(|x|)) + T(x \cap \bigcup_{i=0}^{\infty} A_{2i}</tex>будет отличаться от любого полиномиального языка, и ни одна полиномиальная функция не будет сводить<tex>in \mathrm{SAT}))</tex> к <tex>L</tex>.
Попытаемся построить такую полиномиальную функцию <tex>f</tex>, что <tex>A_i = T_2(n) \left\{x \mid fle c_2 n (|x|) = ^i\right\}</tex>. Тогда <tex>A=\left\{x \mid f+ T_g(|x|) \equiv 0 (\mathrm{mod}\ + 2) \right\}</tex> и <tex>L=\mathrm^{SAT} \cap A = \left\{\varphi \mid \varphi \in \mathrm{SAT|x|} \land f(|\varphix|) \equiv 0 (\mathrm{mod}\ 2) \right\}</tex>
===Построение <tex>f</tex>===Зададим <tex>fT_2(0n) = f(1) = 0</tex>. Затем рекурсивно определим <tex>f(\le c_2 n)</tex>. Для этого рассмотрим три случая:*<tex>(\log_2 n) ^ {f(n-1)i} \ge n</tex>:*:<tex>f+ T_g(n) = f(n-1)</tex>;*<tex>f(n-1)=2i</tex>:*:если существует <tex>x</tex> такой, что <tex>|x| < \log_2 n</tex> и <tex>p_i(x) \ne [x \in L]</tex>, то <tex>f(n) = f(n-1)+1</tex>, иначе <tex>f(n) = f(n-1)</tex>;*<tex>f(n-1)=2i+1</tex>:*:если существует <tex>x</tex> такой, что <tex>|x| < \2^{log_2 n</tex>,<tex>|f_i(x)| < \} log_2 n</tex> и <tex>[x \in \mathrm{SAT}] \ne [f_i(x) \in L]</tex>, то <tex>f(n) = f(n-1)+1</tex>, иначе <tex>f(n) = f(n-1)</tex>.
Заметим, что вызовы <tex>[T_2(n) \alpha \in L]</tex> делаются для <tex>\alpha</tex>, для которых <tex>fle c_2 n (log_2^{g(n)} n + T_g(log_2 n) + n log_2 n)</tex> уже построена.
Первый случай позволяет сказать, что <tex>fT_2(n)</tex> ограничена <tex>O\leftle c_2 (\log_{\n^2 + n^2 log_2 n} + n\right) = OT_g(\log_2 n)</tex>.Второй «ответственен» за множества <tex>A_i</tex> для чётных <tex>i</tex>, третий — для нечетных.Логарифм в условии <tex>|x| < \log_2 n</tex> необходим для полиномиальности <tex>f(n)</tex>.
===Полиномиальность <tex>f</tex>===Покажем, что <tex>f \in \tilde{\mathrm{P}}</tex>. Для упрощения будем считать, что алфавит <tex>\Sigma=\{0,1T_2(n) \}le c_2 (2n^3 + n T_g(log_2 n))</tex>.
* <tex>Tg(n) = T(n-2i + 1) + a(n)(b_1(n) + b_2(n) + b_3(n) + b_4(n)) + c_1(n) + c_2(n)</tex>, где:*<tex>T(n-1)</tex> идёт на вычисление <tex>f(n-1)</tex>;*<tex>a(n)</tex> — время перебора всех слов <tex>x</tex> таких, что <tex>|x| < \log_2 n</tex>;*<tex>b_1(n)</tex> — время работы <tex>p_i(x)</tex>;*<tex>b_2(n)</tex> — время работы <tex>[x \in \mathrm{SAT}]</tex>;*<tex>b_3(n)</tex> — время работы <tex>[x \in L]</tex>;*<tex>b_4(n)</tex> — время работы <tex>[f_i(x) \in L]</tex>;*<tex>c_1(n)</tex> — время, необходимое для построения программы <tex>p_i</tex>;*<tex>c_2(n)</tex> — время, необходимое для построения функции <tex>f_i</tex>.
<tex>aT_3(n) = O\left(le 2^{\log_2 n}(T(x \rightin \mathrm{SAT}) = O+ T_g(n|f_i(x)|)</tex>, таким образом <tex>a+ T(f_i(nx) \in \mathrm{SAT}))</tex>.
<tex>b_1T_3(n) = O\leftle c_3 n (i(\2^{log_2 n)^i\right) = O\left(f(} log_2 n-1)+ T_g(\log_2 n)+ 2^{f(log_2 n-1)}\right) = O\left(f(log_2 n-1)n\right) = O(n^2)</tex>
<tex>b_2T_3(n) = O \leftle c_3 ( 2n^2^{\log_2 n} \log_2 + n\right) = O\leftT_g(n \log_2 n\right) = O\left(n^2\right)</tex>
<tex>b_3T_3(n) = O \leftle c_3 (22n^{\log_2 n} \log_2 n 3 + \log_2 n\right) = O \leftT_g(n \log_2 n\right) = O\left(n^2\right)</tex>
<tex>b_4(n) = b_3(b_1(n)) = O\left(n^4\right)</tex>Таким образом,
Чтобы построить программу <tex>p_i</tex> достаточно построить <tex>T_g(n) \tilde{p_i}</tex>. Из того, что все <tex>\tilde{p_i}</tex> упорядочены по длине, следует, что длина<tex>\tilde{p_i}</tex> не превосходит <tex>ci</tex> le T_g(константа зависит от языка описания программыn-1).Поэтому для построения i-ой программы достаточно перебрать все <tex>2+ c_1 n^{ci5 +1}-1</tex> слов с длиной не больше <tex>ci</tex>и вывести i-ое, являющееся программой. Такой способ требует <tex>Oc_2 (22n^{ci}i) = O3 + n T_g(2^{\log_2 n} \log_2 n) = O) + c_3 (2n^3 + n^2)</tex> времени.Аналогично можно построить и <tex>f_i</tex>. Из этого следует, что <tex>c_1T_g(log_2 n)</tex> и <tex>c_2(n)</tex> тоже полиномиальны.
Получаем, что <tex>TT_g(n) = T\le T_g(n-1) + poly</tex>. Значит, <tex>T(k_1 n) \le ^5 + k_2 n \cdot poly </tex>. Поэтому <tex>TT_g(log_2 n) \in \tilde{\mathrm{P}}</tex> и <tex>A \in \mathrm{P}</tex>.
Таким образомЕсли выписывать полученные значения <tex>g(n)</tex> на ленте машины Тьюринга в порядке возрастания <tex>n</tex>, <tex>fT_g(log_2 n)</tex> полиномиальна и можно получить за <tex>A \in k_3 (n + log_2 n) \mathrm{P}le 2 k_3 n</tex>.Тогда
===Доказательство выполнения свойств <tex>A</tex>===Предположим, что <tex>\lim_{n \to \infty}fT_g(n) = 2i</tex>. Это значит, что фунция «застряла» в ветке «иначе» случая два,но из этого следует, что <tex>\mathrm{SAT}</tex> не отличается от <tex>Lle T_g(p_in-1)+ k_1 n^5 + 2 k_2 k_3 n^2</tex>. Этовлечёт за собой принадлежность <tex>\mathrm{SAT}</tex> к <tex>\mathrm{P}</tex>, что противоречит предположению <tex>\mathrm{P} \ne \mathrm{NP}</tex>.
Аналогично, в случае, если Пусть <tex>\lim_{n \to \infty}fT_g(n1) = 2i+1const = d</tex>. Тогда функция «застряла» в ветке «иначе» случая три.Следствием этого является то, что Существует константа <tex>c \mathrm{SAT}</tex> функцией <tex>p_ige d</tex> сводится к конечному множеству, что тожепротиворечит предположению для которой при любом <tex>\mathrm{P} \ne \mathrm{NP}n</tex>.верно
Получается, что <tex>\lim_{n \to \infty}fc (n-1) = ^6 + k_1 n^5 +2 k_2 k_3 n^2 \infty</tex>, но по построению если <tex>f</tex> неограниченно растет,то <tex>L</tex> не совпадает ни с каким языком <tex>L(p_i)</tex> и ни одна функция <tex>f_i</tex> не сводит<tex>\mathrm{SAT}</tex> к <tex>L</tex>. Следовательно, выполняются все три требуемых свойста, и <tex>L</tex> является примеромязыка из <tex>\mathrm{NP}\setminus(\mathrm{P} \cup \mathrm{NPC})le c n^6</tex>.
Теорема доказанаТогда, в силу <tex>T_g(1) = d \le c 1^6</tex> и неравенства выше, по индукции легко доказать, что <tex>T_g(n)</tex> ограничено сверху <tex>c n^6</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.
==ИсточникиИсточник ==* ''Rafael PassWilliam Gasarch, Lance Fortnow''. [http://wwwblog.cscomputationalcomplexity.cornell.edu/courses/cs6810/2009sporg/scribemedia/lecture2ladner.pdf Theory Two Proofs of Computing. Lecture 2: DiagonalizationLadner’s Theorem]
