Теорема Ладнера

Формулировка

Теорема Ладнера (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]A \in P[/math] и [math]SAT \in NP[/math] следует, что [math]SAT \cap A \in NP[/math].

Предположим, что [math]SAT \cap A[/math] является NP-полным. Из NP-полноты следует, что существует полиномиальная функция f сводящая по Карпу [math]SAT[/math] к [math]SAT \cap A[/math].

Возьмем формулу [math]\phi[/math] длиной [math]^{2k+1}10[/math]. Она не лежит в [math]A[/math] и, следовательно, в [math]SAT \cap A[/math]. Функция [math]f[/math] не может перевести [math]\phi[/math] в промежуток [math]\left[^{2k+2}10, ^{2k+4}10\right)[/math] или дальше, так как размер выхода полиномиальной функции не может быть экспоненциально больше длинны входа. Значит [math]\phi[/math] отображается в меньший промежуток, но в этом случае размер выхода экспоненциально меньше длины входа. Добавляя к этому то, что проверку на принадлежность [math]f(\phi)[/math] [math]SAT \cap A[/math] можно осуществить за [math]O(2^{poly})[/math] (это следует из принадлежности [math]NP[/math]), получаем программу разрешающую [math]\phi[/math] за полином, а это почему-то плохо.

Доказательство

[math]L=\left\{\varphi | \varphi \in SAT \and f(|\varphi|) \text{ is even}\right\}[/math]

[math]A=\left\{x | f(|x|) \text{ is even}\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_2n[/math] и [math]M_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_2n[/math] и [math]SAT(x) \ne L(g_i(x))[/math], то [math]f(n) = f(n-1)+1[/math], иначе [math]f(n) = f(n-1)[/math]