==Формулировка=='''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным, ни [[NP-полнота|NP-полным]].
'''Теорема Ладнера''' (Ladner's Theorem) утверждает,что если <math>P \ne NP</math>, то существует язык <math>L</math>,принадлежащий <math>NP \setminus (P \cup NPC)</math>.== Иллюстрация ==
==Иллюстрация== Определим язык <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>,не принадлежащих классу <math>P</math>распознаваемых за полиномиальное время, поэтому <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-полным.
Заметим, что это объяснение не является доказательством!
==ДоказательствоТеорема == {{Теорема|author=Ладнер|statement=<tex>\mathrm{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>\mathrm{NP}</tex>-полный язык (например, [[Примеры NP-полных_языков. Теорема_Кука#NP-полнота_2|SAT]]) нельзя [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|свести по Карпу]] к полиномиальному. Будем искать такой язык <tex>A</tex>, чтобы язык <tex>L = \mathrm{SAT} \cap A</tex> удовлетворял следующим условиям: # <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 \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, x) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>.
Будем искать язык Для простоты будем считать, что <mathtex>A|\Sigma| = 2</mathtex>, удовлетворяющий следующим условиям:#. Построим такую ''неубывающую'' функцию <mathtex>A g \in \tilde{\mathrm{P}}</mathtex> (, что влечёт за собойпри <mathtex>SAT A = \cap A {x \in NP</math>\Sigma^*: g(|x|)#<math>SAT \cap A equiv 0 \notpmod{2} \in P}</mathtex>#для <mathtex>SAT \nleqslant SAT \cap AL</mathtex>выполняются три перечисленных свойства.
Если такой язык существует, то <math>L = A \cap SAT</math> искомым примером множестваиз <math>NP \setminus (P \cup NPC)</math>.== Алгоритм построения g ===
'''Утверждение Положим <tex>g(0) = g(1) = 1</tex>.''' Можно перечислить Для <tex>n \ge 1</tex> построим <tex>g(возможно n + 1)</tex> рекурсивно — с повторениями) все языки из помощью <mathtex>Pg(0), g(1), \ldots, g(n)</mathtex>.
Действительно, рассмотрим последовательность всех программ, упорядоченных по длине,* Если <mathtex> (\tilde{p_0}, \tilde{p_1}, \ldots, \tilde{p_n}, \ldots</math>Обозначим за <math>p_i</math> программу, запускающую <math>\tilde{p_i}</math>с таймером <math>inlog_2 n)^i</math>. Тогда среди <math>{p_ig(n)}</math> встречаютсятолько программы из <math>P</math>, и для каждой полиномиальной программы<math>\tilde{p_i}ge n</mathtex>, работающей за полином то <mathtex>q_ig(n+1)</math>, существуетномер <math>j</math>, такой что <math>jn^j > g_i:= g(n)</math> для всех натуральных <math>n</math>и <math>\tilde{p_j}</math> делает то же самое, что и <math>\tilde{p_i}</mathtex>.Таким образом <math>p_j</math> распознает тот же язык, что и <math>\tilde{p_i}</math>Иначе выполняем один из следующих пунктов.
'''Утверждение * Пусть вычисленное значение <tex>g(n) = 2i</tex>.''' Можно перечислить все функции из Определим <mathtex>\tilde{P}g(n+1)</mathtex>.следующим образом:
Аналогично предыдущему доказательству сначала построим последовательность for <mathtex>x</tex> : <tex>|x| \le \log_2 n</tex> if <tex>M_i(x)</tex> and <tex>[g(|x|) \equiv 1 \pmod{2}</tex> or <tex>x \not \in \tildemathrm{f_iSAT}]</mathtex>,а затем, добавив таймер <mathtex>g(n+1) := g(n)+1</tex> return if <tex>! M_i(x)</tex> and <tex>[g(|x|) \equiv 0 \pmod{2}</tex> and <tex>x \in^i\mathrm{SAT}]</mathtex>, получим последовательность <tex>g(n+1) := g(n)+1</tex> return <mathtex>f_ig(n+1) := g(n)</mathtex>.
Упорядочим все слова по возрастанию длины. Разобьем всё <math>\Sigma^{*}</math> на множества<math>A_i</math>, Пусть вычисленное значение <mathtex>\forall i,j i<j \forall \alpha \in A_i, \beta \in A_j |\alpha| < |\beta|</math>так, что <math>SAT \cap \bigcup_{i=0}^{k} A_{2i}</math> отличается от <math>Lg(p_kn)</math> элементомиз <math>\bigcup_{i=0}^{2k} A_i</math>, и существует <math>\alpha \in \bigcup_{2 i=0}^{2k+- 1}</mathtex>для которого выполняется условие . Определим <mathtex>fg(\alpha) \in \bigcup_{i=0}^{2kn+1}</math> и <math>[\alpha \in SAT] \ne [f(\alpha) \in SAT \cap \bigcup_{i=0}^{k} A_{2i}]</mathtex>.следующим образом:
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}</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}</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>
Если мы сможем построить такие <math>A_i</math>, то язык <math>L = SAT \cap \bigcup_{i=0}^{\infty} A_{2i}</math>будет отличаться от любого полиномиального языка и ни какая полиномиальная функция не будет сводить<math>SAT</math> к <math>L</math>.= Корректность алгоритма ===
Попытаемся построить такую полиномиальную функцию Проверим выполнение второго и третьего свойств языка <mathtex>f</math>, что <math>A_i L = \left\mathrm{x \mid f(|x|) = i\right\}</math>. Тогда <math>A=\left\{x \mid f(|x|) \, \vdots \, 2 \right\SAT}</math> и <math>L=SAT \cap A = \left\{\varphi \mid \varphi \in SAT \and f(|\varphi|)\, \vdots \, 2\right\}</mathtex>.
Зададим * Пусть <mathtex>fg(0) = f(1n) = 0</mathtex>. Теперь рекурсивно определим не имеет предела при <mathtex>f(n)</math>. Для этого рассмотрим три случая:#<math>{\log_2 n} ^ {f(n-1)} to \ge ninfty</mathtex>.#:<math>f(n) = f(n-1)</math>.#<math>f(n-1)=2i</math>.#:Если существует <math>x</math>Значит, такой что для любой <mathtex>|x| < \log_2 nM_i</mathtex> и в <mathtex>p_i(x) \ne L(x)</mathtex>существует элемент, то на котором <mathtex>f(n) = f(n-1)+1M_i</mathtex>«ошибается»; аналогично, иначе для любой полиномиальной функции <mathtex>f(n) = f(n-1)f_i</math>.#<mathtex>f(n-1)=2i+1</math>.#:Если существует элемент, на котором <mathtex>xf_i</mathtex>, такой что неверно сводит <mathtex>|x| < \log_2 nmathrm{SAT}</mathtex> и к <mathtex>SAT(x) \ne L(f_i(x))</math>, то <math>f(n) = f(n-1)+1</math>, иначе <math>f(n) = f(n-1)</mathtex>. Оба свойства выполнены.
Первый случай позволяет сказать, что * Пусть <mathtex>f\lim\limits_{n \to \infty} g(n)= 2i</tex>. Значит, в нашем множестве существует такая машина Тьюринга <tex>M_i</tex>, распознающая <tex>L</mathtex> ограничена , что <mathtex>O\leftforall x \Rightarrow M_i(x) = [g(|x|) \equiv 0 \log_pmod{2} \log_2 n} nwedge x \right) = O(in \log_2 n)mathrm{SAT}]</mathtex>.Второй «ответственен» С одной стороны, <tex>M_i</tex> работает за множества полином, и <mathtex>A_iL \in \mathrm{P}</mathtex> для чётных . С другой стороны, по определению <mathtex>iA</mathtex>, третий — для нечетных.Логарифм <tex>L</tex> различается с <tex>\mathrm{SAT}</tex> в условии конечном числе элементов, значит <mathtex>|x| < \log_2 nmathrm{SAT} \le L</mathtex> необходим для полиномиальности . Получено противоречие с предположением <mathtex>f(n)\mathrm{P} \neq \mathrm{NP}</mathtex>.
Покажем, что * Пусть <tex>\lim\limits_{n \to \infty} g(n) = 2i + 1</tex>. Тогда в нашем множестве полиномиальных функций существует <mathtex>f f_i : \forall x \Rightarrow [x \in SAT] = [g(|f_i(x)|) \equiv 0 \pmod{2} \wedge f_i(x) \in \tildemathrm{SAT}]</tex>. С одной стороны, <tex>\mathrm{PSAT}\le L</tex> с помощью <tex>f_i</mathtex>. Для упрощения будем считатьС другой стороны, из определения <tex>A</tex> выходит, что алфавит язык <tex>L</tex> конечен, значит <mathtex>L \in \Sigma=mathrm{0,1P}</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>Таким образом, где:*при верности предположения <mathtex>T(n-1)</math> идёт на вычисление <math>f(n-1)</math>;*<math>a(n)</math> — перебор всех слов <math>x</math>, таких что <math>|x| < \log_2 nmathrm{P} \neq \mathrm{NP}</mathtex>;*второе и третье свойства <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> — запуск <mathtex>L(f_i(x))</math>;*<math>c_1(n)</math> — построение программы <math>p_i</math>;*<math>c_2(n)</math> — построение программы <math>f_i</mathtex>выполнены.
<math>a(n) = O\left(2^{\log_2 n}\right) = O(n)</math>, таким образом <math>a(n) \in \tilde{P}</math>= Время работы алгоритма ===
Проверим выполнение первого свойства языка <mathtex>b_1L</tex>. Для этого достаточно установить полиномиальность <tex>A</tex>. Покажем, что <tex>T(g, n) = O\left</tex> отличается от <tex>T(g, n - 1)</tex> не более, чем на неубывающий полином <tex>p(i(\log_2 n)^i\right) = O\left(f</tex>. Из этого будет следовать полиномиальность <tex>g</tex>: <tex>T(g, n-1)\le p(\log_2 n)^{f+ p(n-1)}+ \rightldots + p(1) = O\left(fle n p(n-1)n\right) = Oin poly(n^2) \in \tilde{P}</mathtex>.
Заметим, что <mathtex>b_2g(n) = O \left( 2^{\log_2 le n} \log_2 </tex> по построению для <tex>n\right) = O\left(n \log_2 n\right) = O\left(n^2\right) \in \tilde{P}ge 1</mathtex>.
Вычисление значения <mathtex>b_3g(n+1) = O \left</tex> состоит из вычисления <tex>g(2^{\log_2 n} \log_2 n + \log_2 n\right) = O \left</tex>, проверки неравенства <tex>(n \log_2 n\right) = O\left^{g(n^2\right) } \in \tilde{P}ge n</mathtex>и, возможно, запуска одной из двух внутренних функций, время выполнения которых составляет:
<mathul>b_4<li>для случая <tex>g(n) = b32 i</tex>:<br/><tex>\parbox{0px}{\begin{align*}T(b1n) & \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|) = O\leftle \\ & \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^42 + n^2 \rightlog_2 n + n T(g, \log_2 n)) \in le \\ & \le k_1 (2n^3 + n T(g, \log_2 n));\tildeend{Palign*}}</mathtex></li>
Чтобы построить программу <mathli>p_iдля случая </mathtex> достаточно построить g(n) = 2 i - 1<math/tex>\tilde{p_i}:<br/math>. Из того, что все <mathtex>\tildeparbox{p_i0px}</math> упорядоченны по длине, следует, что длина{<math>\tildebegin{p_ialign*}</math> не превосходит <math>ci</math> T(константа зависит от языка описания программыn).Поэтому для построения i-ой программы достаточно перебрать все <math>& \le 2^{ci\log_2 n} (T(x \in \mathrm{SAT}</math> слов с длиной меньше, чем <math>ci</math>) + T(g,|f_i(x)|) + T(f_i(x) \in \mathrm{SAT})) \le \\и вывести i-ое, являющееся программой. Такой способ требует <math>O & \le k_2 n (2^{ci\log_2 n}i\log_2 n + T(g, \log_2 n) = O(+ 2^{\log_2 n} \log_2 n) = O\le \\ & \le k_2 (n2n^2\log_2 n + n T(g, \log_2 n))</math> времени.\le \\Аналогично можно построить и <math>f_i</math>. Из этого следует & \le k_2 (2n^3 + n T(g, что <math>c_1(\log_2 n)).\end{align*}}</mathtex> и <math/li>c_2(n)</mathul> тоже полиномиальны.
Получаем, что Вычислить <mathtex>T(\log_2 n) = T^{g(n-1) + poly}</mathtex>. Значит можно за<mathtex>Tk_3 \log_2 g(n) |(\le log_2 n)^{g(n )}|^2 \cdot poly </math>. Поэтому <math>Tle k_3 (g(n) |log_2 n|)^2 log_2 n \in \tilde{P}</math> и <math>A \in Ple k_3 n^3</mathtex>.
Таким образом, <mathtex>f</math> полиномиальнаT(g, n) \le T(g, n-1) + k (n^3 + n T(g, а значит <math>A \in Plog_2 n))</mathtex>.
Предположим, что Пусть <mathtex>\lim_{n \to \infty}fT(ng, 1) = 2id</mathtex>. Это значит, что фунция «застряла» в ветке «иначе» случая два,но из этого следует, что Существует константа <mathtex>SATc \ge d</mathtex> отличается от , для которой при любом <mathtex>L(p_i)n</mathtex> лишь на конечное число элементов. Этоверновлечёт за собой принадлежность <mathtex>SAT</math> к <math>P</math>, что противоречит предположению <math>P c (n-1)^4 + k n^3 + k n c (\log_2 n)^4 \ne NPle c n^4</mathtex>.
АналогичноТогда, в случае, если силу <mathtex>\lim_{n \to \infty}fT(ng, 1) = 2i+d \le c \cdot 1^4</mathtex>. Тогда функция «застряла» в ветке «иначе» случая три.Следствием этого является тои неравенства строкой выше, по индукции легко доказать, что <mathtex>SATT(g, n)</mathtex> функцией ограничено сверху <mathtex>p_ic n^4</mathtex> сводится к конечному множеству, что тожепротиворечит предположению то есть <mathtex>g \in \tilde{\mathrm{P }}</tex>, а, в свою очередь, <tex>A \in \ne NPmathrm{P}</mathtex>.}}
Получается, что <math>\lim_{n \to \infty}f(n) = +\infty</math>, но по построению, если <math>f</math> неограниченно растет,= Источник ==то <math>L</math> не совпадает ни с каким языком <math>L(p_i)</math>* ''William Gasarch, и ни какая функция <math>f_i<Lance Fortnow''. [http:/math> не сводит<math>SAT</math> к <math>L</math>blog.computationalcomplexity. Следовательно, выполняются все три пункта, и <math>L<org/math> является примеромязыка из <math>NP\setminus(P \cup NPC)<media/math>ladner.pdf Two Proofs of Ladner’s Theorem]
Теорема доказана.[[Категория: Теория сложности]]
