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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
'''Теорема Ладнера''' (Ladner's Theorem) утверждает,
+
'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся полиномиальным и [[NP-полнота|NP-полным]].
что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык <tex>L</tex>,
 
принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся полиномиальным и [[NP-полнота|NP-полным]].
 
  
==Иллюстрация==
+
== Доказательство ==
  
Определим язык <tex>A</tex> как множество таких формул <tex>\alpha</tex>,
+
Предположим, что <tex>\mathrm{P} \neq \mathrm{NP}</tex>. Из этого следует, что <tex>\mathrm{NP}</tex>-полный язык (например, <tex>\mathrm{SAT}</tex>) нельзя свести по Карпу к полиномиальному. Будем искать язык <tex>A</tex>, удовлетворяющий следующим условиям:
что <tex>\left\lfloor \frac{1}{2}\log_{10}^*|\alpha|\right\rfloor</tex> чётно.
 
Иными словами, <tex>A</tex> — это язык формул с длинами, лежащими в промежутках
 
<tex>\left[1,10^{10}\right),
 
\left[\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_4,
 
\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_6\right), \ldots</tex>
 
Далее будем обозначать <tex>\underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_n</tex>
 
как <tex>^{n}a</tex>.
 
  
Рассмотрим язык [[SAT]] всех удовлетворимых формул. Логично предположить, что как в <tex>A</tex>,
+
# <tex>A \in \mathrm{P}</tex> (что влечёт за собой <tex>\mathrm{SAT} \cap A \in \mathrm{NP}</tex>);
так и в <tex>\bar{A}</tex> лежит бесконечное множество элементов из <tex>\mathrm{SAT}</tex>,
+
# <tex>\mathrm{SAT} \cap A \not \in \mathrm{P}</tex>;
не распознаваемых за полиномиальное время, поэтому <tex>\mathrm{SAT} \cap A \not\in \mathrm{P}</tex>.
+
# <tex>\mathrm{SAT} \not \le \mathrm{SAT} \cap A</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-полным. Пусть
+
Если такой язык существует, то <tex>L = \mathrm{SAT} \cap A</tex> является искомым примером множества
это не так. Тогда из NP-полноты следует, что существует полиномиальная функция <math>f</math>,
+
из <tex>\mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC})</tex>.
[[Сведение по Карпу|сводящая по Карпу]] <tex>\mathrm{SAT}</tex> к <tex>\mathrm{SAT} \cap A</tex>.
+
 
 +
Пусть <tex>M_1, \ldots, M_n, \ldots</tex> — все машины Тьюринга из <tex>\tilde{\mathrm{P}}</tex>, причём <tex>T(M_i(x)) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>.
 +
 
 +
Пусть <tex>f_1, \ldots, f_n, \ldots</tex> — аналогичное множество полиномиальных функций: <tex>T(f_i(x)) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>.
 +
 
 +
Для простоты будем считать, что <tex>|\Sigma| = 2</tex>. Построим такую неубывающую функцию <tex>g \in \tilde{\mathrm{P}}</tex>, что для <tex>A = \{x \in \Sigma^*: g(|x|) \% 2 = 0\}</tex> выполняются три названных свойства.
 +
 
 +
=== Построение <tex>g</tex> ===
 +
 
 +
Определим <tex>g</tex> рекурсивно. Установим <tex>g(0) = g(1) = 1</tex>. Для <tex>n \ge 1</tex>:
 +
 
 +
* Если <tex>log_2^{g(n)} n \ge n</tex>, <tex>g(n+1) := g(n)</tex>.
 +
 
 +
Иначе <tex> n > log_2^{g(n)} n \ge log_2 n</tex>; значения <tex>g(m)</tex> для <tex>m \le log_2 n</tex> уже известны.
 +
 
 +
* <tex>g(n) = 2i</tex>.
 +
for <tex>x</tex>: <tex>|x| \le log_2 n</tex>
 +
  if <tex>M_i(x)</tex> and (<tex>g(|x|) \% 2 = 1</tex> or <tex>x \not \in \mathrm{SAT})</tex>
 +
    <tex>g(n+1) := g(n)+1</tex>, return
 +
  if <tex>! M_i(x)</tex> and (<tex>g(|x|) \% 2 = 0</tex> and <tex>x \in \mathrm{SAT})</tex>
 +
    <tex>g(n+1) := g(n)+1</tex>, return
 +
  <tex>g(n+1) := g(n)</tex>
  
