Теорема Ладнера

Теорема Ладнера (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].

Источник

• William Gasarch, Lance Fortnow. Two Proofs of Ladner’s Theorem