Изменения

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

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

4341 байт добавлено, 16:20, 4 июня 2013
Теорема
'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным и , ни [[NP-полнота|NP-полным]].
== Доказательство Иллюстрация ==
ПредположимОпределим язык <tex>A</tex> как множество таких формул <tex>\alpha</tex>, что <tex>\mathrmleft\lfloor \frac{P1}{2} \neq \mathrmlog_{NP10}^*|\alpha|\right\rfloor</tex>чётно. Из этого следуетИными словами, <tex>A</tex> — это язык формул с длинами, что лежащими в промежутках <tex>\mathrmleft[1,10^{10}\right),\left[\underbrace{10^{10^{\cdot^{\cdot^{NP10}}}}}_4,\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_6\right), \ldots</tex>-полный язык (например, Далее будем обозначать <tex>\mathrmunderbrace{a^{a^{\cdot^{\cdot^{SATa}}}}}_n</tex>) нельзя свести по Карпу к полиномиальному. Будем искать язык как <tex>A^{n}a</tex>, удовлетворяющий следующим условиям:.
# Рассмотрим язык [[SAT]] всех удовлетворимых формул. Логично предположить, что как в <tex>A </tex>,так и в <tex>\in bar{A}</tex> лежит бесконечное множество элементов из <tex>\mathrm{PSAT}</tex> (что влечёт ,не распознаваемых за собой полиномиальное время, поэтому <tex>\mathrm{SAT} \cap A \not\in \mathrm{NPP}</tex>);.# Из <tex>\mathrm{SAT} \cap A \not \in \mathrm{P}</tex>;# и <tex>\mathrm{SAT} \not in \le mathrm{NP}</tex> следует, что <tex>\mathrm{SAT} \cap A\in \mathrm{NP}</tex>.
Если такой язык существуетОсталось показать, то что <tex>L = \mathrm{SAT} \cap A</tex> не является искомым примером множестваNP-полным. Пустьэто не так. Тогда из NP-полноты следует, что существует полиномиальная функция <math>f</math>,[[Сведение по Карпу|сводящая по Карпу]] <tex>\mathrm{NPSAT} \setminus (</tex> к <tex>\mathrm{PSAT} \cup \mathrm{NPC})cap A</tex>.
Пусть Возьмём формулу <tex>M_1, \ldotsvarphi</tex> длиной <tex>^{2k+1}10</tex>. Она не лежит в <tex>A</tex> и, M_nследовательно, в <tex>\ldotsmathrm{SAT} \cap A</tex> — все машины Тьюринга из .Функция <tex>f</tex> не может перевести <tex>\tilde{varphi</tex> в промежуток<tex>\mathrmleft[^{P2k+2}10, ^{2k+4}10\right)</tex>или дальше, так как размервыхода полиномиальной функции не может быть экспоненциально больше длинывхода. Значит, причём <tex>T\varphi</tex> отображается в меньший промежуток, нов этом случае размер выхода экспоненциально меньше длины входа. Добавляяк этому то, что проверку на принадлежность <tex>f(M_i\varphi)</tex> к<tex>\mathrm{SAT} \cap A</tex> можно осуществить за <tex>O(x2^{poly})</tex>(это следует из её принадлежности классу <tex>\mathrm{NP}</tex>) , получаем программу,разрешающую <tex>\le |x|varphi</tex> за полином. Утверждение о том, что все формулы<tex>\varphi</tex> длиной <tex>^i{2k+1}10</tex> для любого принадлежат классу<tex>x \in mathrm{P}</tex>, скорее всего неверно, и, следовательно, язык <tex>\Sigma^*mathrm{SAT} \cap A</tex>не является NP-полным.
Пусть <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> выполняются три названных свойства.
{{Теорема|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>gA</tex> , чтобы язык <tex>L ===\mathrm{SAT} \cap A</tex> удовлетворял следующим условиям:
Определим # <tex>gL \in \mathrm{NP}</tex> рекурсивно. Установим (для этого достаточно, чтобы выполнялось <tex>A \in \mathrm{P}</tex>g(0) = g(1) = 1;# <tex>L \not \in \mathrm{P}</tex>. Для ;# <tex>n \ge 1mathrm{SAT} \not \le L</tex>:.
* Если выполнены все три свойства, то <tex>log_2^L \in \mathrm{gNP} \setminus (n)\mathrm{P} n \ge n</tex>, <tex>g(n+1) := g(ncup \mathrm{NPC})</tex>.
Иначе Пусть <tex> n M_1, \ldots, M_n, \ldots</tex> — все машины Тьюринга из <tex> log_2^\tilde{\mathrm{g(n)P}} n \ge log_2 n</tex>; значения (возможно, с повторениями), расположенные в таком порядке, чтобы <tex>gT(mM_i, x)\le |x|^i</tex> для любого <tex>m x \in \le log_2 nSigma^*</tex> уже известны.
* Пусть <tex>g(n) = 2i</tex>. for <tex>x</tex>: <tex>|x| f_1, \le log_2 n</tex> if <tex>M_i(x)</tex> and (<tex>g(|x|) ldots, f_n, \% 2 = 1ldots</tex> or — аналогичное множество полиномиальных функций: <tex>x \not \in \mathrm{SAT})</tex> <tex>g(n+1) := gT(n)+1</tex>f_i, return if <tex>! M_i(x)</tex> and (<tex>g(\le |x|) \% 2 = 0^i</tex> and для любого <tex>x \in \mathrm{SAT})</tex> <tex>g(n+1) := g(n)+1</tex>, return <tex>g(n+1) := g(n)Sigma^*</tex>.
* <tex>g(n) = 2i + 1</tex>. for <tex>x</tex>: Для простоты будем считать, что <tex>|x| \le log_2 n, Sigma|f_i(x)| \le log_2 n= 2</tex> if . Построим такую ''неубывающую'' функцию <tex>x g \in \tilde{\mathrm{SATP}}</tex> and (, что при <tex>g(|f_i(x)|) \% 2 A = 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>Sigma^*: g(|f_i(x)|) \% 2 = equiv 0</tex> and <tex>f_i(x) \in pmod{2} \mathrm{SAT})</tex> для <tex>g(n+1) := g(n)+1</tex>, return <tex>g(n+1) := g(n)L</tex>выполняются три перечисленных свойства.
Утверждается=== Алгоритм построения g === Положим <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>(\log_2 n)^{g(n)} \ge n</tex> язык , то <tex>A g(n+1) := g(n)</tex>. Иначе выполняем один из следующих пунктов. * Пусть вычисленное значение <tex>g(n) = 2 i</tex>. Определим <tex>g(n+1)</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 \Sigma^mathrm{SAT}]</tex> <tex>g(n+1) := g(n)+1</tex> return <tex>g(n+1) := g(n)</tex> *Пусть вычисленное значение <tex>g(n) = 2 i - 1</tex>. Определим <tex>g(n+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)|) \% 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>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_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 = 0 } \cap 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_lim\limits_{n \to +\infty} g(n) = 2i + 1</tex>. Тогда в нашем множестве полиномиальных функций существует <tex>f_i</tex>: <tex>\forall x (\Rightarrow [x \in SAT) ] = ([g(|f_i(x)|) \% equiv 0 \pmod{2 = 0 } \cap 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>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>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+1)</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{g(n) } \le c_1 ge 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>
<ul><li>для случая <tex>g(n) = 2 i</tex>:<br/><tex>T_2\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 c_2 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>T_2g(n) = 2 i - 1</tex>:<br/><tex>\parbox{0px}{\begin{align*}T(n) & \le c_2 2^{\log_2 n } (T(log_2^x \in \mathrm{iSAT} n ) + 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>T_2(\log_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) k_3 \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) 2 \le c_3 n k_3 (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 (2nk_3 n^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) + 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>T^g(, 1) = const = d</tex>. Существует константа <tex>c \ge d</tex>, для которой при любом <tex>n</tex> верно <tex>c (n-1)^7 4 + k_1 k n^5 3 + k_2 k n c (\log_2 n)^7 4 \le c n^74</tex>.
Тогда, в силу <tex>T^(g(, 1) = d \le c \cdot 1^74</tex> и неравенства строкой выше, по индукции легко доказать, что <tex>T^(g(, n)</tex> ограничено сверху <tex>c n^74</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.}}
== Источник ==
Анонимный участник

Навигация