Возьмём формулу <tex>\varphi</tex> длиной <tex>^{4k+3}10</tex>.  
+
* <tex>g(n) = 2i + 1</tex>.
Она не лежит в <tex>A</tex> и, следовательно, в <tex>\mathrm{SAT} \cap A</tex>.
+
for <tex>x</tex>: <tex>|x| \le log_2 n, |f_i(x)| \le log_2 n</tex>
Функция <tex>f</tex> не может перевести <tex>\varphi</tex> в промежуток
+
  if <tex>x \in \mathrm{SAT}</tex> and (<tex>g(|f_i(x)|) \% 2 = 1</tex> or <tex>f_i(x) \not \in \mathrm{SAT})</tex>
<tex>\left[^{4k+4}10, ^{4k+6}10\right)</tex> или дальше, так как размер
+
    <tex>g(n+1) := g(n)+1</tex>, return
выхода полиномиальной функции не может быть экспоненциально больше длины
+
  if <tex>x \not \in \mathrm{SAT}</tex> and (<tex>g(|f_i(x)|) \% 2 = 0</tex> and <tex>f_i(x) \in \mathrm{SAT})</tex>
входа. Значит, <tex>\varphi</tex> отображается в меньший промежуток, но
+
    <tex>g(n+1) := g(n)+1</tex>, return
в этом случае размер выхода экспоненциально меньше длины входа.  Добавляя
+
  <tex>g(n+1) := g(n)</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>^{4k+3}10</tex> принадлежат классу
 
<tex>\mathrm{P}</tex>, скорее всего не верно, и, следовательно, язык
 
<tex>\mathrm{SAT} \cap A</tex> не является NP-полным.
 
  
Заметим, что это объяснение не является доказательством!
+
Утверждается, что для такой функции <tex>g</tex> язык <tex>A = \{x \in \Sigma^*: g(|x|) \% 2 = 0\}</tex> является искомым.
  
==Доказательство==
+
=== Корректность алгоритма ===
Будем искать язык <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>L = \mathrm{SAT} \cap A</tex>.
из <tex>\mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC})</tex>.
+
 
 +
* Пусть <tex>g(n)</tex> не имеет предела при <tex>n \to \infty</tex>. Значит, для любой <tex>M_i</tex> в <tex>L</tex> существует элемент, на котором <tex>M_i</tex> «ошибается»; аналогично, для любой полиномиальной функции <tex>f_i</tex> существует элемент, на котором <tex>f_i</tex> неверно сводит <tex>\mathrm{SAT}</tex> к <tex>L</tex>. Оба свойства выполнены.
 +
 
 +
* Пусть <tex>\lim_{n \to +\infty} g(n) = 2i</tex>. Значит, в нашем множестве существует машина Тьюринга <tex>M_i</tex>, распознающая <tex>L</tex>: <tex>\forall x M_i(x) = (g(|x|) \% 2 = 0 \cap x \in \mathrm{SAT})</tex>. С одной стороны, <tex>M_i</tex> работает за полином, и <tex>L \in \mathrm{P}</tex>. С другой стороны, по определению <tex>A</tex>, <tex>L</tex> различается с <tex>\mathrm{SAT}</tex> в конечном числе элементов, значит, <tex>\mathrm{SAT} \le L</tex>. Получено противоречие с предположением <tex>\mathrm{P} \neq \mathrm{NP}</tex>.
 +
 
 +
* Пусть <tex>\lim_{n \to +\infty} g(n) = 2i + 1</tex>. Тогда в нашем множестве полиномиальных функций существует <tex>f_i</tex>: <tex>\forall x (x \in SAT) = (g(|f_i(x)|) \% 2 = 0 \cap f_i(x) \in \mathrm{SAT})</tex>. С одной стороны, <tex>\mathrm{SAT} \le L</tex> с помощью <tex>f_i</tex>. С другой стороны, из определения <tex>A</tex> выходит, что язык <tex>L</tex> конечен, значит, <tex>L \in \mathrm{P}</tex>. Снова получено противоречие с предположением.
 +
 
 +
Таким образом, при верности предположения <tex>\mathrm{P} \neq \mathrm{NP}</tex> второе и третье свойства <tex>L</tex> выполнены.
 +
 
 +
=== Время работы алгоритма ===
 +
 
 +
Проверим первое свойство — полиномиальность языка <tex>A</tex>.
 +
 
 +
