109
правок
Изменения
→Доказательство: совсем почти закончено
'''Утверждение 2.''' Можно перечислить все функции из <math>\tilde{P}</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>SAT \cap \bigcup_{i=0}^{k} A_{2i}</math> отличается от <math>L(p_k)</math> элементомиз <math>\bigcup_{i=0}^{2k} A_i</math>, и существует <math>\alpha \leftin \bigcup_{i=0}^{2k+1}</math>для которого выполняется условие <math>f(\varphi alpha) \mid in \varphi bigcup_{i=0}^{2k+1}</math> и <math>[\alpha \in SAT ] \and ne [f(|\varphi|alpha)\, in SAT \vdots \, 2\rightcap \bigcup_{i=0}^{k} A_{2i}]</math>.
<math>A=\left\{x \mid f(|x|) \, \vdots \, 2 \right\}</math!--Куда-то сюда неплохо было бы добавить картинку-->
Если мы сможем построить такие <math>f(0) A_i</math>, то язык <math>L = f(1) SAT \cap \bigcup_{i= 0}^{\infty} A_{2i}</math>будет отличаться от любого полиномиального языка и ни какая полиномиальная функция не будет сводить<math>SAT</math> к <math>L</math>.
#<math>{\log_2 n} ^ {f(n-1)} \ge n</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>A_i</math> для чётных <math>i</math>, третий — для нечетных.
Логарифм в условии <math>|x| < \log_2 n</math> необходим для полиномиальности <math>f(n)</math>.
Покажем, что <math>f \in \tilde{P}</math>. Для упрощения будем считать, что алфавит <math>\Sigma={0,1}</math>.
<math>T(n) = T(n-1) + a(n)(b_1(n) + b_2(n) + b_3(n) + b_4(n)) + c_1(n) + c2_2(n)</math>, где:
*<math>T(n-1)</math> идёт на вычисление <math>f(n-1)</math>;
<math>a(n) = O\left(2^{\log_2 n}\right) = O(n)</math>, таким образом <math>a(n) \in \tilde{P}</math>
<math>b_1(n) = O\left((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>\in \tilde{P}</math>
<math>b_2(n) = O \left( 2^{\log_2 n} \log_2 n\right) = O\left(n \log_2 n\right)</math> — из <math>= O\left(n^2\right) \in \tilde{P}</math>
<math>b_3(n) = O \left(2^{\log_2 n} \log_2 n + \log_2 n\right) = O \left(n \log_2 n\right)</math> — из <math>= O\left(n^2\right) \in \tilde{P}</math>
<math>b_4(n) = Ob3(b3b1(n))</math> — из <math>= O\left(n^4\right) \in \tilde{P}</math>
Чтобы построить программу <math>p_i</math> достаточно построить <math>\tilde{p_i}</math>.
