Теорема Ладнера (Ladner's Theorem) утверждает,
что если P не совпадает с NP, то существует язык [math]L[/math],
принадлежащий [math]\mathrm{NP}[/math], но не являющийся полиномиальным и NP-полным.
Иллюстрация
Определим язык [math]A[/math] как множество таких формул [math]\alpha[/math],
что [math]\left\lfloor \frac{1}{2}\log_{10}^*|\alpha|\right\rfloor[/math] чётно.
Иными словами, [math]A[/math] — это язык формул с длинами, лежащими в промежутках
[math]\left[1,10^{10}\right),
\left[\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_4,
\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_6\right), \ldots[/math]
Далее будем обозначать [math]\underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_n[/math]
как [math]^{n}a[/math].
Рассмотрим язык SAT всех удовлетворимых формул. Логично предположить, что как в [math]A[/math],
так и в [math]\bar{A}[/math] лежит бесконечное множество элементов из [math]\mathrm{SAT}[/math],
не распознаваемых за полиномиальное время, поэтому [math]\mathrm{SAT} \cap A \not\in \mathrm{P}[/math].
Из [math]A \in \mathrm{P}[/math] и [math]\mathrm{SAT} \in \mathrm{NP}[/math] следует, что [math]\mathrm{SAT} \cap A \in \mathrm{NP}[/math].
Осталось показать, что [math]\mathrm{SAT} \cap A[/math] не является NP-полным. Пусть
это не так. Тогда из NP-полноты следует, что существует полиномиальная функция [math]f[/math],
сводящая по Карпу [math]\mathrm{SAT}[/math] к [math]\mathrm{SAT} \cap A[/math].
Возьмём формулу [math]\varphi[/math] длиной [math]^{2k+1}10[/math].
Она не лежит в [math]A[/math] и, следовательно, в [math]\mathrm{SAT} \cap A[/math].
Функция [math]f[/math] не может перевести [math]\varphi[/math] в промежуток
[math]\left[^{2k+2}10, ^{2k+4}10\right)[/math] или дальше, так как размер
выхода полиномиальной функции не может быть экспоненциально больше длины
входа. Значит, [math]\varphi[/math] отображается в меньший промежуток, но
в этом случае размер выхода экспоненциально меньше длины входа. Добавляя
к этому то, что проверку на принадлежность [math]f(\varphi)[/math] к
[math]\mathrm{SAT} \cap A[/math] можно осуществить за [math]O(2^{poly})[/math]
(это следует из её принадлежности классу [math]\mathrm{NP}[/math]), получаем программу,
разрешающую [math]\varphi[/math] за полином. Утверждение о том, что все формулы
[math]\varphi[/math] длиной [math]^{2k+1}10[/math] принадлежат классу
[math]\mathrm{P}[/math], скорее всего не верно, и, следовательно, язык
[math]\mathrm{SAT} \cap A[/math] не является NP-полным.
Заметим, что это объяснение не является доказательством!
Доказательство
Будем искать язык [math]A[/math], удовлетворяющий следующим условиям:
- [math]A \in \mathrm{P}[/math] (что влечёт за собой [math]\mathrm{SAT} \cap A \in \mathrm{NP}[/math]);
- [math]\mathrm{SAT} \cap A \not\in \mathrm{P}[/math];
- [math]\mathrm{SAT} \not \leqslant \mathrm{SAT} \cap A[/math].
Если такой язык существует, то [math]L = \mathrm{SAT} \cap A[/math] является искомым примером множества
из [math]\mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC})[/math].
Утверждение 1
Можно перечислить (возможно, с повторениями) все языки из [math]\mathrm{P}[/math].
Действительно, рассмотрим последовательность всех программ, упорядоченных по длине:
[math] \tilde{p_0}, \tilde{p_1}, \ldots, \tilde{p_n}, \ldots[/math]
Обозначим за [math]p_i[/math] программу, запускающую [math]\tilde{p_i}[/math]
с таймером [math]in^i[/math]. Тогда среди [math]{p_i}[/math] встречаются
только программы из [math]\mathrm{P}[/math], и для каждой полиномиальной программы
[math]\tilde{p_i}[/math], работающей за полином [math]g_i(n)[/math], существует
номер [math]j[/math] такой, что [math]jn^j \gt 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}[/math].
Утверждение 2
Можно перечислить все функции из [math]\tilde{\mathrm{P}}[/math].
Аналогично предыдущему доказательству, сначала построим последовательность [math]\tilde{f_i}[/math], а затем, добавив таймер [math]in^i[/math], получим последовательность [math]f_i[/math].
Описание способа построения [math]A[/math]
Упорядочим все слова по возрастанию длины. Разобьем всё [math]\Sigma^{*}[/math] на множества
[math]A_i[/math] так, что:
- [math]\forall i\lt j, \forall \alpha \in A_i, \beta \in A_j: |\alpha| \lt |\beta|[/math] (то есть разбиение происходит по длинам, причем [math]A_i[/math] идут «подряд»),
- [math]\mathrm{SAT} \cap \bigcup_{i=0}^{k} A_{2i}[/math] отличается от [math]L(p_k)[/math] элементом [math]x_{2k}[/math] из [math]\bigcup_{i=0}^{2k} A_i[/math],
- для любого [math]k[/math] существует [math]x_{2k+1} \in \bigcup_{i=0}^{2k+1} A_i[/math], для которого выполняются условия [math]f_k(x_{2k+1}) \in \bigcup_{i=0}^{2k+1} A_i[/math] и [math][x_{2k+1} \in \mathrm{SAT}] \ne [f_k(x_{2k+1}) \in \mathrm{SAT} \cap \bigcup_{i=0}^{k} A_{2i}][/math].
Если мы сможем построить такие [math]A_i[/math], то язык [math]L = \mathrm{SAT} \cap \bigcup_{i=0}^{\infty} A_{2i}[/math]
будет отличаться от любого полиномиального языка, и ни одна полиномиальная функция не будет сводить
[math]\mathrm{SAT}[/math] к [math]L[/math].
Попытаемся построить такую полиномиальную функцию [math]f[/math], что
[math]A_i = \left\{x \mid f(|x|) = i\right\}[/math]. Тогда
[math]A=\left\{x \mid f(|x|) \equiv 0 (\mathrm{mod}\ 2) \right\}[/math] и
[math]L=\mathrm{SAT} \cap A = \left\{\varphi \mid \varphi \in \mathrm{SAT} \land f(|\varphi|) \equiv 0 (\mathrm{mod}\ 2) \right\}[/math]
Построение [math]f[/math]
Зададим [math]f(0) = f(1) = 0[/math]. Затем рекурсивно определим [math]f(n)[/math]. Для этого рассмотрим три случая:
- [math](\log_2 n) ^ {f(n-1)} \ge n[/math]:
- [math]f(n) = f(n-1)[/math];
- [math]f(n-1)=2i[/math]:
- если существует [math]x[/math] такой, что [math]|x| \lt \log_2 n[/math] и [math]p_i(x) \ne [x \in L][/math], то [math]f(n) = f(n-1)+1[/math], иначе [math]f(n) = f(n-1)[/math];
- [math]f(n-1)=2i+1[/math]:
- если существует [math]x[/math] такой, что [math]|x| \lt \log_2 n[/math],[math]|f_i(x)| \lt \log_2 n[/math] и [math][x \in \mathrm{SAT}] \ne [f_i(x) \in L][/math], то [math]f(n) = f(n-1)+1[/math], иначе [math]f(n) = f(n-1)[/math].
Заметим, что вызовы [math][\alpha \in L][/math] делаются для [math]\alpha[/math], для которых [math]f[/math] уже построена.
Первый случай позволяет сказать, что [math]f(n)[/math] ограничена [math]O\left(\log_{\log_2 n} n\right) = O(\log_2 n)[/math].
Второй «ответственен» за множества [math]A_i[/math] для чётных [math]i[/math], третий — для нечетных.
Логарифм в условии [math]|x| \lt \log_2 n[/math] необходим для полиномиальности [math]f(n)[/math].
Полиномиальность [math]f[/math]
Покажем, что [math]f \in \tilde{\mathrm{P}}[/math]. Для упрощения будем считать, что алфавит [math]\Sigma=\{0,1\}[/math].
[math]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)[/math], где:
- [math]T(n-1)[/math] идёт на вычисление [math]f(n-1)[/math];
- [math]a(n)[/math] — время перебора всех слов [math]x[/math] таких, что [math]|x| \lt \log_2 n[/math];
- [math]b_1(n)[/math] — время работы [math]p_i(x)[/math];
- [math]b_2(n)[/math] — время работы [math][x \in \mathrm{SAT}][/math];
- [math]b_3(n)[/math] — время работы [math][x \in L][/math];
- [math]b_4(n)[/math] — время работы [math][f_i(x) \in L][/math];
- [math]c_1(n)[/math] — время, необходимое для построения программы [math]p_i[/math];
- [math]c_2(n)[/math] — время, необходимое для построения функции [math]f_i[/math].
[math]a(n) = O\left(2^{\log_2 n}\right) = O(n)[/math], таким образом [math]a(n)[/math].
[math]b_1(n) = O\left(i(\log_2 n)^i\right) = O\left(f(n-1)(\log_2 n)^{f(n-1)}\right) = O\left(f(n-1)n\right) = O(n^2)[/math]
[math]b_2(n) = O \left( 2^{\log_2 n} \log_2 n\right) = O\left(n \log_2 n\right) = O\left(n^2\right)[/math]
[math]b_3(n) = O \left(2^{\log_2 n} \log_2 n + \log_2 n\right) = O \left(n \log_2 n\right) = O\left(n^2\right)[/math]
[math]b_4(n) = b_3(b_1(n)) = O\left(n^4\right)[/math]
Чтобы построить программу [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] тоже полиномиальны.
Получаем, что [math]T(n) = T(n-1) + poly[/math]. Значит, [math]T(n) \le n \cdot poly [/math].
Поэтому [math]T(n) \in \tilde{\mathrm{P}}[/math] и [math]A \in \mathrm{P}[/math].
Таким образом, [math]f[/math] полиномиальна и [math]A \in \mathrm{P}[/math].
Доказательство выполнения свойств [math]A[/math]
Предположим, что [math]\lim_{n \to \infty}f(n) = 2i[/math]. Это значит, что фунция «застряла» в ветке «иначе» случая два,
но из этого следует, что [math]\mathrm{SAT}[/math] не отличается от [math]L(p_i)[/math]. Это
влечёт за собой принадлежность [math]\mathrm{SAT}[/math] к [math]\mathrm{P}[/math], что противоречит предположению [math]\mathrm{P} \ne \mathrm{NP}[/math].
Аналогично, в случае, если [math]\lim_{n \to \infty}f(n) = 2i+1[/math]. Тогда функция «застряла» в ветке «иначе» случая три.
Следствием этого является то, что [math]\mathrm{SAT}[/math] функцией [math]p_i[/math] сводится к конечному множеству, что тоже
противоречит предположению [math]\mathrm{P} \ne \mathrm{NP}[/math].
Получается, что [math]\lim_{n \to \infty}f(n) = +\infty[/math], но по построению если [math]f[/math] неограниченно растет,
то [math]L[/math] не совпадает ни с каким языком [math]L(p_i)[/math] и ни одна функция [math]f_i[/math] не сводит
[math]\mathrm{SAT}[/math] к [math]L[/math]. Следовательно, выполняются все три требуемых свойста, и [math]L[/math] является примером
языка из [math]\mathrm{NP}\setminus(\mathrm{P} \cup \mathrm{NPC})[/math].
Теорема доказана.
