Вестник Московского Университета. Математика, Механика - Содержание


УДК 519.7

Средняя сложность симметрических булевых функций / Чашкин А.В. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2003. N.1 C. 16-19.

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

Библиогр. 5.

К оглавлению номера  Go!