Пусть <tex>T_g(n)</tex> — время вычисления <tex>g(n)</tex>.
 +
 
 +
Заметим, что <tex>g(n) \le n</tex> по построению для <tex>n \ge 1</tex>.
 +
 
 +
Время выполнения шагов составляет:
 +
 
 +
* проверка неравенства:
 +
 
 +
<tex>T_1(n) \le g(n) T_*(log_2^{g(n)} n, log_2^{g(n)} n)</tex>
  
===Утверждение 1===
+
<tex>T_1(n) \le c_1 g(n) (log_2 (log_2^{g(n)} n))^2</tex>
Можно перечислить (возможно, с повторениями) все языки из <tex>\mathrm{P}</tex>.
 
  
Действительно, рассмотрим последовательность всех программ, упорядоченных по длине:
+
<tex>T_1(n) \le c_1 g^3(n) log_2^2 log_2 n</tex>
<tex> \tilde{p_0}, \tilde{p_1}, \ldots, \tilde{p_n}, \ldots</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>
 
и <tex>\tilde{p_j}</tex> делает то же самое, что и <tex>\tilde{p_i}</tex>.
 
Таким образом, <tex>p_j</tex> распознает тот же язык, что и <tex>\tilde{p_i}</tex>.
 
  
===Утверждение 2===
+
<tex>T_1(n) \le c_1 n^3 log_2^2 log_2 n</tex>
Можно перечислить все функции из <tex>\tilde{\mathrm{P}}</tex>.
 
  
Аналогично предыдущему доказательству, сначала построим последовательность <tex>\tilde{f_i}</tex>, а затем, добавив таймер <tex>in^i</tex>, получим последовательность <tex>f_i</tex>.
+
<tex>T_1(n) \le c_1 n^5</tex>,
  
===Описание способа построения <tex>A</tex>===
+
где <tex>T_*(a, b)</tex> — время нахождения произведения чисел <tex>a</tex> и <tex>b</tex>
Упорядочим все слова по возрастанию длины. Разобьем всё <tex>\Sigma^{*}</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>g(n) = 2i</tex>:
  
Если мы сможем построить такие <tex>A_i</tex>, то язык <tex>L = \mathrm{SAT} \cap \bigcup_{i=0}^{\infty} A_{2i}</tex>
+
<tex>T_2(n) \le 2^{log_2 n} (T(M_i(x)) + T(g(|x|)) + T(x \in \mathrm{SAT}))</tex>
будет отличаться от любого полиномиального языка, и ни одна полиномиальная функция не будет сводить
 
<tex>\mathrm{SAT}</tex> к <tex>L</tex>.
 
  
Попытаемся построить такую полиномиальную функцию <tex>f</tex>, что
+
<tex>T_2(n) \le c_2 n (|x|^i + T_g(|x|) + 2^{|x|}|x|)</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>T_2(n) \le c_2 n (log_2^{i} n + T_g(|x|) + 2^{log_2 n} log_2 n)</tex>
Зададим <tex>f(0) = f(1) = 0</tex>. Затем рекурсивно определим <tex>f(n)</tex>. Для этого рассмотрим три случая:
 
*<tex>(\log_2 n) ^ {f(n-1)} \ge n</tex>:
 
*:<tex>f(n) = f(n-1)</tex>;
 
*<tex>f(n-1)=2i</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>T_2(n) \le c_2 n (log_2^{g(n)} n + T_g(log_2 n) + n log_2 n)</tex>
  
Первый случай позволяет сказать, что <tex>f(n)</tex> ограничена <tex>O\left(\log_{\log_2 n} n\right) = O(\log_2 n)</tex>.
+
<tex>T_2(n) \le c_2 (n^2 + n^2 log_2 n + n T_g(log_2 n))</tex>
Второй «ответственен» за множества <tex>A_i</tex> для чётных <tex>i</tex>, третий — для нечетных.
 
Логарифм в условии <tex>|x| < \log_2 n</tex> необходим для полиномиальности <tex>f(n)</tex>.
 
  
===Полиномиальность <tex>f</tex>===
+
<tex>T_2(n) \le c_2 (2n^3 + n T_g(log_2 n))</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>g(n) = 2i + 1</tex>:
*<tex>T(n-1)</tex> идёт на вычисление <tex>f(n-1)</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>c_1(n)</tex> — время, необходимое для построения программы <tex>p_i</tex>;
 
