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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Иллюстрация)
м (rollbackEdits.php mass rollback)
 
(не показано 59 промежуточных версий 12 участников)
Строка 1: Строка 1:
'''Теорема Ладнера''' (Ladner's Theorem) утверждает,
+
'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным, ни [[NP-полнота|NP-полным]].
что если [[P]] не совпадает с [[NP]], то существует язык <tex>L</tex>,
 
принадлежащий <tex>NP</tex>, но не являющийся полиномиальным и [[NP-полнота|NP-полным]].
 
  
==Иллюстрация==
+
== Иллюстрация ==
  
 
Определим язык <tex>A</tex> как множество таких формул <tex>\alpha</tex>,
 
Определим язык <tex>A</tex> как множество таких формул <tex>\alpha</tex>,
 
что <tex>\left\lfloor \frac{1}{2}\log_{10}^*|\alpha|\right\rfloor</tex> чётно.
 
что <tex>\left\lfloor \frac{1}{2}\log_{10}^*|\alpha|\right\rfloor</tex> чётно.
 
Иными словами, <tex>A</tex> — это язык формул с длинами, лежащими в промежутках  
 
Иными словами, <tex>A</tex> — это язык формул с длинами, лежащими в промежутках  
<math>\left[1,10^{10}\right),
+
<tex>\left[1,10^{10}\right),
 
\left[\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_4,
 
\left[\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_4,
\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_6\right), \ldots</math>
+
\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_6\right), \ldots</tex>
 
Далее будем обозначать <tex>\underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_n</tex>
 
Далее будем обозначать <tex>\underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_n</tex>
 
как <tex>^{n}a</tex>.
 
как <tex>^{n}a</tex>.
  
 
Рассмотрим язык [[SAT]] всех удовлетворимых формул. Логично предположить, что как в <tex>A</tex>,
 
Рассмотрим язык [[SAT]] всех удовлетворимых формул. Логично предположить, что как в <tex>A</tex>,
так и в <tex>\bar{A}</tex> лежит бесконечное множество элементов из <tex>SAT</tex>,
+
так и в <tex>\bar{A}</tex> лежит бесконечное множество элементов из <tex>\mathrm{SAT}</tex>,
не распознаваемых за полиномиальное время, поэтому <tex>SAT \cap A \not\in P</tex>.
+
не распознаваемых за полиномиальное время, поэтому <tex>\mathrm{SAT} \cap A \not\in \mathrm{P}</tex>.
Из <tex>A \in P</tex> и <tex>SAT \in NP</tex> следует, что <tex>SAT \cap A \in NP</tex>.
+
Из <tex>A \in \mathrm{P}</tex> и <tex>\mathrm{SAT} \in \mathrm{NP}</tex> следует, что <tex>\mathrm{SAT} \cap A \in \mathrm{NP}</tex>.
  
Осталось показать, что <tex>SAT \cap A</tex> не является NP-полным. Пусть
+
Осталось показать, что <tex>\mathrm{SAT} \cap A</tex> не является NP-полным. Пусть
 
это не так. Тогда из NP-полноты следует, что существует полиномиальная функция <math>f</math>,
 
это не так. Тогда из NP-полноты следует, что существует полиномиальная функция <math>f</math>,
[[Сведение по Карпу|сводящая по Карпу]] <tex>SAT</tex> к <tex>SAT \cap A</tex>.  
+
[[Сведение по Карпу|сводящая по Карпу]] <tex>\mathrm{SAT}</tex> к <tex>\mathrm{SAT} \cap A</tex>.  
  
 
Возьмём формулу <tex>\varphi</tex> длиной <tex>^{2k+1}10</tex>.  
 
Возьмём формулу <tex>\varphi</tex> длиной <tex>^{2k+1}10</tex>.  
Она не лежит в <tex>A</tex> и, следовательно, в <tex>SAT \cap A</tex>.
+
Она не лежит в <tex>A</tex> и, следовательно, в <tex>\mathrm{SAT} \cap A</tex>.
 
Функция <tex>f</tex> не может перевести <tex>\varphi</tex> в промежуток
 
Функция <tex>f</tex> не может перевести <tex>\varphi</tex> в промежуток
 
<tex>\left[^{2k+2}10, ^{2k+4}10\right)</tex> или дальше, так как размер
 
<tex>\left[^{2k+2}10, ^{2k+4}10\right)</tex> или дальше, так как размер
Строка 31: Строка 29:
 
в этом случае размер выхода экспоненциально меньше длины входа.  Добавляя
 
в этом случае размер выхода экспоненциально меньше длины входа.  Добавляя
 
к этому то, что проверку на принадлежность <tex>f(\varphi)</tex> к
 
к этому то, что проверку на принадлежность <tex>f(\varphi)</tex> к
<tex>SAT \cap A</tex> можно осуществить за <tex>O(2^{poly})</tex>
+
<tex>\mathrm{SAT} \cap A</tex> можно осуществить за <tex>O(2^{poly})</tex>
(это следует из её принадлежности классу <tex>NP</tex>), получаем программу,
+
(это следует из её принадлежности классу <tex>\mathrm{NP}</tex>), получаем программу,
 
разрешающую <tex>\varphi</tex> за полином. Утверждение о том, что все формулы
 
разрешающую <tex>\varphi</tex> за полином. Утверждение о том, что все формулы
 
<tex>\varphi</tex> длиной <tex>^{2k+1}10</tex> принадлежат классу
 
<tex>\varphi</tex> длиной <tex>^{2k+1}10</tex> принадлежат классу
<tex>P</tex>, скорее всего не верно, и, следовательно, язык  
+
<tex>\mathrm{P}</tex>, скорее всего неверно, и, следовательно, язык  
<tex>SAT \cap A</tex> не является NP-полным.
+
<tex>\mathrm{SAT} \cap A</tex> не является NP-полным.
  
 
Заметим, что это объяснение не является доказательством!
 
Заметим, что это объяснение не является доказательством!
  
==Доказательство==
+
== Теорема ==
Будем искать язык <tex>A</tex>, удовлетворяющий следующим условиям:
 
#<tex>A \in P</tex> (что влечёт за собой<tex>SAT \cap A \in NP</tex>);
 
#<tex>SAT \cap A \not\in P</tex>;
 
#<tex>SAT \not \leq SAT \cap A</tex>.
 
  
Если такой язык существует, то <tex>L = SAT \cap A</tex> является искомым примером множества
+
{{Теорема
из <tex>NP \setminus (P \cup NPC)</tex>.
+
|author=Ладнер
 +
|statement=
 +
<tex>\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \varnothing</tex>.
 +
|proof=
 +
Предположим, что <tex>\mathrm{P} \neq \mathrm{NP}</tex>. Из этого следует, что никакой <tex>\mathrm{NP}</tex>-полный язык (например, [[Примеры NP-полных_языков. Теорема_Кука#NP-полнота_2|SAT]]) нельзя [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|свести по Карпу]] к полиномиальному. Будем искать такой язык <tex>A</tex>, чтобы язык <tex>L = \mathrm{SAT} \cap A</tex> удовлетворял следующим условиям:
  
===Утверждение 1===
+
# <tex>L \in \mathrm{NP}</tex> (для этого достаточно, чтобы выполнялось <tex>A \in \mathrm{P}</tex>);
Можно перечислить (возможно, с повторениями) все языки из <tex>P</tex>.
+
# <tex>L \not \in \mathrm{P}</tex>;
 +
# <tex>\mathrm{SAT} \not \le L</tex>.
  
Действительно, рассмотрим последовательность всех программ, упорядоченных по длине:
+
Если выполнены все три свойства, то <tex>L \in \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC})</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>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>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>\tilde{P}</tex>.
 
  
Аналогично предыдущему доказательству, сначала построим последовательность <tex>\tilde{f_i}</tex>, а затем, добавив таймер <tex>in^i</tex>, получим последовательность <tex>f_i</tex>.
+
Пусть <tex>f_1, \ldots, f_n, \ldots</tex> — аналогичное множество полиномиальных функций: <tex>T(f_i, x) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>.
  
===Описание способа построения <tex>A</tex>===
+
Для простоты будем считать, что <tex>|\Sigma| = 2</tex>. Построим такую ''неубывающую'' функцию <tex>g \in \tilde{\mathrm{P}}</tex>, что при <tex>A = \{x \in \Sigma^*: g(|x|) \equiv 0 \pmod{2} \}</tex> для <tex>L</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>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 SAT] \ne [f_k(x_{2k+1}) \in SAT \cap \bigcup_{i=0}^{k} A_{2i}]</tex>.
 
  
[[File:Ladner.png]]
+
=== Алгоритм построения g ===
  
Если мы сможем построить такие <tex>A_i</tex>, то язык <tex>L = SAT \cap \bigcup_{i=0}^{\infty} A_{2i}</tex>
+
Положим <tex>g(0) = g(1) = 1</tex>. Для <tex>n \ge 1</tex> построим <tex>g(n + 1)</tex> рекурсивно — с помощью <tex>g(0), g(1), \ldots, g(n)</tex>.
будет отличаться от любого полиномиального языка, и ни одна полиномиальная функция не будет сводить
 
<tex>SAT</tex> к <tex>L</tex>.
 
  
Попытаемся построить такую полиномиальную функцию <tex>f</tex>, что
+
* Если <tex>(\log_2 n)^{g(n)} \ge n</tex>, то <tex>g(n+1) := g(n)</tex>. Иначе выполняем один из следующих пунктов.
<tex>A_i = \left\{x \mid f(|x|) = i\right\}</tex>. Тогда
 
<math>A=\left\{x \mid f(|x|) \, \vdots \, 2 \right\}</math> и
 
<math>L=SAT \cap A = \left\{\varphi \mid \varphi \in SAT \and f(|\varphi|)\, \vdots \, 2\right\}</math>
 
  
===Построение <tex>f</tex>===
+
* Пусть вычисленное значение <tex>g(n) = 2 i</tex>. Определим <tex>g(n+1)</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 L(x)</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>SAT(x) \ne L(f_i(x))</tex>, то <tex>f(n) = f(n-1)+1</tex>, иначе <tex>f(n) = f(n-1)</tex>.
 
  
Заметим, что вызовы <tex>L(\alpha)</tex> делаются для <tex>\alpha</tex>, для которых <tex>f</tex> уже построена.
+
for <tex>x</tex> : <tex>|x| \le \log_2 n</tex>
 +
  if <tex>M_i(x)</tex> and <tex>[g(|x|) \equiv 1 \pmod{2}</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|) \equiv 0 \pmod{2}</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>f(n)</tex> ограничена <tex>O\left(\log_{\log_2 n} n\right) = O(\log_2 n)</tex>.
+
* Пусть вычисленное значение <tex>g(n) = 2 i - 1</tex>. Определим <tex>g(n+1)</tex> следующим образом:
Второй «ответственен» за множества <tex>A_i</tex> для чётных <tex>i</tex>, третий — для нечетных.
 
Логарифм в условии <tex>|x| < \log_2 n</tex> необходим для полиномиальности <tex>f(n)</tex>.
 
  
===Полиномиальность <tex>f</tex>===
+
for <tex>x</tex> : <tex>|x| \le \log_2 n, |f_i(x)| \le \log_2 n</tex>
Покажем, что <tex>f \in \tilde{P}</tex>. Для упрощения будем считать, что алфавит <tex>\Sigma=\{0,1\}</tex>.
+
  if <tex>x \in \mathrm{SAT}</tex> and <tex>[g(|f_i(x)|) \equiv 1 \pmod{2}</tex> or <tex>f_i(x) \not \in \mathrm{SAT}]</tex>
 +
    <tex>g(n+1) := g(n)+1</tex>
 +
    return
 +
  if <tex>x \not \in \mathrm{SAT}</tex> and <tex>[g(|f_i(x)|) \equiv 0 \pmod{2}</tex> and <tex>f_i(x) \in \mathrm{SAT}]</tex>
 +
    <tex>g(n+1) := g(n)+1</tex>
 +
    return
 +
<tex>g(n+1) := g(n)</tex>
  
<tex>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)</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>SAT(x)</tex>;
 
*<tex>b_3(n)</tex> — время работы <tex>L(x)</tex>;
 
*<tex>b_4(n)</tex> — время работы <tex>L(f_i(x))</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) \in \tilde{P}</tex>.
+
Проверим выполнение второго и третьего свойств языка <tex>L = \mathrm{SAT} \cap A</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) \in \tilde{P}</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>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) \in \tilde{P}</tex>
+
* Пусть <tex>\lim\limits_{n \to \infty} g(n) = 2i</tex>. Значит, в нашем множестве существует такая машина Тьюринга <tex>M_i</tex>, распознающая <tex>L</tex>, что <tex>\forall x \Rightarrow M_i(x) = [g(|x|) \equiv 0 \pmod{2} \wedge 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>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) \in \tilde{P}</tex>
+
* Пусть <tex>\lim\limits_{n \to \infty} g(n) = 2i + 1</tex>. Тогда в нашем множестве полиномиальных функций существует <tex>f_i : \forall x \Rightarrow [x \in SAT] = [g(|f_i(x)|) \equiv 0 \pmod{2} \wedge 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>b_4(n) = b_3(b_1(n)) = O\left(n^4\right) \in \tilde{P}</tex>
+
Таким образом, при верности предположения <tex>\mathrm{P} \neq \mathrm{NP}</tex> второе и третье свойства <tex>L</tex> выполнены.
  
Чтобы построить программу <tex>p_i</tex> достаточно построить <tex>\tilde{p_i}</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>L</tex>. Для этого достаточно установить полиномиальность <tex>A</tex>. Покажем, что <tex>T(g, n)</tex> отличается от <tex>T(g, n - 1)</tex> не более, чем на неубывающий полином <tex>p(n)</tex>. Из этого будет следовать полиномиальность <tex>g</tex>: <tex>T(g, n) \le p(n) + p(n - 1) + \ldots + p(1) \le n p(n) \in poly(n)</tex>.
Поэтому <tex>T(n) \in \tilde{P}</tex> и <tex>A \in P</tex>.
 
  
Таким образом, <tex>f</tex> полиномиальна и <tex>A \in P</tex>.
+
Заметим, что <tex>g(n) \le n</tex> по построению для <tex>n \ge 1</tex>.
  
===Доказательство выполнения свойств <tex>A</tex>===
+
Вычисление значения <tex>g(n+1)</tex> состоит из вычисления <tex>g(n)</tex>, проверки неравенства <tex>(\log_2 n)^{g(n)} \ge n</tex> и, возможно, запуска одной из двух внутренних функций, время выполнения которых составляет:
Предположим, что <tex>\lim_{n \to \infty}f(n) = 2i</tex>. Это значит, что фунция «застряла» в ветке «иначе» случая два,
 
но из этого следует, что <tex>SAT</tex> не отличается от <tex>L(p_i)</tex>. Это
 
влечёт за собой принадлежность <tex>SAT</tex> к <tex>P</tex>, что противоречит предположению <tex>P \ne NP</tex>.
 
  
Аналогично, в случае, если <tex>\lim_{n \to \infty}f(n) = 2i+1</tex>. Тогда функция «застряла» в ветке «иначе» случая три.
+
<ul>
Следствием этого является то, что <tex>SAT</tex> функцией <tex>p_i</tex> сводится к конечному множеству, что тоже
+
<li>для случая <tex>g(n) = 2 i</tex>:<br/>
противоречит предположению <tex>P \ne NP</tex>.
+
<tex>\parbox{0px}{
 +
\begin{align*}
 +
T(n) & \le 2^{\log_2 n} (T(M_i, x) + T(g, |x|) + T(x \in \mathrm{SAT})) \le \\
 +
    & \le k_1 n (|x|^i + T(g, |x|) + 2^{|x|}|x|) \le \\
 +
    & \le k_1 n ((\log_2 n)^{g(n)} + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n) \le \\
 +
    & \le k_1 (n^2 + n^2 \log_2 n + n T(g, \log_2 n)) \le \\
 +
    & \le k_1 (2n^3 + n T(g, \log_2 n));
 +
\end{align*}
 +
}</tex>
 +
</li>
  
Получается, что <tex>\lim_{n \to \infty}f(n) = +\infty</tex>, но по построению если <tex>f</tex> неограниченно растет,
+
<li>для случая <tex>g(n) = 2 i - 1</tex>:<br/>
то <tex>L</tex> не совпадает ни с каким языком <tex>L(p_i)</tex> и ни одна функция <tex>f_i</tex> не сводит
+
<tex>\parbox{0px}{
<tex>SAT</tex> к <tex>L</tex>.  Следовательно, выполняются все три требуемых свойста, и <tex>L</tex> является примером
+
\begin{align*}
языка из <tex>NP\setminus(P \cup NPC)</tex>.
+
T(n) & \le 2^{\log_2 n} (T(x \in \mathrm{SAT}) + T(g, |f_i(x)|) + T(f_i(x) \in \mathrm{SAT})) \le \\
 +
    & \le k_2 n (2^{\log_2 n} \log_2 n + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n) \le \\
 +
    & \le k_2 (2n^2 \log_2 n + n T(g, \log_2 n)) \le \\
 +
    & \le k_2 (2n^3 + n T(g, \log_2 n)).
 +
\end{align*}
 +
}</tex>
 +
</li>
 +
</ul>
  
Теорема доказана.
+
Вычислить <tex>(\log_2 n)^{g(n)}</tex> можно за
 +
<tex>k_3 \log_2 g(n) |(\log_2 n)^{g(n)}|^2 \le k_3 (g(n) |log_2 n|)^2 log_2 n \le k_3 n^3</tex>.
 +
 
 +
Таким образом,
 +
<tex>T(g, n) \le T(g, n-1) + k (n^3 + n T(g, \log_2 n))</tex>.
 +
 
 +
Пусть <tex>T(g, 1) = d</tex>. Существует константа <tex>c \ge d</tex>, для которой при любом <tex>n</tex> верно
 +
<tex>c (n-1)^4 + k n^3 + k n c (\log_2 n)^4 \le c n^4</tex>.
 +
 
 +
Тогда, в силу <tex>T(g, 1) = d \le c \cdot 1^4</tex> и неравенства строкой выше, по индукции легко доказать, что <tex>T(g, n)</tex> ограничено сверху <tex>c n^4</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.
 +
}}
 +
 
 +
