Редактирование: Теорема Ладнера

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным, ни [[NP-полнота|NP-полным]].
 
'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным, ни [[NP-полнота|NP-полным]].
 
== Иллюстрация ==
 
 
Определим язык <tex>A</tex> как множество таких формул <tex>\alpha</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>\bar{A}</tex> лежит бесконечное множество элементов из <tex>\mathrm{SAT}</tex>,
 
не распознаваемых за полиномиальное время, поэтому <tex>\mathrm{SAT} \cap A \not\in \mathrm{P}</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-полным. Пусть
 
это не так. Тогда из NP-полноты следует, что существует полиномиальная функция <math>f</math>,
 
[[Сведение по Карпу|сводящая по Карпу]] <tex>\mathrm{SAT}</tex> к <tex>\mathrm{SAT} \cap A</tex>.
 
 
Возьмём формулу <tex>\varphi</tex> длиной <tex>^{2k+1}10</tex>.
 
Она не лежит в <tex>A</tex> и, следовательно, в <tex>\mathrm{SAT} \cap A</tex>.
 
Функция <tex>f</tex> не может перевести <tex>\varphi</tex> в промежуток
 
<tex>\left[^{2k+2}10, ^{2k+4}10\right)</tex> или дальше, так как размер
 
выхода полиномиальной функции не может быть экспоненциально больше длины
 
входа. Значит, <tex>\varphi</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>^{2k+1}10</tex> принадлежат классу
 
<tex>\mathrm{P}</tex>, скорее всего неверно, и, следовательно, язык
 
<tex>\mathrm{SAT} \cap A</tex> не является NP-полным.
 
 
Заметим, что это объяснение не является доказательством!
 
 
== Теорема ==
 
  
 
{{Теорема
 
{{Теорема
 
|author=Ладнер
 
|author=Ладнер
 
|statement=
 
|statement=
<tex>\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \varnothing</tex>.
+
<tex>\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \emptyset</tex>
 
|proof=
 
|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> удовлетворял следующим условиям:
 
Предположим, что <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> удовлетворял следующим условиям:
Строка 53: Строка 14:
 
Если выполнены все три свойства, то <tex>L \in \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC})</tex>.
 
Если выполнены все три свойства, то <tex>L \in \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC})</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>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>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>|\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>g</tex> ===
  
=== Алгоритм построения g ===
+
Определим <tex>g</tex> рекурсивно. Положим <tex>g(0) = g(1) = 1</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>n \ge 1</tex>:
  
* Если <tex>(\log_2 n)^{g(n)} \ge n</tex>, то <tex>g(n+1) := g(n)</tex>. Иначе выполняем один из следующих пунктов.
+
* Если <tex>(\log_2 n)^{g(n)} \ge n</tex>, <tex>g(n+1) := g(n)</tex>.
  