*<tex>c_2(n)</tex> — время, необходимое для построения функции <tex>f_i</tex>.
 
  
<tex>a(n) = O\left(2^{\log_2 n}\right) = O(n)</tex>, таким образом <tex>a(n)</tex>.
+
<tex>T_3(n) \le 2^{log_2 n} (T(x \in \mathrm{SAT}) + T_g(|f_i(x)|) + T(f_i(x) \in \mathrm{SAT}))</tex>
  
<tex>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)</tex>
+
<tex>T_3(n) \le c_3 n (2^{log_2 n} log_2 n + T_g(log_2 n) + 2^{log_2 n} log_2 n)</tex>
  
<tex>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)</tex>
+
<tex>T_3(n) \le c_3 (2n^2 log_2 n + n T_g(log_2 n))</tex>
  
<tex>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)</tex>
+
<tex>T_3(n) \le c_3 (2n^3 + n T_g(log_2 n))</tex>
  
<tex>b_4(n) = b_3(b_1(n)) = O\left(n^4\right)</tex>
+
Таким образом,
  
Чтобы построить программу <tex>p_i</tex> достаточно построить <tex>\tilde{p_i}</tex>.
+
<tex>T_g(n) \le T_g(n-1) + c_1 n^5 + c_2 (2n^3 + n T_g(log_2 n)) + c_3 (2n^3 + n T_g(log_2 n))</tex>
Из того, что все <tex>\tilde{p_i}</tex> упорядочены по длине, следует, что длина
 
<tex>\tilde{p_i}</tex> не превосходит <tex>ci</tex> (константа зависит от языка описания программы).
 
Поэтому для построения i-ой программы достаточно перебрать все <tex>2^{ci+1}-1</tex> слов с длиной не больше <tex>ci</tex>
 
и вывести i-ое, являющееся программой. Такой способ требует <tex>O(2^{ci}i) = O(2^{\log_2 n} \log_2 n) = O(n^2)</tex> времени.
 
Аналогично можно построить и <tex>f_i</tex>. Из этого следует, что <tex>c_1(n)</tex> и <tex>c_2(n)</tex> тоже полиномиальны.
 
  
Получаем, что <tex>T(n) = T(n-1) + poly</tex>. Значит, <tex>T(n) \le n \cdot poly </tex>.
+
<tex>T_g(n) \le T_g(n-1) + k_1 n^5 + k_2 n T_g(log_2 n)</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>g(n)</tex> на ленте машины Тьюринга в порядке возрастания <tex>n</tex>, <tex>T_g(log_2 n)</tex> можно получить за <tex>k_3 (n + log_2 n) \le 2 k_3 n</tex>. Тогда
  
===Доказательство выполнения свойств <tex>A</tex>===
+
<tex>T_g(n) \le T_g(n-1) + k_1 n^5 + 2 k_2 k_3 n^2</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>T_g(1) = const = d</tex>. Существует константа <tex>c \ge d</tex>, для которой при любом <tex>n</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>c (n-1)^6 + k_1 n^5 + 2 k_2 k_3 n^2 \le c n^6</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>.
 
  
Теорема доказана.
+
Тогда, в силу <tex>T_g(1) = d \le c 1^6</tex> и неравенства выше, по индукции легко доказать, что <tex>T_g(n)</tex> ограничено сверху <tex>c n^6</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.
  
==Источники==
+
== Источник ==
* ''Rafael Pass''. [http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture2.pdf Theory of Computing. Lecture 2: Diagonalization]
+
* ''William Gasarch, Lance Fortnow''. [http://blog.computationalcomplexity.org/media/ladner.pdf Two Proofs of Ladner’s Theorem]

Версия 21:14, 20 мая 2012

Теорема Ладнера (Ladner's Theorem) утверждает, что если P не совпадает с NP, то существует язык, принадлежащий [math]\mathrm{NP}[/math], но не являющийся полиномиальным и NP-полным.

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

Предположим, что [math]\mathrm{P} \neq \mathrm{NP}[/math]. Из этого следует, что [math]\mathrm{NP}[/math]-полный язык (например, [math]\mathrm{SAT}[/math]) нельзя свести по Карпу к полиномиальному. Будем искать язык [math]A[/math], удовлетворяющий следующим условиям:

  1. [math]A \in \mathrm{P}[/math] (что влечёт за собой [math]\mathrm{SAT} \cap A \in \mathrm{NP}[/math]);
  2. [math]\mathrm{SAT} \cap A \not \in \mathrm{P}[/math];
  3. [math]\mathrm{SAT} \not \le \mathrm{SAT} \cap A[/math].

Если такой язык существует, то [math]L = \mathrm{SAT} \cap A[/math] является искомым примером множества из [math]\mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC})[/math].

