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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Иллюстрация)
(Иллюстрация: дописана до конца)
Строка 8: Строка 8:
  
 
Определим язык <math>A</math> как множество таких формул <math>\alpha</math>,
 
Определим язык <math>A</math> как множество таких формул <math>\alpha</math>,
что <math>\left\lfloor \frac{1}{2}\log_{10}^*|\alpha|\right\rfloor</math> чётно. Иными словами,
+
что <math>\left\lfloor \frac{1}{2}\log_{10}^*|\alpha|\right\rfloor</math> чётно.
<math>A</math> — это язык формул с длинами, лежащими в промежутках  
+
Иными словами, <math>A</math> — это язык формул с длинами, лежащими в промежутках  
 
<math>\left[1,10^{10}\right),
 
<math>\left[1,10^{10}\right),
\left[\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_4, \underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_6\right), \dots</math>
+
\left[\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_4,
Далее будем обозначать <math>\underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_n</math> как <math>^{n}a</math>.
+
\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_6\right), \dots</math>
 +
Далее будем обозначать <math>\underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_n</math>
 +
как <math>^{n}a</math>.
  
 
Рассмотрим язык <math>SAT</math>. Логично предположить, что как в <math>A</math>,
 
Рассмотрим язык <math>SAT</math>. Логично предположить, что как в <math>A</math>,
так и в <math>\bar{A}</math> лежит бесконечное множество элементов из <math>SAT</math>.
+
так и в <math>\bar{A}</math> лежит бесконечное множество элементов из <math>SAT</math>,
 +
не принадлежащих классу <math>P</math>, поэтому <math>SAT \cap A \not\in P</math>
 
Из <math>A \in P</math> и <math>SAT \in NP</math> следует, что <math>SAT \cap A \in NP</math>.
 
Из <math>A \in P</math> и <math>SAT \in NP</math> следует, что <math>SAT \cap A \in NP</math>.
  
Предположим, что <math>SAT \cap A</math> является NP-полным.
+
Осталось показать, что <math>SAT \cap A</math> не является NP-полным. Пусть
Из NP-полноты следует, что существует полиномиальная функция f сводящая по Карпу <math>SAT</math>  
+
это не так. Тогда из NP-полноты следует, что существует полиномиальная функция <math>f</math>
к <math>SAT \cap A</math>.  
+
сводящая по Карпу <math>SAT</math> к <math>SAT \cap A</math>.  
  
Возьмем формулу <math>\varphi</math> длиной <math>^{2k+1}10</math>. Она не лежит в <math>A</math> и,
+
Возьмем формулу <math>\varphi</math> длиной <math>^{2k+1}10</math>.  
следовательно, в <math>SAT \cap A</math>. Функция <math>f</math> не может перевести <math>\varphi</math>
+
Она не лежит в <math>A</math> и, следовательно, в <math>SAT \cap A</math>.
в промежуток <math>\left[^{2k+2}10, ^{2k+4}10\right)</math> или дальше, так как размер выхода полиномиальной функции не может быть экспоненциально больше длинны входа. Значит <math>\varphi</math> отображается в меньший промежуток, но в этом случае размер выхода экспоненциально меньше длины входа.  Добавляя к этому то, что проверку на принадлежность <math>f(\varphi)</math> <math>SAT \cap A</math> можно осуществить за <math>O(2^{poly})</math> (это следует из принадлежности <math>NP</math>), получаем программу разрешающую <math>\varphi</math> за полином.
+
Функция <math>f</math> не может перевести <math>\varphi</math> в промежуток
 +
<math>\left[^{2k+2}10, ^{2k+4}10\right)</math> или дальше, так как размер
 +
выхода полиномиальной функции не может быть экспоненциально больше длинны
 +
входа. Значит <math>\varphi</math> отображается в меньший промежуток, но
 +
в этом случае размер выхода экспоненциально меньше длины входа.  Добавляя
 +
к этому то, что проверку на принадлежность <math>f(\varphi)</math>  
 +
<math>SAT \cap A</math> можно осуществить за <math>O(2^{poly})</math>
 +
