О сравнении сложностей недетерминированных ветвящихся $k$-программ

Проводится сравнение сложностей реализации булевых функций недетерминированными синтаксическими ветвящимися $k$- и $s_k$-программами. Показывается, что для любого натурального $k$, $k\geqslant 2$, существует последовательность булевых функций такая, что сложность реализации каждой функции из этой последовательности в классе недетерминированных синтаксических ветвящихся $k$-программ в экспоненциальное число раз (по числу переменных булевой функции) превосходит сложность реализации той же функции в классе недетерминированных синтаксических ветвящихся $\lceil k\ln k/\ln2+C\rceil$-программ, где $C$ – константа, не зависящая от $k$. Кроме того, показано, что для любых натуральных $N$ и $k(N)$, где $4\leqslant k(N)<C_2\sqrt{\ln N}/\ln\ln N$, а $C_2<\sqrt 2$ – не зависящая от $k$ и $N$ константа, существует булева функция от $N$ переменных такая, что сложность реализации этой функции в классе недетерминированных синтаксических ветвящихся $k$-программ в экспоненциальное число раз (по $N$) превосходит сложность реализации той же функции в классе недетерминированных синтаксических ветвящихся $\lceil k\ln k/\ln2+C\rceil$-программ. Ил. 1, библиогр. 11.