* Пусть вычисленное значение <tex>g(n) = 2 i</tex>. Определим <tex>g(n+1)</tex> следующим образом:
+
Иначе <tex> n > (\log_2 n)^{g(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>
 
  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>
+
   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>
 
     <tex>g(n+1) := g(n)+1</tex>
 
     return
 
     return
   if <tex>! M_i(x)</tex> and <tex>[g(|x|) \equiv 0 \pmod{2}</tex> and <tex>x \in \mathrm{SAT}]</tex>
+
   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>
 
     <tex>g(n+1) := g(n)+1</tex>
 
     return
 
     return
 
  <tex>g(n+1) := g(n)</tex>
 
  <tex>g(n+1) := g(n)</tex>
  
* Пусть вычисленное значение <tex>g(n) = 2 i - 1</tex>. Определим <tex>g(n+1)</tex> следующим образом:
+
* <tex>g(n) = 2i + 1</tex>.
 
 
 
  for <tex>x</tex> : <tex>|x| \le \log_2 n, |f_i(x)| \le \log_2 n</tex>
 
  for <tex>x</tex> : <tex>|x| \le \log_2 n, |f_i(x)| \le \log_2 n</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>
+
   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>g(n+1) := g(n)+1</tex>
+
     <tex>g(n+1) := g(n)+1</tex>, return
    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>
   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)+1</tex>
 
    return
 
 
  <tex>g(n+1) := g(n)</tex>
 
  <tex>g(n+1) := g(n)</tex>
  
Строка 93: Строка 54:
 
* Пусть <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>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\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>\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|) \% 2 = 0 \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>\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>\lim\limits_{n \to \infty} g(n) = 2i + 1</tex>. Тогда в нашем множестве полиномиальных функций существует <tex>f_i : \forall x \Rightarrow [x \in SAT] = [g(|f_i(x)|) \% 2 = 0 \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>\mathrm{P} \neq \mathrm{NP}</tex> второе и третье свойства <tex>L</tex> выполнены.
 
Таким образом, при верности предположения <tex>\mathrm{P} \neq \mathrm{NP}</tex> второе и третье свойства <tex>L</tex> выполнены.
Строка 101: Строка 62:
 
=== Время работы алгоритма ===
 
=== Время работы алгоритма ===
  
Проверим выполнение первого свойства языка <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>A</tex>.
 +
 
 +
Пусть <tex>T^g(n)</tex> — время вычисления <tex>g(n)</tex>.
  
 
Заметим, что <tex>g(n) \le n</tex> по построению для <tex>n \ge 1</tex>.
 
Заметим, что <tex>g(n) \le n</tex> по построению для <tex>n \ge 1</tex>.
  
Вычисление значения <tex>g(n+1)</tex> состоит из вычисления <tex>g(n)</tex>, проверки неравенства <tex>(\log_2 n)^{g(n)} \ge n</tex> и, возможно, запуска одной из двух внутренних функций, время выполнения которых составляет:
+
Время выполнения шагов составляет:
 +
 
 +
* проверка неравенства:
 +
 
 +
<tex>T_1(n) \le g(n) T_*(\log_2^{g(n)} n, \log_2^{g(n)} n)</tex>
  
<ul>
+
<tex>T_1(n) \le c_1 g(n) (\log_2 (\log_2^{g(n)} n))^2</tex>
<li>для случая <tex>g(n) = 2 i</tex>:<br/>
 
<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>
 
  
<li>для случая <tex>g(n) = 2 i - 1</tex>:<br/>
+
<tex>T_1(n) \le c_1 g^3(n) \log_2^2 \log_2 n</tex>
<tex>\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*}
 
}</tex>
 
</li>
 
</ul>
 
  
Вычислить <tex>(\log_2 n)^{g(n)}</tex> можно за
+
<tex>T_1(n) \le c_1 n^3 \log_2^2 \log_2 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_1(n) \le c_1 n^5</tex>,
 +
 
 +
где <tex>T_*(a, b)</tex> — время нахождения произведения чисел <tex>a</tex> и <tex>b</tex>
 +
 
 +
* <tex>g(n) = 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>T_2(n) \le c_2 n (|x|^i + T^g(|x|) + 2^{|x|}|x|)</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>T_2(n) \le c_2 n (\log_2^{g(n)} n + T^g(\log_2 n) + n \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>T_2(n) \le c_2 (2n^3 + n T^g(\log_2 n))</tex>
 +
 
 +
* <tex>g(n) = 2i + 1</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>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>T_3(n) \le c_3 (2n^2 \log_2 n + n T^g(\log_2 n))</tex>
 +
 
 +
<tex>T_3(n) \le c_3 (2n^3 + n T^g(\log_2 n))</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>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>c (n-1)^4 + k n^3 + k n c (\log_2 n)^4 \le c n^4</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^g(1) = const = d</tex>. Существует константа <tex>c \ge d</tex>, для которой при любом <tex>n</tex> верно
 +
 
 +
<tex>c (n-1)^7 + k_1 n^5 + k_2 n c (\log_2 n)^7 \le c n^7</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>.
+
Тогда, в силу <tex>T^g(1) = d \le c 1^7</tex> и неравенства выше, по индукции легко доказать, что <tex>T^g(n)</tex> ограничено сверху <tex>c n^7</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.
 
}}
 
}}
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: