О реализации булевых функций программами одного типа

Рассмотрена сложность вычисления булевых функций неветвящимися программами с условной остановкой, допускающими только однократное использование промежуточных значений. Показано, что средняя сложность вычисления каждой функции $n$ переменных такими программами не превосходит величины $\frac12\frac{2^n}{\log n}(1+o(1))$ и средняя сложность почти каждой функции $n$ переменных не меньше чем $\frac12\frac{2^n}{\log n}(1+o(1))$.
Библиогр. 2.