109
правок
Изменения
м
→Доказательство
только программы из <math>P</math>, и для каждой полиномиальной программы
<math>\tilde{p_i}</math>, работающей за полином <math>q_i(n)</math>, существует
номер <math>j</math>такой, такой что <math>jn^j > g_i(n)</math> для всех натуральных <math>n</math>,
и <math>\tilde{p_j}</math> делает то же самое, что и <math>\tilde{p_i}</math>.
Таким образом , <math>p_j</math> распознает тот же язык, что и <math>\tilde{p_i}</math>.
'''Утверждение 2.''' Можно перечислить все функции из <math>\tilde{P}</math>.
<math>A_i</math>, <math>\forall i,j i<j \forall \alpha \in A_i, \beta \in A_j |\alpha| < |\beta|</math>
так, что <math>SAT \cap \bigcup_{i=0}^{k} A_{2i}</math> отличается от <math>L(p_k)</math> элементом
из <math>\bigcup_{i=0}^{2k} A_i</math>, и существует <math>\alpha \in \bigcup_{i=0}^{2k+1}</math>для которого выполняется выполняются условия <math>f(\alpha) \in \bigcup_{i=0}^{2k+1}</math> и
<math>[\alpha \in SAT] \ne [f(\alpha) \in SAT \cap \bigcup_{i=0}^{k} A_{2i}]</math>.
Если мы сможем построить такие <math>A_i</math>, то язык <math>L = SAT \cap \bigcup_{i=0}^{\infty} A_{2i}</math>
будет отличаться от любого полиномиального языка, и ни какая одна полиномиальная функция не будет сводить
<math>SAT</math> к <math>L</math>.
#:<math>f(n) = f(n-1)</math>;
#<math>f(n-1)=2i</math>:
#:если существует <math>x</math>такой, такой что <math>|x| < \log_2 n</math> и <math>p_i(x) \ne L(x)</math>, то <math>f(n) = f(n-1)+1</math>, иначе <math>f(n) = f(n-1)</math>;
#<math>f(n-1)=2i+1</math>:
#:если существует <math>x</math>такой, такой что <math>|x| < \log_2 n</math> и <math>SAT(x) \ne L(f_i(x))</math>, то <math>f(n) = f(n-1)+1</math>, иначе <math>f(n) = f(n-1)</math>.
Первый случай позволяет сказать, что <math>f(n)</math> ограничена <math>O\left(\log_{\log_2 n} n\right) = O(\log_2 n)</math>.
Чтобы построить программу <math>p_i</math> достаточно построить <math>\tilde{p_i}</math>.
Из того, что все <math>\tilde{p_i}</math> упорядоченны упорядочены по длине, следует, что длина
<math>\tilde{p_i}</math> не превосходит <math>ci</math> (константа зависит от языка описания программы).
Поэтому для построения i-ой программы достаточно перебрать все <math>2^{ci+1}-1</math> слов с длиной не больше <math>ci</math>
Аналогично можно построить и <math>f_i</math>. Из этого следует, что <math>c_1(n)</math> и <math>c_2(n)</math> тоже полиномиальны.
Получаем, что <math>T(n) = T(n-1) + poly</math>. Значит , <math>T(n) \le n \cdot poly </math>.
Поэтому <math>T(n) \in \tilde{P}</math> и <math>A \in P</math>.
противоречит предположению <math>P \ne NP</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>.
Теорема доказана.
