109
правок
Изменения
→Полиномиальность f
*<tex>a(n)</tex> — время перебора всех слов <tex>x</tex> таких, что <tex>|x| < \log_2 n</tex>;
*<tex>b_1(n)</tex> — время работы <tex>p_i(x)</tex>;
*<tex>b_2(n)</tex> — время работы <tex>[x \in SAT(x)]</tex>;*<tex>b_3(n)</tex> — время работы <tex>[x \in L(x)]</tex>;*<tex>b_4(n)</tex> — время работы <tex>L([f_i(x))\in L]</tex>;
*<tex>c_1(n)</tex> — время, необходимое для построения программы <tex>p_i</tex>;
*<tex>c_2(n)</tex> — время, необходимое для построения функции <tex>f_i</tex>.
