Средняя сложность симметрических булевых функций

Изучается среднее время вычисления значений симметрических булевых функций при помощи неветвящихся программ с условной остановкой. Показано, что с точностью до постоянного множителя среднее время вычисления симметрической функции $f$ совпадает с величиной $n-\mu(f)+2$, где $\mu(f)$ равно максимальному числу последовательных слоев, на которых функция $f$ принимает одинаковые значения.
Библиогр. 5.