== Источник ==
 +
* ''William Gasarch, Lance Fortnow''. [http://blog.computationalcomplexity.org/media/ladner.pdf Two Proofs of Ladner’s Theorem]
 +
 
 +
[[Категория: Теория сложности]]

Текущая версия на 19:35, 4 сентября 2022

Теорема Ладнера (Ladner's Theorem) утверждает, что если P не совпадает с NP, то существует язык, принадлежащий [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]\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \varnothing[/math].
Доказательство:
[math]\triangleright[/math]

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

  1. [math]L \in \mathrm{NP}[/math] (для этого достаточно, чтобы выполнялось [math]A \in \mathrm{P}[/math]);
  2. [math]L \not \in \mathrm{P}[/math];
  3. [math]\mathrm{SAT} \not \le L[/math].

Если выполнены все три свойства, то [math]L \in \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|) \equiv 0 \pmod{2} \}[/math] для [math]L[/math] выполняются три перечисленных свойства.

Алгоритм построения g

Положим [math]g(0) = g(1) = 1[/math]. Для [math]n \ge 1[/math] построим [math]g(n + 1)[/math] рекурсивно — с помощью [math]g(0), g(1), \ldots, g(n)[/math].

  • Если [math](\log_2 n)^{g(n)} \ge n[/math], то [math]g(n+1) := g(n)[/math]. Иначе выполняем один из следующих пунктов.
  • Пусть вычисленное значение [math]g(n) = 2 i[/math]. Определим [math]g(n+1)[/math] следующим образом:
