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

2012-06-01T19:44:05Z

178.130.42.66: Андрей, там определяется (n+1) через n, посмотри внимательнее.

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

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

Предположим, что <tex>\mathrm{P} \neq \mathrm{NP}</tex>. Из этого следует, что <tex>\mathrm{NP}</tex>-полный язык (например, <tex>\mathrm{SAT}</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 \le \mathrm{SAT} \cap A</tex>.

Если такой язык существует, то <tex>L = \mathrm{SAT} \cap A</tex> является искомым примером множества
из <tex>\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>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>g(n) = 2i + 1</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)|) \% 2 = 1</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)|) \% 2 = 0</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>g</tex> язык <tex>A = \{x \in \Sigma^*: g(|x|) \% 2 = 0\}</tex> является искомым.

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

Проверим выполнение второго и третьего свойств языка <tex>L = \mathrm{SAT} \cap A</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>

<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_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) + 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_1 n^5 + k_2 n T_g(log_2 n)</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>T_g(n) \le T_g(n-1) + k_1 n^5 + 2 k_2 k_3 n^2</tex>

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

<tex>c (n-1)^6 + k_1 n^5 + 2 k_2 k_3 n^2 \le c n^6</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>.

== Источник ==
* ''William Gasarch, Lance Fortnow''. [http://blog.computationalcomplexity.org/media/ladner.pdf Two Proofs of Ladner’s Theorem]

[[Категория: Теория сложности]]

Викиконспекты - Вклад участника [ru]

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