Изменения

Действительно, рассмотрим последовательность всех программ , упорядоченных по длине,<math> \tilde{p_1p_0}, \tilde{p_2p_1}, \ldots, \tilde{p_n}, \ldots</math>

Определим <math>f(n)</math>. Для этого рассмотрим два три случая:*'''Случай #<math>{\log_2 n} ^ {f(n-1)} \ge n</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>.*'''Случай 2:''' #<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>c_1c_2(n)</math> — построение программы <math>f_i</math>.

<math>a(n) = O\approx left(2^{\log_2 n} \right) = O(n)</math>, таким образом <math>a(n) \in \tilde{P}</math>

<math>b_1(n) = O\approxleft((i(\log_2 n)^i\right) = O\left(f(n-1)(\log_2 n)^{f(n-1)}\right) = O\left(f(n-1)n\right) = O(n^2) </math> что-то, —тоже из <math>\tilde{P}</math>

<math>b_2(n) = O \approx left( 2^{\log_2 n} \log_2 n \right) = O\left(n \log_2 n\right)</math>, — из <math>\tilde{P}</math>

<math>b_3(n) = O \approx left(2^{\log_2 n} \log_2 n + \log_2 n\right) = O \left(n \log_2 n\right)</math>, — из <math>\tilde{P}</math>

<math>b_4(n) \approx </math> что-то типа <math>b_3= O(b3(n)</math>, но с оценкой на <math>|f_i(x)|</math>вместо <math>log_2 n</math>, — из <math>\tilde{P}</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}</math> слов с длиной меньше, чем <math>ci</math>,и вывести i-ое, являющееся программой. Такой способ требует <math>O(2^{ci}i) = O(2^{\log_2 n} \log_2 n) = O(n^2)</math> времени.Аналогично можно построить и <math>f_i</math>. Из этого следует, что <math>c_1(n)</math> и <math>c_2(n)</math> тоже полиномиальны.

В результате всё почти хорошоТаким образом, <math>f</math> полиномиальна, а значит <math>A \in P</math>. Предположим, что <math>\lim_{n \to \infty}f(n) = 2i</math>. Это значит, что фунция «застряла» в ветке «иначе» случая два,но из этого следует, что <math>SAT</math> отличается от <math>L(p_i)</math> лишь на конечное число элементов. Этовлечёт за собой принадлежность <math>SAT</math> к <math>P</math>, что противоречит предположению <math>P \ne NP</math>. Аналогично, в случае, если <math>\lim_{n \to \infty}f(n) = 2i+1</math>. Тогда функция «застряла» в ветке «иначе» случая три.Следствием этого является то, что <math>SAT</math> функцией <math>p_i</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>.