109
правок
Изменения
м
→Построение f
*:если существует <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>|f_i(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>L(\alpha)</math> делаются для <math>\alpha</math>, для которых <math>f</math> уже построена.
Первый случай позволяет сказать, что <math>f(n)</math> ограничена <math>O\left(\log_{\log_2 n} n\right) = O(\log_2 n)</math>.
