109
правок
Изменения
→Доказательство: раделение на пункты
==Доказательство==
Будем искать язык <math>A</math>, удовлетворяющий следующим условиям:
#<math>A \in P</math> (что влечёт за собой<math>SAT \cap A \in NP</math>);
из <math>NP \setminus (P \cup NPC)</math>.
Действительно, рассмотрим последовательность всех программ, упорядоченных по длине:
Таким образом, <math>p_j</math> распознает тот же язык, что и <math>\tilde{p_i}</math>.
Аналогично предыдущему доказательству, сначала построим последовательность <math>\tilde{f_i}</math>,
а затем, добавив таймер <math>in^i</math>, получим последовательность <math>f_i</math>.
===Описание способа построения <math>A</math>===
Упорядочим все слова по возрастанию длины. Разобьем всё <math>\Sigma^{*}</math> на множества
<math>A_i</math>, <math>\forall i,j: i<j, \forall \alpha \in A_i, \beta \in A_j |\alpha| < |\beta|</math>
<math>L=SAT \cap A = \left\{\varphi \mid \varphi \in SAT \and f(|\varphi|)\, \vdots \, 2\right\}</math>
===Построение <math>f</math>===
Зададим <math>f(0) = f(1) = 0</math>. Затем рекурсивно определим <math>f(n)</math>. Для этого рассмотрим три случая:
Первый случай позволяет сказать, что <math>f(n)</math> ограничена <math>O\left(\log_{\log_2 n} n\right) = O(\log_2 n)</math>.
Логарифм в условии <math>|x| < \log_2 n</math> необходим для полиномиальности <math>f(n)</math>.
===Полиномиальность <math>f</math>===
Покажем, что <math>f \in \tilde{P}</math>. Для упрощения будем считать, что алфавит <math>\Sigma={0,1}</math>.
Таким образом, <math>f</math> полиномиальна и <math>A \in P</math>.
===Доказательство выполнения свойств <math>A</math>===
Предположим, что <math>\lim_{n \to \infty}f(n) = 2i</math>. Это значит, что фунция «застряла» в ветке «иначе» случая два,
но из этого следует, что <math>SAT</math> отличается от <math>L(p_i)</math> лишь на конечное число элементов. Это
Получается, что <math>\lim_{n \to \infty}f(n) = +\infty</math>, но по построению если <math>f</math> неограниченно растет,
то <math>L</math> не совпадает ни с каким языком <math>L(p_i)</math> и ни одна функция <math>f_i</math> не сводит
<math>SAT</math> к <math>L</math>. Следовательно, выполняются все три пунктатребуемых свойста, и <math>L</math> является примером
языка из <math>NP\setminus(P \cup NPC)</math>.
Теорема доказана.