Пусть [math]M_1, \ldots, M_n, \ldots[/math] — все машины Тьюринга из [math]\tilde{\mathrm{P}}[/math], причём [math]T(M_i(x)) \le |x|^i[/math] для любого [math]x \in \Sigma^*[/math].

Пусть [math]f_1, \ldots, f_n, \ldots[/math] — аналогичное множество полиномиальных функций: [math]T(f_i(x)) \le |x|^i[/math] для любого [math]x \in \Sigma^*[/math].

Для простоты будем считать, что [math]|\Sigma| = 2[/math]. Построим такую неубывающую функцию [math]g \in \tilde{\mathrm{P}}[/math], что для [math]A = \{x \in \Sigma^*: g(|x|) \% 2 = 0\}[/math] выполняются три названных свойства.

Построение [math]g[/math]

Определим [math]g[/math] рекурсивно. Установим [math]g(0) = g(1) = 1[/math]. Для [math]n \ge 1[/math]:

  • Если [math]log_2^{g(n)} n \ge n[/math], [math]g(n+1) := g(n)[/math].

Иначе [math] n \gt log_2^{g(n)} n \ge log_2 n[/math]; значения [math]g(m)[/math] для [math]m \le log_2 n[/math] уже известны.

  • [math]g(n) = 2i[/math].
for [math]x[/math]: [math]|x| \le log_2 n[/math]
  if [math]M_i(x)[/math] and ([math]g(|x|) \% 2 = 1[/math] or [math]x \not \in \mathrm{SAT})[/math]
    [math]g(n+1) := g(n)+1[/math], return
  if [math]! M_i(x)[/math] and ([math]g(|x|) \% 2 = 0[/math] and [math]x \in \mathrm{SAT})[/math]
    [math]g(n+1) := g(n)+1[/math], return
  [math]g(n+1) := g(n)[/math]
  • [math]g(n) = 2i + 1[/math].
for [math]x[/math]: [math]|x| \le log_2 n, |f_i(x)| \le log_2 n[/math]
  if [math]x \in \mathrm{SAT}[/math] and ([math]g(|f_i(x)|) \% 2 = 1[/math] or [math]f_i(x) \not \in \mathrm{SAT})[/math]
    [math]g(n+1) := g(n)+1[/math], return
  if [math]x \not \in \mathrm{SAT}[/math] and ([math]g(|f_i(x)|) \% 2 = 0[/math] and [math]f_i(x) \in \mathrm{SAT})[/math]
    [math]g(n+1) := g(n)+1[/math], return
  [math]g(n+1) := g(n)[/math]

Утверждается, что для такой функции [math]g[/math] язык [math]A = \{x \in \Sigma^*: g(|x|) \% 2 = 0\}[/math] является искомым.

Корректность алгоритма

Проверим выполнение второго и третьего свойств языка [math]L = \mathrm{SAT} \cap A[/math].

  • Пусть [math]g(n)[/math] не имеет предела при [math]n \to \infty[/math]. Значит, для любой [math]M_i[/math] в [math]L[/math] существует элемент, на котором [math]M_i[/math] «ошибается»; аналогично, для любой полиномиальной функции [math]f_i[/math] существует элемент, на котором [math]f_i[/math] неверно сводит [math]\mathrm{SAT}[/math] к [math]L[/math]. Оба свойства выполнены.
  • Пусть [math]\lim_{n \to +\infty} g(n) = 2i[/math]. Значит, в нашем множестве существует машина Тьюринга [math]M_i[/math], распознающая [math]L[/math]: [math]\forall x M_i(x) = (g(|x|) \% 2 = 0 \cap x \in \mathrm{SAT})[/math]. С одной стороны, [math]M_i[/math] работает за полином, и [math]L \in \mathrm{P}[/math]. С другой стороны, по определению [math]A[/math], [math]L[/math] различается с [math]\mathrm{SAT}[/math] в конечном числе элементов, значит, [math]\mathrm{SAT} \le L[/math]. Получено противоречие с предположением [math]\mathrm{P} \neq \mathrm{NP}[/math].
  • Пусть [math]\lim_{n \to +\infty} g(n) = 2i + 1[/math]. Тогда в нашем множестве полиномиальных функций существует [math]f_i[/math]: [math]\forall x (x \in SAT) = (g(|f_i(x)|) \% 2 = 0 \cap f_i(x) \in \mathrm{SAT})[/math]. С одной стороны, [math]\mathrm{SAT} \le L[/math] с помощью [math]f_i[/math]. С другой стороны, из определения [math]A[/math] выходит, что язык [math]L[/math] конечен, значит, [math]L \in \mathrm{P}[/math]. Снова получено противоречие с предположением.