(это следует из принадлежности <math>NP</math>), получаем программу
 +
разрешающую <math>\varphi</math> за полином. Утверждение о том, что все формулы
 +
<math>\varphi</math> длиной <math>^{2k+1}10</math> принадлежат классу
 +
<math>P</math> скорее всего не верно, а ,следовательно, язык
 +
<math>SAT \cap A</math> не является NP-полным.
 +
 
 +
Заметим, что это объяснение не является доказательством!
  
 
==Доказательство==
 
==Доказательство==

Версия 14:28, 5 марта 2010

Формулировка

Теорема Ладнера (Ladner's Theorem) утверждает, что если [math]P \ne NP[/math], то существует язык [math]L[/math], принадлежащий [math]NP \setminus (P \cup NPC)[/math].

Иллюстрация

Определим язык [math]A[/math] как множество таких формул [math]\alpha[/math], что [math]\left\lfloor \frac{1}{2}\log_{10}^*|\alpha|\right\rfloor[/math] чётно. Иными словами, [math]A[/math] — это язык формул с длинами, лежащими в промежутках [math]\left[1,10^{10}\right), \left[\underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_4, \underbrace{10^{10^{\cdot^{\cdot^{10}}}}}_6\right), \dots[/math] Далее будем обозначать [math]\underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_n[/math] как [math]^{n}a[/math].

Рассмотрим язык [math]SAT[/math]. Логично предположить, что как в [math]A[/math], так и в [math]\bar{A}[/math] лежит бесконечное множество элементов из [math]SAT[/math], не принадлежащих классу [math]P[/math], поэтому [math]SAT \cap A \not\in P[/math] Из [math]A \in P[/math] и [math]SAT \in NP[/math] следует, что [math]SAT \cap A \in NP[/math].

Осталось показать, что [math]SAT \cap A[/math] не является NP-полным. Пусть это не так. Тогда из NP-полноты следует, что существует полиномиальная функция [math]f[/math] сводящая по Карпу [math]SAT[/math] к [math]SAT \cap A[/math].

Возьмем формулу [math]\varphi[/math] длиной [math]^{2k+1}10[/math]. Она не лежит в [math]A[/math] и, следовательно, в [math]SAT \cap A[/math]. Функция [math]f[/math] не может перевести [math]\varphi[/math] в промежуток [math]\left[^{2k+2}10, ^{2k+4}10\right)[/math] или дальше, так как размер выхода полиномиальной функции не может быть экспоненциально больше длинны входа. Значит [math]\varphi[/math] отображается в меньший промежуток, но в этом случае размер выхода экспоненциально меньше длины входа. Добавляя к этому то, что проверку на принадлежность [math]f(\varphi)[/math] [math]SAT \cap A[/math] можно осуществить за [math]O(2^{poly})[/math] (это следует из принадлежности [math]NP[/math]), получаем программу разрешающую [math]\varphi[/math] за полином. Утверждение о том, что все формулы [math]\varphi[/math] длиной [math]^{2k+1}10[/math] принадлежат классу [math]P[/math] скорее всего не верно, а ,следовательно, язык [math]SAT \cap A[/math] не является NP-полным.

Заметим, что это объяснение не является доказательством!

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

[math]L=\left\{\varphi | \varphi \in SAT \and f(|\varphi|) \text{ is even}\right\}[/math]

[math]A=\left\{x | f(|x|) \text{ is even}\right\}[/math]

[math]f(0) = f(1) = 0[/math]

Определим [math]f(n)[/math]:

  • Случай 1: [math]f(n-1)=2i[/math].
    Если существует [math]x[/math], такой что [math]|x| \lt \log_2n[/math] и [math]M_i(x) \ne L(x)[/math], то [math]f(n) = f(n-1)+1[/math], иначе [math]f(n) = f(n-1)[/math]
  • Случай 2: [math]f(n-1)=2i+1[/math].
    Если существует [math]x[/math], такой что [math]|x| \lt \log_2n[/math] и [math]SAT(x) \ne L(g_i(x))[/math], то [math]f(n) = f(n-1)+1[/math], иначе [math]f(n) = f(n-1)[/math]