Том 6, серия 1, номер 1, 1999 г., Стр. 65-85

УДК 519.714
Е. А. Окольнишникова
О сравнении сложностей недетерминированных ветвящихся $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.

Окольнишникова Е. А. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 1 июня 1998 г.