Изменения

'''Теорема Ладнера''' (Ladner's Theorem) утверждает,что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык <tex>L</tex>,принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным и , ни [[NP-полнота|NP-полным]].

==Иллюстрация==

<mathtex>\left[1,10^{10}\right),

\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_6\right), \ldots</mathtex>

так и в <tex>\bar{A}</tex> лежит бесконечное множество элементов из <tex>\mathrm{SAT}</tex>,не распознаваемых за полиномиальное время, поэтому <tex>\mathrm{SAT } \cap A \not\in \mathrm{P}</tex>.Из <tex>A \in \mathrm{P}</tex> и <tex>\mathrm{SAT } \in \mathrm{NP}</tex> следует, что <tex>\mathrm{SAT } \cap A \in \mathrm{NP}</tex>.

Осталось показать, что <tex>\mathrm{SAT } \cap A</tex> не является NP-полным. Пусть

[[Сведение по Карпу|сводящая по Карпу]] <tex>\mathrm{SAT}</tex> к <tex>\mathrm{SAT } \cap A</tex>.

Она не лежит в <tex>A</tex> и, следовательно, в <tex>\mathrm{SAT } \cap A</tex>.

<tex>\mathrm{SAT } \cap A</tex> можно осуществить за <tex>O(2^{poly})</tex>(это следует из её принадлежности классу <tex>\mathrm{NP}</tex>), получаем программу,

<tex>\mathrm{P}</tex>, скорее всего не верноневерно, и, следовательно, язык <tex>\mathrm{SAT } \cap A</tex> не является NP-полным.

==ДоказательствоТеорема ==Будем искать язык <tex>A</tex>, удовлетворяющий следующим условиям:#<tex>A \in P</tex> (что влечёт за собой <tex>SAT \cap A \in NP</tex>);#<tex>SAT \cap A \not\in P</tex>;#<tex>SAT \not \leqslant SAT \cap A</tex>.

Если такой язык существует, то {{Теорема|author=Ладнер|statement=<tex>L = SAT \cap Amathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \varnothing</tex> является искомым примером множества.из |proof=Предположим, что <tex>\mathrm{P} \neq \mathrm{NP }</tex>. Из этого следует, что никакой <tex>\setminus mathrm{NP}</tex>-полный язык (P например, [[Примеры NP-полных_языков. Теорема_Кука#NP-полнота_2|SAT]]) нельзя [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|свести по Карпу]] к полиномиальному. Будем искать такой язык <tex>A</tex>, чтобы язык <tex>L = \mathrm{SAT} \cup NPC)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> L \tilde{p_0}, in \tildemathrm{p_1NP}, \ldots, setminus (\tildemathrm{p_nP}, \ldots</tex>Обозначим за <tex>p_i</tex> программу, запускающую <tex>\tilde{p_i}</tex>с таймером <tex>in^i</tex>. Тогда среди <tex>{p_i}</tex> встречаютсятолько программы из <tex>P</tex>, и для каждой полиномиальной программы<tex>cup \tildemathrm{p_iNPC}</tex>, работающей за полином <tex>g_i(n)</tex>, существуетномер <tex>j</tex> такой, что <tex>jn^j > g_i(n)</tex> для всех натуральных <tex>n</tex>и <tex>\tilde{p_j}</tex> делает то же самое, что и <tex>\tilde{p_i}</tex>.Таким образом, <tex>p_j</tex> распознает тот же язык, что и <tex>\tilde{p_i}</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>.

===Описание способа построения <math>A</math>===Упорядочим все слова по возрастанию длины. Разобьем всё <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>SAT g \cap in \bigcup_{i=0}^{k} A_{2i}</tex> отличается от <tex>L(p_k)</tex> элементом <tex>x_tilde{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 SAT] \ne [f_k(x_{2k+1}) \in SAT \cap \bigcup_{i=0}^{k} A_{2i}]L</tex>выполняются три перечисленных свойства.

Если мы сможем построить такие Положим <tex>A_ig(0) = g(1) = 1</tex>, то язык . Для <tex>L = SAT \cap n \bigcup_{i=0}^{\infty} A_{2i}ge 1</tex>будет отличаться от любого полиномиального языка, и ни одна полиномиальная функция не будет сводитьпостроим <tex>SATg(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=SAT \cap A = \left\{\varphi \mid \varphi \in 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 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>fx</tex> : <tex>|x| \le \log_2 n, |f_i(x)| \le \log_2 n</tex>===Покажем, что if <tex>f x \in \tildemathrm{PSAT}</tex>. Для упрощения будем считать, что алфавит and <tex>[g(|f_i(x)|) \equiv 1 \pmod{2}</tex> or <tex>f_i(x) \Sigmanot \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,1\pmod{2}</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 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>T(n) \in \tilde{P}g</tex> и : <tex>A T(g, n) \le p(n) + p(n - 1) + \ldots + p(1) \le n p(n) \in Ppoly(n)</tex>.

Таким образомЗаметим, что <tex>fg(n) \le n</tex> полиномиальна и по построению для <tex>A n \in Pge 1</tex>.

===Доказательство выполнения свойств <tex>A</tex>===Предположим, что Вычисление значения <tex>\lim_{n \to \infty}fg(n+1) = 2i</tex>. Это значит, что фунция «застряла» в ветке «иначе» случая два,но состоит из этого следует, что <tex>SAT</tex> не отличается от вычисления <tex>Lg(p_in)</tex>. Этовлечёт за собой принадлежность <tex>SAT</tex> к <tex>P</tex>, что противоречит предположению проверки неравенства <tex>P (\ne NPlog_2 n)^{g(n)} \ge n</tex>.и, возможно, запуска одной из двух внутренних функций, время выполнения которых составляет:

Аналогично, в случае, если <ul><li>для случая <tex>\lim_{n \to \infty}fg(n) = 2i+12 i</tex>. Тогда функция «застряла» в ветке «иначе» случая три.Следствием этого является то, что <tex>SAT:<br/tex> функцией <tex>p_i\parbox{0px}{\begin{align*}T(n) & \le 2^{\log_2 n} (T(M_i, x) + T(g, |x|) + T(x \in \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> сводится к конечному множеству, что тожепротиворечит предположению <tex>P \ne NP</texli>.

Получается, что <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> не сводит(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 \\<tex>SAT</tex> к <tex>L</tex>. Следовательно & \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>L</texli> является примеромязыка из <tex>NP\setminus(P \cup NPC)</texul>.

Теорема доказанаВычислить <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>.}} == Источник ==* ''William Gasarch, Lance Fortnow''. [http://blog.computationalcomplexity.org/media/ladner.pdf Two Proofs of Ladner’s Theorem] [[Категория: Теория сложности]]