On the mean time for computing the values of elementary Boolean functions

The disjunction, conjunction, and linear function, each depending on an increasing number of arguments, are computed by straight-line programs with a conditional stop. Asymptotically exact formulas for the average-case complexity of these functions are found. It is shown that the average-case complexities of disjunction and conjunction are constants and the average-case complexity of the linear function coincides with its circuit size.
The research was supported by the Russian Foundation for Basic Research, grant 99-01-01175, and the Federal Program 'Integration', grant 473.