Формулировка
Теорема Ладнера (Ladner's Theorem) утверждает,
что если [math]P \ne NP[/math], то существует язык [math]L[/math],
принадлежащий [math]NP \setminus (P \cup NPC)[/math].
Иллюстрация
Определим язык [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), \dots[/math]
Далее будем обозначать [math]\underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_n[/math]
как [math]^{n}a[/math].
Рассмотрим язык [math]SAT[/math]. Логично предположить, что как в [math]A[/math],
так и в [math]\bar{A}[/math] лежит бесконечное множество элементов из [math]SAT[/math],
не принадлежащих классу [math]P[/math], поэтому [math]SAT \cap A \not\in P[/math].
Из [math]A \in P[/math] и [math]SAT \in NP[/math] следует, что [math]SAT \cap A \in NP[/math].
Осталось показать, что [math]SAT \cap A[/math] не является NP-полным. Пусть
это не так. Тогда из NP-полноты следует, что существует полиномиальная функция [math]f[/math]
сводящая по Карпу [math]SAT[/math] к [math]SAT \cap A[/math].
Возьмем формулу [math]\varphi[/math] длиной [math]^{2k+1}10[/math].
Она не лежит в [math]A[/math] и, следовательно, в [math]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]SAT \cap A[/math] можно осуществить за [math]O(2^{poly})[/math]
(это следует из принадлежности [math]NP[/math]), получаем программу
разрешающую [math]\varphi[/math] за полином. Утверждение о том, что все формулы
[math]\varphi[/math] длиной [math]^{2k+1}10[/math] принадлежат классу
[math]P[/math] скорее всего не верно, а ,следовательно, язык
[math]SAT \cap A[/math] не является 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 = A \cap SAT[/math] искомым примером множества
из [math]NP \setminus (P \cup NPC)[/math].
Утверждение 1. Можно перечислить (возможно с повторениями) все языки из [math]P[/math].
Действительно, рассмотрим последовательность всех программ
[math] \tilde{p_1}, \tilde{p_2}, \ldots, \tilde{p_n}, \ldots[/math]
Обозначим за [math]p_i[/math] программу, запускающую [math]\tilde{p_i}[/math]
с таймером [math]in^i[/math]. Тогда среди [math]{p_i}[/math] встречаются
только программы из [math]P[/math], и для каждой полиномиальной программы
[math]\tilde{p_i}[/math], работающей за полином [math]q_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{P}[/math].
Доказательство аналогично доказательству предыдущего утверждения.
[math]L=\left\{\varphi \mid \varphi \in SAT \and f(|\varphi|)\, \vdots \, 2\right\}[/math]
[math]A=\left\{x \mid f(|x|) \, \vdots \, 2 \right\}[/math]
[math]f(0) = f(1) = 0[/math]
Определим [math]f(n)[/math]. Для этого рассмотрим два случая:
- Случай 1: [math]f(n-1)=2i[/math].
- Если существует [math]x[/math], такой что [math]|x| \lt \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].
- Случай 2: [math]f(n-1)=2i+1[/math].
- Если существует [math]x[/math], такой что [math]|x| \lt \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].
Покажем, что [math]f \in \tilde{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) + c2_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]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_1(n)[/math] — построение программы [math]f_i[/math].
[math]a(n) \approx 2^{log_2 n} = n[/math], таким образом [math]a(n) \in \tilde{P}[/math]
[math]b_1(n) \approx[/math] что-то, тоже из [math]\tilde{P}[/math]
[math]b_2(n) \approx 2^{log_2 n} log_2 n [/math], из [math]\tilde{P}[/math]
[math]b_3(n) \approx 2^{log_2 n} log_2 n + log_2 n[/math], из [math]\tilde{P}[/math]
[math]b_4(n) \approx [/math] что-то типа [math]b_3(n)[/math], но с оценкой на [math]|f_i(x)|[/math]
вместо [math]log_2 n[/math], из [math]\tilde{P}[/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{P}[/math] и [math]A \in P[/math].
В результате всё почти хорошо.
Теорема доказана.
