171
правка
Изменения
м
Определим <tex>g</tex> рекурсивно. Положим <tex>g(0) = g(1) = 1</tex>. Для <tex>n \ge 1</tex>:построим <tex>g(n + 1)</tex> рекурсивно — с помощью <tex>g(1), g(2), \ldots, g(n)</tex>.
Иначе * Пусть вычисленное значение <tex> n > (\log_2 n)^{g(n)} \ge \log_2 n</tex>; значения чётно. Определим <tex>g(mn+1)</tex> для <tex>m \le \log_2 n</tex> уже известны.так:
* <tex>g(n) = 2i</tex>.
Поменял описание g
=== Построение <tex>g</tex> ===
* Если <tex>(\log_2 n)^{g(n)} \ge n</tex>, <tex>g(n+1) := g(n)</tex>.
for <tex>x</tex> : <tex>|x| \le \log_2 n</tex>
if <tex>M_i(x)</tex> and <tex>[g(|x|) \equiv 1 \pmod{2}</tex> or <tex>x \not \in \mathrm{SAT}]</tex>
<tex>g(n+1) := g(n)</tex>
* Пусть вычисленное значение <tex>g(n) = 2i </tex> нечётно. Определим <tex>g(n+ 1)</tex>.так:
for <tex>x</tex> : <tex>|x| \le \log_2 n, |f_i(x)| \le \log_2 n</tex>
if <tex>x \in \mathrm{SAT}</tex> and <tex>[g(|x|) \equiv 1 \pmod{2}</tex> or <tex>f_i(x) \not \in \mathrm{SAT}]</tex>
