Average case complexity for finite Boolean functions (Q5954082)

A straight-line program is a sequence of instructions, each consisting of a unary or binary Boolean function with arguments either input variables or values computed by some previous instructions. A straight-line program with conditional stop may additionally use a two argument stop instruction with the semantics that the computation of the program stops and the second argument is the result of the computation if the first argument is equal to one; otherwise execution of the program is continued with the next instruction. This means that different inputs may lead to computations of different time complexity, and hence it makes sense to talk about the average time complexity to compute a Boolean function. In the present paper it is shown that for almost every Boolean function, the average time complexity is up to a constant factor the same as the usual straight-line program complexity (i.e., Boolean circuit size). On the other hand, a family of functions is constructed that has average time complexity that is (up to a constant factor) less than the usual straight-line program complexity by a factor of \((2^n/n)^{1/2}\).