Таким образом, при верности предположения [math]\mathrm{P} \neq \mathrm{NP}[/math] второе и третье свойства [math]L[/math] выполнены.

Время работы алгоритма

Проверим первое свойство — полиномиальность языка [math]A[/math].

Пусть [math]T_g(n)[/math] — время вычисления [math]g(n)[/math].

Заметим, что [math]g(n) \le n[/math] по построению для [math]n \ge 1[/math].

Время выполнения шагов составляет:

  • проверка неравенства:

[math]T_1(n) \le g(n) T_*(log_2^{g(n)} n, log_2^{g(n)} n)[/math]

[math]T_1(n) \le c_1 g(n) (log_2 (log_2^{g(n)} n))^2[/math]

[math]T_1(n) \le c_1 g^3(n) log_2^2 log_2 n[/math]

[math]T_1(n) \le c_1 n^3 log_2^2 log_2 n[/math]

[math]T_1(n) \le c_1 n^5[/math],

где [math]T_*(a, b)[/math] — время нахождения произведения чисел [math]a[/math] и [math]b[/math]

  • [math]g(n) = 2i[/math]:

[math]T_2(n) \le 2^{log_2 n} (T(M_i(x)) + T(g(|x|)) + T(x \in \mathrm{SAT}))[/math]

[math]T_2(n) \le c_2 n (|x|^i + T_g(|x|) + 2^{|x|}|x|)[/math]

[math]T_2(n) \le c_2 n (log_2^{i} n + T_g(|x|) + 2^{log_2 n} log_2 n)[/math]

[math]T_2(n) \le c_2 n (log_2^{g(n)} n + T_g(log_2 n) + n log_2 n)[/math]

[math]T_2(n) \le c_2 (n^2 + n^2 log_2 n + n T_g(log_2 n))[/math]

[math]T_2(n) \le c_2 (2n^3 + n T_g(log_2 n))[/math]

  • [math]g(n) = 2i + 1[/math]:

[math]T_3(n) \le 2^{log_2 n} (T(x \in \mathrm{SAT}) + T_g(|f_i(x)|) + T(f_i(x) \in \mathrm{SAT}))[/math]

[math]T_3(n) \le c_3 n (2^{log_2 n} log_2 n + T_g(log_2 n) + 2^{log_2 n} log_2 n)[/math]

[math]T_3(n) \le c_3 (2n^2 log_2 n + n T_g(log_2 n))[/math]

[math]T_3(n) \le c_3 (2n^3 + n T_g(log_2 n))[/math]

Таким образом,

[math]T_g(n) \le T_g(n-1) + c_1 n^5 + c_2 (2n^3 + n T_g(log_2 n)) + c_3 (2n^3 + n T_g(log_2 n))[/math]

[math]T_g(n) \le T_g(n-1) + k_1 n^5 + k_2 n T_g(log_2 n)[/math]

Если выписывать полученные значения [math]g(n)[/math] на ленте машины Тьюринга в порядке возрастания [math]n[/math], [math]T_g(log_2 n)[/math] можно получить за [math]k_3 (n + log_2 n) \le 2 k_3 n[/math]. Тогда

[math]T_g(n) \le T_g(n-1) + k_1 n^5 + 2 k_2 k_3 n^2[/math]

Пусть [math]T_g(1) = const = d[/math]. Существует константа [math]c \ge d[/math], для которой при любом [math]n[/math] верно

[math]c (n-1)^6 + k_1 n^5 + 2 k_2 k_3 n^2 \le c n^6[/math]

Тогда, в силу [math]T_g(1) = d \le c 1^6[/math] и неравенства выше, по индукции легко доказать, что [math]T_g(n)[/math] ограничено сверху [math]c n^6[/math], то есть [math]g \in \tilde{\mathrm{P}}[/math], а, в свою очередь, [math]A \in \mathrm{P}[/math].

Источник