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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 14: Строка 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|) \equiv 0 \pmod{2} \}</tex> выполняются три перечисленных свойства.
 
Для простоты будем считать, что <tex>|\Sigma| = 2</tex>. Построим такую ''неубывающую'' функцию <tex>g \in \tilde{\mathrm{P}}</tex>, что для <tex>A = \{x \in \Sigma^*: g(|x|) \equiv 0 \pmod{2} \}</tex> выполняются три перечисленных свойства.
Строка 64: Строка 64:
 
=== Время работы алгоритма ===
 
=== Время работы алгоритма ===
  
Проверим первое свойство — полиномиальность языка <tex>A</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>g(n) \le n</tex> по построению для <tex>n \ge 1</tex>.
Строка 72: Строка 70:
 
Время выполнения шагов составляет:
 
Время выполнения шагов составляет:
  
* проверка неравенства:
+
* для случая <tex>g(n) = 2i</tex>:
 
 
<tex>T_1(n) \le g(n) T_*(\log_2^{g(n)} n, \log_2^{g(n)} n)</tex>
 
 
 
<tex>T_1(n) \le c_1 g(n) (\log_2 (\log_2^{g(n)} n))^2</tex>
 
 
 
<tex>T_1(n) \le c_1 g^3(n) \log_2^2 \log_2 n</tex>
 
 
 
<tex>T_1(n) \le c_1 n^3 \log_2^2 \log_2 n</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(n) \le 2^{\log_2 n} (T(M_i, x) + T(g, |x|) + T(x \in \mathrm{SAT}))</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(n) \le k_1 n (|x|^i + T(g, |x|) + 2^{|x|}|x|)</tex>;
  
<tex>T_2(n) \le c_2 n (|x|^i + T^g(|x|) + 2^{|x|}|x|)</tex>
+
<tex>T(n) \le k_1 n ((\log_2 n)^{g(n)} + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n)</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(n) \le k_1 (n^2 + n^2 \log_2 n + n T(g, \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(n) \le k_1 (2n^3 + n T(g, \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>g(n) = 2i + 1</tex>:
  
<tex>T_2(n) \le c_2 (2n^3 + n T^g(\log_2 n))</tex>
+
<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}))</tex>;
  
* <tex>g(n) = 2i + 1</tex>:
+
<tex>T(n) \le k_2 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 2^{\log_2 n} (T(x \in \mathrm{SAT}) + T^g(|f_i(x)|) + T(f_i(x) \in \mathrm{SAT}))</tex>
+
<tex>T(n) \le k_2 (2n^2 \log_2 n + n T(g, \log_2 n))</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(n) \le k_2 (2n^3 + n T(g, \log_2 n))</tex>.
  
<tex>T_3(n) \le c_3 (2n^2 \log_2 n + n T^g(\log_2 n))</tex>
+
Кроме того, необходимо знать значение <tex>g(n)</tex>, получаемое на <tex>n-1</tex> шаге, и вычислить <tex>(\log_2 n)^{g(n)}</tex>, что можно сделать за
  
<tex>T_3(n) \le c_3 (2n^3 + n T^g(\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^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>T(g, n) \le T(g, n-1) + k (n^3 + n T(g, \log_2 n))</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>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>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 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>.
+
Тогда, в силу <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>.
 
}}
 
}}
  

Версия 14:12, 3 июня 2012

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

Определим [math]g[/math] рекурсивно. Положим [math]g(0) = g(1) = 1[/math].

Для [math]n \ge 1[/math]:

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

Иначе [math] n \gt (\log_2 n)^{g(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|) \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) = 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(|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(|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]g(n) \le n[/math] по построению для [math]n \ge 1[/math].

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

  • для случая [math]g(n) = 2i[/math]:

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

[math]T(n) \le k_1 n (|x|^i + T(g, |x|) + 2^{|x|}|x|)[/math];

[math]T(n) \le k_1 n ((\log_2 n)^{g(n)} + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n)[/math];

[math]T(n) \le k_1 (n^2 + n^2 \log_2 n + n T(g, \log_2 n))[/math];

[math]T(n) \le k_1 (2n^3 + n T(g, \log_2 n))[/math];

  • для случая [math]g(n) = 2i + 1[/math]:

[math]T(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(n) \le k_2 n (2^{\log_2 n} \log_2 n + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n)[/math];

[math]T(n) \le k_2 (2n^2 \log_2 n + n T(g, \log_2 n))[/math];

[math]T(n) \le k_2 (2n^3 + n T(g, \log_2 n))[/math].

Кроме того, необходимо знать значение [math]g(n)[/math], получаемое на [math]n-1[/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) = const = 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]

Источник