УДК 519.7
Средняя сложность симметрических булевых функций / Чашкин А.В. // Вестн. Моск. ун-та. Сер. 1,
Математика. Механика.
C. 16-19.
Изучается среднее время вычисления значений симметрических
булевых функций при помощи неветвящихся программ
с условной остановкой. Показано, что
с точностью до постоянного множителя среднее время вычисления
симметрической функции 
совпадает с величиной 
, где
равно максимальному числу последовательных слоев,
на которых функция принимает одинаковые значения.
Библиогр. 5.