for [math]x[/math] : [math]|x| \le \log_2 n[/math]
  if [math]M_i(x)[/math] and [math][g(|x|) \equiv 1 \pmod{2}[/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|) \equiv 0 \pmod{2}[/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) = 2 i - 1[/math]. Определим [math]g(n+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)|) \equiv 1 \pmod{2}[/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)|) \equiv 0 \pmod{2}[/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]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\limits_{n \to \infty} g(n) = 2i[/math]. Значит, в нашем множестве существует такая машина Тьюринга [math]M_i[/math], распознающая [math]L[/math], что [math]\forall x \Rightarrow M_i(x) = [g(|x|) \equiv 0 \pmod{2} \wedge 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\limits_{n \to \infty} g(n) = 2i + 1[/math]. Тогда в нашем множестве полиномиальных функций существует [math]f_i : \forall x \Rightarrow [x \in SAT] = [g(|f_i(x)|) \equiv 0 \pmod{2} \wedge 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]L[/math]. Для этого достаточно установить полиномиальность [math]A[/math]. Покажем, что [math]T(g, n)[/math] отличается от [math]T(g, n - 1)[/math] не более, чем на неубывающий полином [math]p(n)[/math]. Из этого будет следовать полиномиальность [math]g[/math]: [math]T(g, n) \le p(n) + p(n - 1) + \ldots + p(1) \le n p(n) \in poly(n)[/math].

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

Вычисление значения [math]g(n+1)[/math] состоит из вычисления [math]g(n)[/math], проверки неравенства [math](\log_2 n)^{g(n)} \ge n[/math] и, возможно, запуска одной из двух внутренних функций, время выполнения которых составляет:

  • для случая [math]g(n) = 2 i[/math]:
    [math]\parbox{0px}{ \begin{align*} T(n) & \le 2^{\log_2 n} (T(M_i, x) + T(g, |x|) + T(x \in \mathrm{SAT})) \le \\ & \le k_1 n (|x|^i + T(g, |x|) + 2^{|x|}|x|) \le \\ & \le k_1 n ((\log_2 n)^{g(n)} + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n) \le \\ & \le k_1 (n^2 + n^2 \log_2 n + n T(g, \log_2 n)) \le \\ & \le k_1 (2n^3 + n T(g, \log_2 n)); \end{align*} }[/math]
  • для случая [math]g(n) = 2 i - 1[/math]:
    [math]\parbox{0px}{ \begin{align*} T(n) & \le 2^{\log_2 n} (T(x \in \mathrm{SAT}) + T(g, |f_i(x)|) + T(f_i(x) \in \mathrm{SAT})) \le \\ & \le k_2 n (2^{\log_2 n} \log_2 n + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n) \le \\ & \le k_2 (2n^2 \log_2 n + n T(g, \log_2 n)) \le \\ & \le k_2 (2n^3 + n T(g, \log_2 n)). \end{align*} }[/math]

Вычислить [math](\log_2 n)^{g(n)}[/math] можно за [math]k_3 \log_2 g(n) |(\log_2 n)^{g(n)}|^2 \le k_3 (g(n) |log_2 n|)^2 log_2 n \le k_3 n^3[/math].

Таким образом, [math]T(g, n) \le T(g, n-1) + k (n^3 + n T(g, \log_2 n))[/math].

Пусть [math]T(g, 1) = d[/math]. Существует константа [math]c \ge d[/math], для которой при любом [math]n[/math] верно [math]c (n-1)^4 + k n^3 + k n c (\log_2 n)^4 \le c n^4[/math].

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

Источник