Теорема Ладнера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Доказательство: is even -> \vdots 2)
(Доказательство: почти закончено)
Строка 54: Строка 54:
 
'''Утверждение 1.''' Можно перечислить (возможно с повторениями) все языки из <math>P</math>.
 
'''Утверждение 1.''' Можно перечислить (возможно с повторениями) все языки из <math>P</math>.
  
Действительно, рассмотрим последовательность всех программ  
+
Действительно, рассмотрим последовательность всех программ, упорядоченных по длине,
<math> \tilde{p_1}, \tilde{p_2}, \ldots, \tilde{p_n}, \ldots</math>
+
<math> \tilde{p_0}, \tilde{p_1}, \ldots, \tilde{p_n}, \ldots</math>
 
Обозначим за <math>p_i</math> программу, запускающую <math>\tilde{p_i}</math>
 
Обозначим за <math>p_i</math> программу, запускающую <math>\tilde{p_i}</math>
 
с таймером <math>in^i</math>. Тогда среди <math>{p_i}</math> встречаются
 
с таймером <math>in^i</math>. Тогда среди <math>{p_i}</math> встречаются
Строка 74: Строка 74:
 
<math>f(0) = f(1) = 0</math>
 
<math>f(0) = f(1) = 0</math>
  
Определим <math>f(n)</math>. Для этого рассмотрим два случая:
+
Определим <math>f(n)</math>. Для этого рассмотрим три случая:
*'''Случай 1:''' <math>f(n-1)=2i</math>.
+
#<math>{\log_2 n} ^ {f(n-1)} \ge n</math>.
*: Если существует <math>x</math>, такой что <math>|x| < \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>.
+
#:<math>f(n) = f(n-1)</math>.
*'''Случай 2:''' <math>f(n-1)=2i+1</math>.
+
#<math>f(n-1)=2i</math>.
*:Если существует <math>x</math>, такой что <math>|x| < \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>x</math>, такой что <math>|x| < \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>.
 +
#<math>f(n-1)=2i+1</math>.
 +
#:Если существует <math>x</math>, такой что <math>|x| < \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>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) = 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>T(n-1)</math> идёт на вычисление <math>f(n-1)</math>;
Строка 89: Строка 93:
 
*<math>b_4(n)</math> — запуск <math>L(f_i(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>p_i</math>;
*<math>c_1(n)</math> — построение программы <math>f_i</math>.
+
*<math>c_2(n)</math> — построение программы <math>f_i</math>.
  
<math>a(n) \approx 2^{log_2 n} = n</math>, таким образом <math>a(n) \in \tilde{P}</math>
+
<math>a(n) = O\left(2^{\log_2 n}\right) = O(n)</math>, таким образом <math>a(n) \in \tilde{P}</math>
  
<math>b_1(n) \approx</math> что-то, тоже из <math>\tilde{P}</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>\tilde{P}</math>
  
<math>b_2(n) \approx 2^{log_2 n} log_2 n </math>, из <math>\tilde{P}</math>
+
<math>b_2(n) = O \left( 2^{\log_2 n} \log_2 n\right) = O\left(n \log_2 n\right)</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_3(n) = O \left(2^{\log_2 n} \log_2 n + \log_2 n\right) = O \left(n \log_2 n\right)</math> из <math>\tilde{P}</math>
  
<math>b_4(n) \approx </math> что-то типа <math>b_3(n)</math>, но с оценкой на <math>|f_i(x)|</math>
+
<math>b_4(n) = O(b3(n))</math> из <math>\tilde{P}</math>
вместо <math>log_2 n</math>, из <math>\tilde{P}</math>
 
  
<math>c_1(n)</math> и <math>c_2(n)</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}</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) = 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>.
 
Поэтому <math>T(n) \in \tilde{P}</math> и <math>A \in P</math>.
  
В результате всё почти хорошо.
+
Таким образом, <math>f</math> полиномиальна, а значит <math>A \in P</math>.
 +
 
 +
Предположим, что <math>\lim_{n \to \infty}f(n) = 2i</math>. Это значит, что фунция «застряла» в ветке «иначе» случая два,
 +
но из этого следует, что <math>SAT</math> отличается от <math>L(p_i)</math> лишь на конечное число элементов. Это
 +
влечёт за собой принадлежность <math>SAT</math> к <math>P</math>, что противоречит предположению <math>P \ne NP</math>.
 +
 
 +
Аналогично, в случае, если <math>\lim_{n \to \infty}f(n) = 2i+1</math>. Тогда функция «застряла» в ветке «иначе» случая три.
 +
Следствием этого является то, что <math>SAT</math> функцией <math>p_i</math> сводится к конечному множеству, что тоже
 +
противоречит предположению <math>P \ne 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>SAT</math> к <math>L</math>.  Следовательно, выполняются все три пункта, и <math>L</math> является примером
 +
языка из <math>NP\setminus(P \cup NPC)</math>.
  
 
Теорема доказана.
 
Теорема доказана.

Версия 00:00, 7 марта 2010

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

Теорема Ладнера (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], удовлетворяющий следующим условиям:

  1. [math]A \in P[/math] (что влечёт за собой[math]SAT \cap A \in NP[/math])
  2. [math]SAT \cap A \not\in P[/math]
  3. [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_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]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]{\log_2 n} ^ {f(n-1)} \ge n[/math].
    [math]f(n) = f(n-1)[/math].
  2. [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].
  3. [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_2(n)[/math] — построение программы [math]f_i[/math].

[math]a(n) = O\left(2^{\log_2 n}\right) = O(n)[/math], таким образом [math]a(n) \in \tilde{P}[/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]\tilde{P}[/math]

[math]b_2(n) = O \left( 2^{\log_2 n} \log_2 n\right) = O\left(n \log_2 n\right)[/math] — из [math]\tilde{P}[/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)[/math] — из [math]\tilde{P}[/math]

[math]b_4(n) = O(b3(n))[/math] — из [math]\tilde{P}[/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}[/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{P}[/math] и [math]A \in P[/math].

Таким образом, [math]f[/math] полиномиальна, а значит [math]A \in P[/math].

Предположим, что [math]\lim_{n \to \infty}f(n) = 2i[/math]. Это значит, что фунция «застряла» в ветке «иначе» случая два, но из этого следует, что [math]SAT[/math] отличается от [math]L(p_i)[/math] лишь на конечное число элементов. Это влечёт за собой принадлежность [math]SAT[/math] к [math]P[/math], что противоречит предположению [math]P \ne NP[/math].

Аналогично, в случае, если [math]\lim_{n \to \infty}f(n) = 2i+1[/math]. Тогда функция «застряла» в ветке «иначе» случая три. Следствием этого является то, что [math]SAT[/math] функцией [math]p_i[/math] сводится к конечному множеству, что тоже противоречит предположению [math]P \ne 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]SAT[/math] к [math]L[/math]. Следовательно, выполняются все три пункта, и [math]L[/math] является примером языка из [math]NP\setminus(P \cup NPC)[/math].

Теорема доказана.