109
правок
Изменения
→Построение f
*:<tex>f(n) = f(n-1)</tex>;
*<tex>f(n-1)=2i</tex>:
*:если существует <tex>x</tex> такой, что <tex>|x| < \log_2 n</tex> и <tex>p_i(x) \ne [x \in L(x)]</tex>, то <tex>f(n) = f(n-1)+1</tex>, иначе <tex>f(n) = f(n-1)</tex>;
*<tex>f(n-1)=2i+1</tex>:
*:если существует <tex>x</tex> такой, что <tex>|x| < \log_2 n</tex>,<tex>|f_i(x)| < \log_2 n</tex> и <tex>[x \in SAT(x) ] \ne L([f_i(x))\in L]</tex>, то <tex>f(n) = f(n-1)+1</tex>, иначе <tex>f(n) = f(n-1)</tex>.
Заметим, что вызовы <tex>L([\alpha)\in L]</tex> делаются для <tex>\alpha</tex>, для которых <tex>f</tex> уже построена.
Первый случай позволяет сказать, что <tex>f(n)</tex> ограничена <tex>O\left(\log_{\log_2 n} n\right) = O(\log_2 n)</tex>.
