Изменения

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

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

3649 байт добавлено, 16:20, 4 июня 2013
Теорема
'''Теорема Ладнера''' (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=Ладнер
|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>A</tex>, чтобы язык <tex>L = \mathrm{SAT} \cap A</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> такследующим образом:
for <tex>x</tex> : <tex>|x| \le \log_2 n</tex>
<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>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>g(n+1)</tex> состоит из вычисления <tex>g(n)</tex>, проверки неравенства <tex>(\log_2 n)^{g(n)} \ge n</tex> и, возможно, запуска одной из двух внутренних функций. Время , время выполнения этих функций которых составляет:
<ul>
<li>для случая <tex>g(n) \equiv 0 \pmod{= 2}i</tex>:<br/>
<tex>\parbox{0px}{
\begin{align*}
</li>
<li>для случая <tex>g(n) \equiv = 2 i - 1 \pmod{2}</tex>:<br/>
<tex>\parbox{0px}{
\begin{align*}
<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 \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>.
}}
Анонимный участник

Навигация