'''Теорема Ладнера''' (Ladner's Theorem) утверждает,что если <math>[[Класс P|P \ne ]] не совпадает с [[Класс NP|NP</math>]], то существует язык <math>L</math>,принадлежащий <mathtex>\mathrm{NP \setminus (P \cup NPC)}</mathtex>, но не являющийся ни полиномиальным, ни [[NP-полнота|NP-полным]].
__TOC__==Иллюстрация==
Определим язык <mathtex>A</mathtex> как множество таких формул <mathtex>\alpha</mathtex>,что <mathtex>\left\lfloor \frac{1}{2}\log_{10}^*|\alpha|\right\rfloor</mathtex> чётно.Иными словами, <mathtex>A</mathtex> — это язык формул с длинами, лежащими в промежутках <mathtex>\left[1,10^{10}\right),
\left[\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_4,
\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_6\right), \dotsldots</mathtex>Далее будем обозначать <mathtex>\underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_n</mathtex>как <mathtex>^{n}a</mathtex>.
Рассмотрим язык <math>[[SAT</math>]] всех удовлетворимых формул. Логично предположить, что как в <mathtex>A</mathtex>,так и в <mathtex>\bar{A}</mathtex> лежит бесконечное множество элементов из <mathtex>\mathrm{SAT}</mathtex>,не распознаваемых за полиномиальное время, поэтому <mathtex>\mathrm{SAT } \cap A \not\in \mathrm{P}</mathtex>.Из <mathtex>A \in \mathrm{P}</mathtex> и <mathtex>\mathrm{SAT } \in \mathrm{NP}</mathtex> следует, что <mathtex>\mathrm{SAT } \cap A \in \mathrm{NP}</mathtex>.
Осталось показать, что <mathtex>\mathrm{SAT } \cap A</mathtex> не является NP-полным. Пусть
это не так. Тогда из NP-полноты следует, что существует полиномиальная функция <math>f</math>,
[[Сведение по Карпу|сводящая по Карпу ]] <mathtex>\mathrm{SAT}</mathtex> к <mathtex>\mathrm{SAT } \cap A</mathtex>.
Возьмём формулу <mathtex>\varphi</mathtex> длиной <mathtex>^{2k+1}10</mathtex>. Она не лежит в <mathtex>A</mathtex> и, следовательно, в <mathtex>\mathrm{SAT } \cap A</mathtex>.Функция <mathtex>f</mathtex> не может перевести <mathtex>\varphi</mathtex> в промежуток<mathtex>\left[^{2k+2}10, ^{2k+4}10\right)</mathtex> или дальше, так как размер
выхода полиномиальной функции не может быть экспоненциально больше длины
входа. Значит, <mathtex>\varphi</mathtex> отображается в меньший промежуток, но
в этом случае размер выхода экспоненциально меньше длины входа. Добавляя
к этому то, что проверку на принадлежность <mathtex>f(\varphi)</mathtex> к<mathtex>\mathrm{SAT } \cap A</mathtex> можно осуществить за <mathtex>O(2^{poly})</mathtex>(это следует из её принадлежности классу <mathtex>\mathrm{NP}</mathtex>), получаем программу,разрешающую <mathtex>\varphi</mathtex> за полином. Утверждение о том, что все формулы<mathtex>\varphi</mathtex> длиной <mathtex>^{2k+1}10</mathtex> принадлежат классу<mathtex>\mathrm{P}</mathtex>, скорее всего не верноневерно, и, следовательно, язык <mathtex>\mathrm{SAT } \cap A</mathtex> не является NP-полным.
Заметим, что это объяснение не является доказательством!
==ДоказательствоТеорема ==Будем искать язык <math>A</math>, удовлетворяющий следующим условиям:#<math>A \in P</math> (что влечёт за собой<math>SAT \cap A \in NP</math>);#<math>SAT \cap A \not\in P</math>;#<math>SAT \nleqslant SAT \cap A</math>.
Если такой язык существует, то <math>L {{Теорема|author=Ладнер|statement= SAT \cap A</math> является искомым примером множестваиз <mathtex>\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP } \setminus (\mathrm{P } \cup \mathrm{NPC})\neq \varnothing</mathtex>.|proof=Предположим, что <tex>\mathrm{P} \neq \mathrm{NP}</tex>. Из этого следует, что никакой <tex>\mathrm{NP}</tex>-полный язык (например, [[Примеры NP-полных_языков. Теорема_Кука#NP-полнота_2|SAT]]) нельзя [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|свести по Карпу]] к полиномиальному. Будем искать такой язык <tex>A</tex>, чтобы язык <tex>L = \mathrm{SAT} \cap A</tex> удовлетворял следующим условиям:
===Утверждение 1===Можно перечислить # <tex>L \in \mathrm{NP}</tex> (возможнодля этого достаточно, с повторениямичтобы выполнялось <tex>A \in \mathrm{P}</tex>) все языки из ;# <mathtex>L \not \in \mathrm{P}</tex>;# <tex>\mathrm{SAT} \not \le L</mathtex>.
ДействительноЕсли выполнены все три свойства, рассмотрим последовательность всех программ, упорядоченных по длине:то <mathtex> L \tilde{p_0}, in \tildemathrm{p_1NP}, \ldots, setminus (\tildemathrm{p_nP}, \ldots</math>Обозначим за <math>p_i</math> программу, запускающую <math>cup \tildemathrm{p_iNPC}</math>с таймером <math>in^i</math>. Тогда среди <math>{p_i}</math> встречаютсятолько программы из <math>P</math>, и для каждой полиномиальной программы<math>\tilde{p_i}</math>, работающей за полином <math>g_i(n)</math>, существуетномер <math>j</math> такой, что <math>jn^j > g_i(n)</math> для всех натуральных <math>n</math>и <math>\tilde{p_j}</math> делает то же самое, что и <math>\tilde{p_i}</math>.Таким образом, <math>p_j</math> распознает тот же язык, что и <math>\tilde{p_i}</mathtex>.
===Утверждение 2===Можно перечислить Пусть <tex>M_1, \ldots, M_n, \ldots</tex> — все функции машины Тьюринга из <mathtex>\tilde{\mathrm{P}}</tex> (возможно, с повторениями), расположенные в таком порядке, чтобы <tex>T(M_i, x) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</mathtex>.
Аналогично предыдущему доказательству, сначала построим последовательность Пусть <mathtex>f_1, \tilde{f_i}ldots, f_n, \ldots</mathtex>,а затем, добавив таймер — аналогичное множество полиномиальных функций: <mathtex>inT(f_i, x) \le |x|^i</mathtex>, получим последовательность для любого <mathtex>f_ix \in \Sigma^*</mathtex>.
===Описание способа построения <math>A</math>===Упорядочим все слова по возрастанию длины. Разобьем всё <math>\Sigma^{*}</math> на множества<math>A_i</math> такДля простоты будем считать, что <mathtex>\forall i<j, \forall \alpha \in A_i, \beta \in A_j: |\alpha| < |\betaSigma|= 2</mathtex>(то есть разбиение происходит по длинам, причем <math>A_i</math> идут подряд),. Построим такую ''неубывающую'' функцию <mathtex>SAT g \cap in \bigcup_tilde{i=0}^\mathrm{kP} A_{2i}</mathtex> отличается от , что при <math>L(p_k)</math> элементомиз <mathtex>A = \bigcup_{i=0}^{2k} A_i</math> и для любого <math>k</math> существует <math>\alpha x \in \bigcup_{i=0}Sigma^{2k+1} A_i</math>,для которого выполняются условия <math>f_k*: g(\alpha|x|) \in equiv 0 \bigcup_pmod{i=02}^{2k+1\} A_i</mathtex> и для <mathtex>[\alpha \in SAT] \ne [f_k(\alpha) \in SAT \cap \bigcup_{i=0}^{k} A_{2i}]L</mathtex>выполняются три перечисленных свойства.
<!--Куда-то сюда неплохо было бы добавить картинку-->=== Алгоритм построения g ===
Если мы сможем построить такие Положим <mathtex>A_ig(0) = g(1) = 1</mathtex>, то язык . Для <mathtex>L = SAT \cap n \bigcup_{i=0}^{\infty} A_{2i}ge 1</mathtex>будет отличаться от любого полиномиального языка, и ни одна полиномиальная функция не будет сводитьпостроим <mathtex>SATg(n + 1)</mathtex> к рекурсивно — с помощью <mathtex>Lg(0), g(1), \ldots, g(n)</mathtex>.
Попытаемся построить такую полиномиальную функцию * Если <mathtex>f</math>, что <math>A_i = \left(\log_2 n)^{x \mid fg(|x|n) = i\right} \}ge n</mathtex>. Тогда , то <mathtex>A=\left\{x \mid fg(|x|n+1) \, \vdots \, 2 \right\}</math> и <math>L=SAT \cap A := \left\{\varphi \mid \varphi \in SAT \and fg(|\varphi|n)\, \vdots \, 2\right\}</mathtex>. Иначе выполняем один из следующих пунктов.
===Построение <math>f</math>===Зададим <math>f(0) = f(1) = 0</math>. Затем рекурсивно определим <math>f(n)</math>. Для этого рассмотрим три случая:*Пусть вычисленное значение <mathtex>{\log_2 n} ^ {f(n-1)} \ge n</math>:*:<math>fg(n) = f(n-1)2 i</mathtex>;*. Определим <mathtex>fg(n-1)=2i</math>:*:если существует <math>x</math> такой, что <math>|x| < \log_2 n</math> и <math>p_i(x) \ne L(x)</math>, то <math>f(n) = f(n-1)+1</math>, иначе <math>f(n) = f(n-1)</math>;*<math>f(n-1)=2i+1</mathtex>следующим образом:*:если существует <math>x</math> такой, что <math>|x| < \log_2 n</math> и <math>SAT(x) \ne L(f_i(x))</math>, то <math>f(n) = f(n-1)+1</math>, иначе <math>f(n) = f(n-1)</math>.
Первый случай позволяет сказать, что for <mathtex>fx</tex> : <tex>|x| \le \log_2 n</tex> if <tex>M_i(nx)</mathtex> ограничена and <mathtex>O[g(|x|) \left(equiv 1 \log_pmod{2}</tex> or <tex>x \not \in \log_2 nmathrm{SAT} ]</tex> <tex>g(n\right+1) := Og(\log_2 n)+1</mathtex>.Второй «ответственен» за множества return if <mathtex>A_i! M_i(x)</mathtex> для чётных and <mathtex>i[g(|x|) \equiv 0 \pmod{2}</mathtex>, третий — для нечетных.Логарифм в условии and <mathtex>|x| \in \mathrm{SAT}]</tex> < \log_2 tex>g(n+1) := g(n)+1</mathtex> необходим для полиномиальности return <mathtex>fg(n+1) := g(n)</mathtex>.
* Пусть вычисленное значение <tex>g(n) = 2 i - 1</tex>. Определим <tex>g(n+1)</tex> следующим образом:
===Полиномиальность for <mathtex>fx</mathtex> : <tex>|x| \le \log_2 n, |f_i(x)| \le \log_2 n</tex>===Покажем, что if <mathtex>f x \in \tildemathrm{PSAT}</mathtex>. Для упрощения будем считать, что алфавит and <tex>[g(|f_i(x)|) \equiv 1 \pmod{2}</tex> or <mathtex>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)</mathtex>.
<math>T(n) = T(n-1) + a(n)(b_1(n) + b_2(n) + b_3(n) + b_4(n)) + c_1(n) + c2_2(n)</math>, где:*<math>T(n-1)</math> идёт на вычисление <math>f(n-1)</math>;*<math>a(n)</math> — время перебора всех слов <math>x</math> таких, что <math>|x| < \log_2 n</math>;*<math>b_1(n)</math> — время работы <math>p_i(x)</math>;*<math>b_2(n)</math> — время работы <math>SAT(x)</math>;*<math>b_3(n)</math> — время работы <math>L(x)</math>;*<math>b_4(n)</math> — время работы <math>L(f_i(x))</math>;*<math>c_1(n)</math> — время, необходимое для построения программы <math>p_i</math>;*<math>c_2(n)</math> — время, необходимое для построения функции <math>f_i</math>.== Корректность алгоритма ===
Проверим выполнение второго и третьего свойств языка <mathtex>a(n) L = O\left(2^mathrm{\log_2 nSAT}\right) = O(n)</math>, таким образом <math>a(n) \in \tilde{P}cap A</mathtex>.
* Пусть <mathtex>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)}\right) = O\left(f(n-1)n\right) = O(n^2) \in \tilde{PSAT}</mathtex> к <tex>L</tex>. Оба свойства выполнены.
* Пусть <mathtex>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^{\log_2 n} \log_2 nwedge x \right) = Oin \left(n mathrm{SAT}]</tex>. С одной стороны, <tex>M_i</tex> работает за полином, и <tex>L \log_2 nin \right) = Omathrm{P}</tex>. С другой стороны, по определению <tex>A</tex>, <tex>L</tex> различается с <tex>\left(n^2mathrm{SAT}</tex> в конечном числе элементов, значит <tex>\right) mathrm{SAT} \in le L</tex>. Получено противоречие с предположением <tex>\tildemathrm{P} \neq \mathrm{NP}</mathtex>.
* Пусть <mathtex>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 \tildemathrm{SAT}]</tex>. С одной стороны, <tex>\mathrm{SAT} \le L</tex> с помощью <tex>f_i</tex>. С другой стороны, из определения <tex>A</tex> выходит, что язык <tex>L</tex> конечен, значит <tex>L \in \mathrm{P}</mathtex>. Снова получено противоречие с предположением.
Таким образом, при верности предположения <mathtex>b_4(n) = b3(b1(n)) = O\left(n^4mathrm{P} \right) neq \in \tildemathrm{PNP}</mathtex> второе и третье свойства <tex>L</tex>выполнены.
Чтобы построить программу <math>p_i</math> достаточно построить <math>\tilde{p_i}</math>. Из того, что все <math>\tilde{p_i}</math> упорядочены по длине, следует, что длина<math>\tilde{p_i}</math> не превосходит <math>ci</math> (константа зависит от языка описания программы).Поэтому для построения i-ой программы достаточно перебрать все <math>2^{ci+1}-1</math> слов с длиной не больше <math>ci</math>и вывести i-ое, являющееся программой. Такой способ требует <math>O(2^{ci}i) = O(2^{\log_2 n} \log_2 n) = O(n^2)</math> времени.Аналогично можно построить и <math>f_i</math>. Из этого следует, что <math>c_1(n)</math> и <math>c_2(n)</math> тоже полиномиальны.= Время работы алгоритма ===
ПолучаемПроверим выполнение первого свойства языка <tex>L</tex>. Для этого достаточно установить полиномиальность <tex>A</tex>. Покажем, что <mathtex>T(g, n) = </tex> отличается от <tex>T(g, n-1) + poly</mathtex>. Значитне более, чем на неубывающий полином <mathtex>Tp(n) \le n \cdot poly </mathtex>. Поэтому Из этого будет следовать полиномиальность <tex>g</tex>: <mathtex>T(g, n) \in le p(n) + p(n - 1) + \ldots + p(1) \tilde{P}</math> и <math>A le n p(n) \in Ppoly(n)</mathtex>.
Таким образомЗаметим, что <mathtex>fg(n) \le n</mathtex> полиномиальна и по построению для <mathtex>A n \in Pge 1</mathtex>.
===Доказательство выполнения свойств <math>A</math>===Предположим, что Вычисление значения <mathtex>\lim_{n \to \infty}fg(n+1) = 2i</mathtex>. Это значит, что фунция «застряла» в ветке «иначе» случая два,но состоит из этого следует, что <math>SAT</math> не отличается от вычисления <mathtex>Lg(p_in)</math>. Этовлечёт за собой принадлежность <math>SAT</math> к <math>P</mathtex>, что противоречит предположению проверки неравенства <mathtex>P (\ne NPlog_2 n)^{g(n)} \ge n</mathtex>.и, возможно, запуска одной из двух внутренних функций, время выполнения которых составляет:
Аналогично<ul><li>для случая <tex>g(n) = 2 i</tex>:<br/><tex>\parbox{0px}{\begin{align*}T(n) & \le 2^{\log_2 n} (T(M_i, в случаеx) + T(g, если <math>|x|) + T(x \in \lim_mathrm{SAT})) \le \\ & \le k_1 n (|x|^i + T(g, |x|) + 2^{|x|}|x|) \to le \\ & \le k_1 n ((\inftylog_2 n)^{g(n)}f+ T(g, \log_2 n) + 2^{\log_2 n} \log_2 n) = 2i\le \\ & \le k_1 (n^2 + n^2 \log_2 n +1</math>. Тогда функция «застряла» в ветке «иначе» случая три.n T(g, \log_2 n)) \le \\Следствием этого является то & \le k_1 (2n^3 + n T(g, что <math>SAT\log_2 n));\end{align*}}</math> функцией <mathtex>p_i</math> сводится к конечному множеству, что тожепротиворечит предположению <math>P \ne NP</mathli>.
Получается, что <mathli>для случая <tex>\lim_{n \to \infty}fg(n) = +\infty2 i - 1</mathtex>, но по построению если <math>f:<br/math> неограниченно растет,то <mathtex>L</math> не совпадает ни с каким языком <math>L\parbox{0px}{\begin{align*}T(n) & \le 2^{\log_2 n} (T(x \in \mathrm{SAT}) + T(g, |f_i(p_ix)</math> и ни одна функция <math>|) + T(f_i</math> не сводит(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 \\<math>SAT</math> к <math>L</math>. Следовательно & \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*}}<math/tex>L</mathli> является примеромязыка из <math>NP\setminus(P \cup NPC)</mathul>.
Теорема доказанаВычислить <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] [[Категория: Теория сложности]]
