109
правок
Изменения
м
→Доказательство
из <math>NP \setminus (P \cup NPC)</math>.
'''Утверждение 1.''' Можно перечислить (возможно , с повторениями) все языки из <math>P</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>T(n) \in \tilde{P}</math> и <math>A \in P</math>.
Таким образом, <math>f</math> полиномиальна, а значит и <math>A \in P</math>.
Предположим, что <math>\lim_{n \to \infty}f(n) = 2i</math>. Это значит, что фунция «застряла» в ветке «иначе» случая два,
