109
правок
Изменения
м
Нет описания правки
'''Теорема Ладнера''' (Ladner's Theorem) утверждает,
что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык <tex>L</tex>,
принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся полиномиальным и [[NP-полнота|NP-полным]].
==Иллюстрация==
Рассмотрим язык [[SAT]] всех удовлетворимых формул. Логично предположить, что как в <tex>A</tex>,
так и в <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-полным. Пусть
это не так. Тогда из NP-полноты следует, что существует полиномиальная функция <math>f</math>,
[[Сведение по Карпу|сводящая по Карпу]] <tex>\mathrm{SAT}</tex> к <tex>\mathrm{SAT } \cap A</tex>.
Возьмём формулу <tex>\varphi</tex> длиной <tex>^{2k+1}10</tex>.
Она не лежит в <tex>A</tex> и, следовательно, в <tex>\mathrm{SAT } \cap A</tex>.
Функция <tex>f</tex> не может перевести <tex>\varphi</tex> в промежуток
<tex>\left[^{2k+2}10, ^{2k+4}10\right)</tex> или дальше, так как размер
в этом случае размер выхода экспоненциально меньше длины входа. Добавляя
к этому то, что проверку на принадлежность <tex>f(\varphi)</tex> к
<tex>\mathrm{SAT } \cap A</tex> можно осуществить за <tex>O(2^{poly})</tex>(это следует из её принадлежности классу <tex>\mathrm{NP}</tex>), получаем программу,
разрешающую <tex>\varphi</tex> за полином. Утверждение о том, что все формулы
<tex>\varphi</tex> длиной <tex>^{2k+1}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>.
Если такой язык существует, то <tex>L = \mathrm{SAT } \cap A</tex> является искомым примером множестваиз <tex>\mathrm{NP } \setminus (\mathrm{P } \cup \mathrm{NPC})</tex>.
===Утверждение 1===
Можно перечислить (возможно, с повторениями) все языки из <tex>\mathrm{P}</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_i(n)</tex>, существует
номер <tex>j</tex> такой, что <tex>jn^j > g_i(n)</tex> для всех натуральных <tex>n</tex>
===Утверждение 2===
Можно перечислить все функции из <tex>\tilde{\mathrm{P}}</tex>.
Аналогично предыдущему доказательству, сначала построим последовательность <tex>\tilde{f_i}</tex>, а затем, добавив таймер <tex>in^i</tex>, получим последовательность <tex>f_i</tex>.
<tex>A_i</tex> так, что:
*<tex>\forall i<j, \forall \alpha \in A_i, \beta \in A_j: |\alpha| < |\beta|</tex> (то есть разбиение происходит по длинам, причем <tex>A_i</tex> идут «подряд»),
*<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_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}]</tex>.
[[File:Ladner.png]]
Если мы сможем построить такие <tex>A_i</tex>, то язык <tex>L = \mathrm{SAT } \cap \bigcup_{i=0}^{\infty} A_{2i}</tex>
будет отличаться от любого полиномиального языка, и ни одна полиномиальная функция не будет сводить
<tex>\mathrm{SAT}</tex> к <tex>L</tex>.
Попытаемся построить такую полиномиальную функцию <tex>f</tex>, что
<tex>A_i = \left\{x \mid f(|x|) = i\right\}</tex>. Тогда
<tex>A=\left\{x \mid f(|x|) \equiv 0 (\mathrm{mod}\ 2) \right\}</tex> и
<tex>L=\mathrm{SAT } \cap A = \left\{\varphi \mid \varphi \in \mathrm{SAT } \land f(|\varphi|) \equiv 0 (\mathrm{mod}\ 2) \right\}</tex>
===Построение <tex>f</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| < \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>[\alpha \in L]</tex> делаются для <tex>\alpha</tex>, для которых <tex>f</tex> уже построена.
===Полиномиальность <tex>f</tex>===
Покажем, что <tex>f \in \tilde{\mathrm{P}}</tex>. Для упрощения будем считать, что алфавит <tex>\Sigma=\{0,1\}</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>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>T(n) = T(n-1) + poly</tex>. Значит, <tex>T(n) \le n \cdot poly </tex>.
Поэтому <tex>T(n) \in \tilde{\mathrm{P}}</tex> и <tex>A \in \mathrm{P}</tex>.
Таким образом, <tex>f</tex> полиномиальна и <tex>A \in \mathrm{P}</tex>.
===Доказательство выполнения свойств <tex>A</tex>===
Предположим, что <tex>\lim_{n \to \infty}f(n) = 2i</tex>. Это значит, что фунция «застряла» в ветке «иначе» случая два,
но из этого следует, что <tex>\mathrm{SAT}</tex> не отличается от <tex>L(p_i)</tex>. Этовлечёт за собой принадлежность <tex>\mathrm{SAT}</tex> к <tex>\mathrm{P}</tex>, что противоречит предположению <tex>\mathrm{P } \ne \mathrm{NP}</tex>.
Аналогично, в случае, если <tex>\lim_{n \to \infty}f(n) = 2i+1</tex>. Тогда функция «застряла» в ветке «иначе» случая три.
Следствием этого является то, что <tex>\mathrm{SAT}</tex> функцией <tex>p_i</tex> сводится к конечному множеству, что тожепротиворечит предположению <tex>\mathrm{P } \ne \mathrm{NP}</tex>.
Получается, что <tex>\lim_{n \to \infty}f(n) = +\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})</tex>.
Теорема доказана.
