109
правок
Изменения
добавлена немного недоделанная иллюстрация
==Формулировка==
'''Теорема Ладнера''' (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>A \in P</math> и <math>SAT \in NP</math> следует, что <math>SAT \cap A \in NP</math>.
Предположим, что <math>SAT \cap A</math> является NP-полным.
Из NP-полноты следует, что существует полиномиальная функция f сводящая по Карпу <math>SAT</math>
к <math>SAT \cap A</math>.
Возьмем формулу <math>\phi</math> длиной <math>^{2k+1}10</math>. Она не лежит в <math>A</math> и,
следовательно, в <math>SAT \cap A</math>. Функция <math>f</math> не может перевести <math>\phi</math>
в промежуток <math>\left[^{2k+2}10, ^{2k+4}10\right)</math> или дальше, так как размер выхода
полиномиальной функции не может быть экспоненциально больше длинны входа. Значит <math>\phi</math>
отображается в меньший промежуток, но в этом случае размер выхода экспоненциально меньше длины входа.
Добавляя к этому то, что проверку на принадлежность <math>f(\phi)</math> <math>SAT \cap A</math> можно осуществить
за <math>O(2^{poly})</math> (это следует из принадлежности <math>NP</math>), получаем программу разрешающую
<math>\phi</math> за полином, а это почему-то плохо.
==Доказательство==
'''Теорема Ладнера''' (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>A \in P</math> и <math>SAT \in NP</math> следует, что <math>SAT \cap A \in NP</math>.
Предположим, что <math>SAT \cap A</math> является NP-полным.
Из NP-полноты следует, что существует полиномиальная функция f сводящая по Карпу <math>SAT</math>
к <math>SAT \cap A</math>.
Возьмем формулу <math>\phi</math> длиной <math>^{2k+1}10</math>. Она не лежит в <math>A</math> и,
следовательно, в <math>SAT \cap A</math>. Функция <math>f</math> не может перевести <math>\phi</math>
в промежуток <math>\left[^{2k+2}10, ^{2k+4}10\right)</math> или дальше, так как размер выхода
полиномиальной функции не может быть экспоненциально больше длинны входа. Значит <math>\phi</math>
отображается в меньший промежуток, но в этом случае размер выхода экспоненциально меньше длины входа.
Добавляя к этому то, что проверку на принадлежность <math>f(\phi)</math> <math>SAT \cap A</math> можно осуществить
за <math>O(2^{poly})</math> (это следует из принадлежности <math>NP</math>), получаем программу разрешающую
<math>\phi</math> за полином, а это почему-то плохо.
==Доказательство==
