Average complexity of symmetric Boolean functions (Q1878531)

The author studies the average complexity of symmetric Boolean functions. The functions are computed by means of nonbranching programs with conditional halting. The programs under consideration are sequences of elementary operators of two types: functional operators and halting operators. It is shown that an average time of computing the symmetric function \(f\) coincides with the value \(\,n-\mu(f)+2\), where \(\mu\) is a maximal number of successive layers on which the function \(f\) takes similar values.