'''Теорема Ладнера''' (Ladner's Theorem) утверждает,что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык <tex>L</tex>,принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным и , ни [[NP-полнота|NP-полным]].
==Иллюстрация==
Определим язык <tex>A</tex> как множество таких формул <tex>\alpha</tex>,
[[Сведение по Карпу|сводящая по Карпу]] <tex>\mathrm{SAT}</tex> к <tex>\mathrm{SAT} \cap A</tex>.
Возьмём формулу <tex>\varphi</tex> длиной <tex>^{4k2k+31}10</tex>.
Она не лежит в <tex>A</tex> и, следовательно, в <tex>\mathrm{SAT} \cap A</tex>.
Функция <tex>f</tex> не может перевести <tex>\varphi</tex> в промежуток
<tex>\left[^{4k2k+42}10, ^{4k2k+64}10\right)</tex> или дальше, так как размер
выхода полиномиальной функции не может быть экспоненциально больше длины
входа. Значит, <tex>\varphi</tex> отображается в меньший промежуток, но
(это следует из её принадлежности классу <tex>\mathrm{NP}</tex>), получаем программу,
разрешающую <tex>\varphi</tex> за полином. Утверждение о том, что все формулы
<tex>\varphi</tex> длиной <tex>^{4k2k+31}10</tex> принадлежат классу<tex>\mathrm{P}</tex>, скорее всего не верноневерно, и, следовательно, язык
<tex>\mathrm{SAT} \cap A</tex> не является NP-полным.
Заметим, что это объяснение не является доказательством!
==ДоказательствоТеорема ==Будем искать язык <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>.
Если такой язык существует, то {{Теорема|author=Ладнер|statement=<tex>L = \mathrm{SATP} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cap Acup \mathrm{NPC}) \neq \varnothing</tex> является искомым примером множества.из |proof=Предположим, что <tex>\mathrm{NPP} \setminus (neq \mathrm{PNP} </tex>. Из этого следует, что никакой <tex>\cup mathrm{NP}</tex>-полный язык (например, [[Примеры NP-полных_языков. Теорема_Кука#NP-полнота_2|SAT]]) нельзя [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|свести по Карпу]] к полиномиальному. Будем искать такой язык <tex>A</tex>, чтобы язык <tex>L = \mathrm{NPCSAT})\cap A</tex>.удовлетворял следующим условиям:
===Утверждение 1===Можно перечислить # <tex>L \in \mathrm{NP}</tex> (возможнодля этого достаточно, с повторениямичтобы выполнялось <tex>A \in \mathrm{P}</tex>) все языки из ;# <tex>L \not \in \mathrm{P}</tex>;# <tex>\mathrm{SAT} \not \le L</tex>.
ДействительноЕсли выполнены все три свойства, рассмотрим последовательность всех программ, упорядоченных по длине:<tex> \tilde{p_0}, \tilde{p_1}, \ldots, \tilde{p_n}, \ldots</tex>Обозначим за <tex>p_i</tex> программу, запускающую то <tex>L \tilde{p_i}</tex>с таймером <tex>in^i</tex>. Тогда среди <tex>{p_i}</tex> встречаютсятолько программы из <tex>\mathrm{PNP}</tex>, и для каждой полиномиальной программы<tex>\tilde{p_i}</tex>, работающей за полином <tex>g_i(n)</tex>, существуетномер <tex>j</tex> такой, что <tex>jn^j > g_isetminus (n)</tex> для всех натуральных <tex>n</tex>и <tex>\tildemathrm{p_jP}</tex> делает то же самое, что и <tex>\tilde{p_i}</tex>.Таким образом, <tex>p_j</tex> распознает тот же язык, что и <tex>cup \tildemathrm{p_iNPC})</tex>.
===Утверждение 2===Можно перечислить Пусть <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, \tilde{f_i}ldots, f_n, \ldots</tex>, а затем, добавив таймер — аналогичное множество полиномиальных функций: <tex>inT(f_i, x) \le |x|^i</tex>, получим последовательность для любого <tex>f_ix \in \Sigma^*</tex>.
===Описание способа построения <tex>A</tex>===Упорядочим все слова по возрастанию длины. Разобьем всё <tex>\Sigma^{*}</tex> на множества<tex>A_i</tex> такДля простоты будем считать, что:*<tex>\forall i<j, \forall \alpha \in A_i, \beta \in A_j: |\alpha| < |\betaSigma|= 2</tex> (то есть разбиение происходит по длинам, причем <tex>A_i</tex> идут «подряд»),*. Построим такую ''неубывающую'' функцию <tex>g \mathrm{SAT} in \cap \bigcup_{i=0}^{k} A_tilde{2i}</tex> отличается от <tex>L(p_k)</tex> элементом <tex>x_{2k}</tex> из <tex>\bigcup_mathrm{i=0P}^{2k} A_i</tex>, *для любого что при <tex>k</tex> существует <tex>x_A = \{2k+1} x \in \bigcup_{i=0}Sigma^{2k+1} A_i</tex>, для которого выполняются условия <tex>f_k*: g(x_{2k+1}|x|) \in equiv 0 \bigcup_pmod{i=02}^{2k+1\} A_i</tex> и для <tex>[x_{2k+1} \in \mathrm{SAT}] \ne [f_k(x_{2k+1}) \in \mathrm{SAT} \cap \bigcup_{i=0}^{k} A_{2i}]L</tex>выполняются три перечисленных свойства.
[[File:Ladner.png]]=== Алгоритм построения g ===
Если мы сможем построить такие Положим <tex>A_ig(0) = g(1) = 1</tex>, то язык . Для <tex>L = n \mathrm{SAT} \cap \bigcup_{i=0}^{\infty} A_{2i}ge 1</tex>будет отличаться от любого полиномиального языка, и ни одна полиномиальная функция не будет сводитьпостроим <tex>\mathrm{SAT}g(n + 1)</tex> к рекурсивно — с помощью <tex>Lg(0), g(1), \ldots, g(n)</tex>.
Попытаемся построить такую полиномиальную функцию * Если <tex>f</tex>, что <tex>A_i = \left\{x (\mid f(|x|log_2 n) = i\right\}</tex>. Тогда <tex>A=\left\^{x \mid fg(|x|n) \equiv 0 (\mathrm{mod}\ 2) \right\}ge n</tex> и , то <tex>L=\mathrm{SAT} \cap A = \left\{\varphi \mid \varphi \in \mathrm{SAT} \land fg(|\varphi|n+1) \equiv 0 := g(\mathrm{mod}\ 2n) \right\}</tex>. Иначе выполняем один из следующих пунктов.
===Построение <tex>f</tex>===Зададим <tex>f(0) = f(1) = 0</tex>. Затем рекурсивно определим <tex>f(n)</tex>. Для этого рассмотрим три случая:*Пусть вычисленное значение <tex>(\log_2 n) ^ {f(n-1)} \ge n</tex>:*:<tex>fg(n) = f(n-1)2 i</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) = fg(n-1)+1</tex>, иначе <tex>f(n) = f(n-1)</tex>;*<tex>f(n-1)=2i+1</tex>следующим образом:*:если существует <tex>x</tex> такой, что <tex>|x| < \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>.
Заметим, что вызовы for <tex>x</tex> : <tex>|x| \le \log_2 n</tex> if <tex>M_i(x)</tex> and <tex>[g(|x|) \alpha equiv 1 \pmod{2}</tex> or <tex>x \not \in L\mathrm{SAT}]</tex> делаются для <tex>g(n+1) := g(n)+1</tex> return if <tex>! M_i(x)</tex> and <tex>[g(|x|) \equiv 0 \alphapmod{2}</tex> and <tex>x \in \mathrm{SAT}]</tex> <tex>g(n+1) := g(n)+1</tex>, для которых return <tex>fg(n+1) := g(n)</tex> уже построена.
Первый случай позволяет сказать, что * Пусть вычисленное значение <tex>fg(n)</tex> ограничена <tex>O\left(\log_{\log_2 n} n\right) = O(\log_2 n)</tex>.Второй «ответственен» за множества <tex>A_i</tex> для чётных <tex>2 i- 1</tex>, третий — для нечетных.Логарифм в условии Определим <tex>|x| < \log_2 n</tex> необходим для полиномиальности <tex>fg(n+1)</tex>.следующим образом:
===Полиномиальность for <tex>x</tex> : <tex>f|x| \le \log_2 n, |f_i(x)| \le \log_2 n</tex>===Покажем, что if <tex>f x \in \tildemathrm{SAT}</tex> and <tex>[g(|f_i(x)|) \equiv 1 \pmod{2}</tex> or <tex>f_i(x) \not \in \mathrm{PSAT}]</tex> <tex>g(n+1) := g(n)+1</tex> return if <tex>x \not \in \mathrm{SAT}</tex>. Для упрощения будем считать, что алфавит and <tex>[g(|f_i(x)|) \Sigma=equiv 0 \pmod{0,12}</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>T(n) = T(n-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>a(n) L = O\left(2^mathrm{\log_2 nSAT}\right) = O(n)</tex>, таким образом <tex>a(n)cap A</tex>.
* Пусть <tex>b_1g(n) = O\left(i(\log_2 </tex> не имеет предела при <tex>n)^i\right) = Oto \left(f(n-1)(infty</tex>. Значит, для любой <tex>M_i</tex> в <tex>L</tex> существует элемент, на котором <tex>M_i</tex> «ошибается»; аналогично, для любой полиномиальной функции <tex>f_i</tex> существует элемент, на котором <tex>f_i</tex> неверно сводит <tex>\log_2 n)^mathrm{f(n-1)SAT}\right) = O\left(f(n-1)n\right) = O(n^2)</tex>к <tex>L</tex>. Оба свойства выполнены.
* Пусть <tex>b_2\lim\limits_{n \to \infty} g(n) = O 2i</tex>. Значит, в нашем множестве существует такая машина Тьюринга <tex>M_i</tex>, распознающая <tex>L</tex>, что <tex>\leftforall x \Rightarrow M_i( x) = [g(|x|) \equiv 0 \pmod{2^} \wedge x \in \mathrm{SAT}]</tex>. С одной стороны, <tex>M_i</tex> работает за полином, и <tex>L \log_2 nin \mathrm{P} </tex>. С другой стороны, по определению <tex>A</tex>, <tex>L</tex> различается с <tex>\log_2 nmathrm{SAT}</tex> в конечном числе элементов, значит <tex>\right) = Omathrm{SAT} \left(n le L</tex>. Получено противоречие с предположением <tex>\log_2 n\right) = Omathrm{P} \left(n^2neq \right)mathrm{NP}</tex>.
* Пусть <tex>b_3(n) = O \left(2^lim\limits_{\log_2 n} \log_2 n + to \log_2 infty} g(n\right) = O 2i + 1</tex>. Тогда в нашем множестве полиномиальных функций существует <tex>f_i : \left(n forall x \log_2 nRightarrow [x \rightin SAT] = [g(|f_i(x) = O|) \equiv 0 \left(n^pmod{2} \rightwedge 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>b_4(n) = b_3(b_1(n)) = O\left(n^4mathrm{P} \right)neq \mathrm{NP}</tex> второе и третье свойства <tex>L</tex>выполнены.
Чтобы построить программу <tex>p_i</tex> достаточно построить <tex>\tilde{p_i}</tex>. Из того, что все <tex>\tilde{p_i}</tex> упорядочены по длине, следует, что длина<tex>\tilde{p_i}</tex> не превосходит <tex>ci</tex> (константа зависит от языка описания программы).Поэтому для построения i-ой программы достаточно перебрать все <tex>2^{ci+1}-1</tex> слов с длиной не больше <tex>ci</tex>и вывести i-ое, являющееся программой. Такой способ требует <tex>O(2^{ci}i) = O(2^{\log_2 n} \log_2 n) = O(n^2)</tex> времени.Аналогично можно построить и <tex>f_i</tex>. Из этого следует, что <tex>c_1(n)</tex> и <tex>c_2(n)</tex> тоже полиномиальны.= Время работы алгоритма ===
ПолучаемПроверим выполнение первого свойства языка <tex>L</tex>. Для этого достаточно установить полиномиальность <tex>A</tex>. Покажем, что <tex>T(g, n) = </tex> отличается от <tex>T(g, n-1) + poly</tex>. Значитне более, чем на неубывающий полином <tex>Tp(n) \le n \cdot poly </tex>. Поэтому Из этого будет следовать полиномиальность <tex>g</tex>: <tex>T(g, n) \in le p(n) + p(n - 1) + \tilde{ldots + p(1) \mathrm{P}}</tex> и <tex>A le n p(n) \in \mathrm{P}poly(n)</tex>.
Таким образомЗаметим, что <tex>fg(n) \le n</tex> полиномиальна и по построению для <tex>A \in n \mathrm{P}ge 1</tex>.
===Доказательство выполнения свойств Вычисление значения <tex>Ag(n+1)</tex>===Предположим, что состоит из вычисления <tex>\lim_{n \to \infty}fg(n) = 2i</tex>. Это значит, что фунция «застряла» в ветке «иначе» случая два,но из этого следует, что проверки неравенства <tex>(\mathrmlog_2 n)^{SAT}</tex> не отличается от <tex>Lg(p_in)</tex>. Этовлечёт за собой принадлежность <tex>\mathrm{SAT}</tex> к <tex>\mathrm{P}ge n</tex>и, возможно, запуска одной из двух внутренних функций, что противоречит предположению <tex>\mathrm{P} \ne \mathrm{NP}</tex>.время выполнения которых составляет:
Аналогично, в случае, если <ul><li>для случая <tex>\lim_{n \to \infty}fg(n) = 2i+12 i</tex>. Тогда функция «застряла» в ветке «иначе» случая три.:<br/>Следствием этого является то, что <tex>\parbox{0px}{\begin{align*}T(n) & \le 2^{\log_2 n} (T(M_i, x) + T(g, |x|) + T(x \in \mathrm{SAT}</tex> функцией <tex>p_i</tex> сводится к конечному множеству)) \le \\ & \le k_1 n (|x|^i + T(g, что тоже|x|) + 2^{|x|}|x|) \le \\противоречит предположению <tex> & \le k_1 n ((\log_2 n)^{g(n)} + T(g, \mathrmlog_2 n) + 2^{P\log_2 n} \ne 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));\mathrmend{NPalign*}}</tex>.</li>
Получается, что <li>для случая <tex>\lim_{n \to \infty}fg(n) = +\infty2 i - 1</tex>, но по построению если <tex>f:<br/tex> неограниченно растет,то <tex>L</tex> не совпадает ни с каким языком <tex>L\parbox{0px}{\begin{align*}T(n) & \le 2^{\log_2 n} (T(x \in \mathrm{SAT}) + T(g, |f_i(p_ix)</tex> и ни одна функция <tex>|) + T(f_i</tex> не сводит<tex>(x) \in \mathrm{SAT}</tex> к <tex>L</tex>. Следовательно, выполняются все три требуемых свойста, и <tex>L</tex> является примером)) \le \\языка из <tex> & \mathrmle k_2 n (2^{NP\log_2 n}\setminuslog_2 n + T(g, \mathrmlog_2 n) + 2^{P\log_2 n} \cup log_2 n) \le \\ & \le k_2 (2n^2 \mathrmlog_2 n + n T(g, \log_2 n)) \le \\ & \le k_2 (2n^3 + n T(g, \log_2 n)).\end{NPCalign*}})</tex>.</li></ul>
Теорема доказанаВычислить <tex>(\log_2 n)^{g(n)}</tex> можно за<tex>k_3 \log_2 g(n) |(\log_2 n)^{g(n)}|^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, 1) = d</tex>. Существует константа <tex>c \ge d</tex>, для которой при любом <tex>n</tex> верно<tex>c (n-1)^4 + k n^3 + k n c (\log_2 n)^4 \le c n^4</tex>. Тогда, в силу <tex>T(g, 1) = d \le c \cdot 1^4</tex> и неравенства строкой выше, по индукции легко доказать, что <tex>T(g, n)</tex> ограничено сверху <tex>c n^4</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.}} ==ИсточникиИсточник ==* ''Rafael PassWilliam Gasarch, Lance Fortnow''. [http://wwwblog.cscomputationalcomplexity.cornell.eduorg/coursesmedia/cs6810/2009sp/scribe/lecture2ladner.pdf Theory Two Proofs of Computing. Lecture 2Ladner’s Theorem] [[Категория: DiagonalizationТеория сложности]]
