Бюрократы, editor, Администраторы
422
правки
Изменения
Ой, зря я сломал программы. Починил.
* <tex>g(n) = 2i</tex>.
for <tex>x</tex>: <tex>|x| \le \log_2 n</tex>
if <tex>M_i(x)</tex> and (<tex>g(|x|) \% 2 = 1</tex> or <tex>x \not \in \mathrm{SAT})</tex>
<tex>g(n+1) := g(n)+1</tex>
return else if <tex>! M_i(x)</tex> and (<tex>g(|x|) \% 2 = 0</tex> and <tex>x \in \mathrm{SAT})</tex>
<tex>g(n+1) := g(n)+1</tex>
* <tex>g(n) = 2i + 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(|f_i(x)|) \% 2 = 1</tex> or <tex>f_i(x) \not \in \mathrm{SAT})</tex>
<tex>g(n+1) := g(n)+1</tex>, return else if <tex>x \not \in \mathrm{SAT}</tex> and (<tex>g(|f_i(x)|) \% 2 = 0</tex> and <tex>f_i(x) \in \mathrm{SAT})</tex> <tex>g(n+1) := g(n)+1</tex>, return else <tex>g(n+1) := g(n)</tex>
=== Корректность алгоритма ===
