Malign distributions for average case circuit complexity

In contrast to machine models like Turing machines or random access machine s, circuits are a static computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. The refore, size and depth are natural and simple measures for circuits and pro vide a worst-case analysis. We consider a new model in which an internal ga te is evaluated as soon as its result has been determined by a partial assi gnment of its inputs. This way, a dynamic notion of delay is obtained which gives rise to an average case measure for the time complexity of circuits. In a previous paper we have obtained tight upper and lower bounds for the average case complexity of several basic Boolean functions. This paper exam ines the asymptotic average case complexity for the set of all n-ary Boolea n functions. In contrast to worst case analysis a simple counting argument does not work. We prove that with respect to the uniform probability distri bution almost all Boolean functions require at least n - log n - log log n expected time. On the other hand, there is a significantly large subset of functions that can be computed with a constant average delay. Finally, for an arbitrary Boolean function we compare its worst case and average case co mplexity. It is shown that for each function that requires circuit depth d, i.e. of worst case complexity d, the expected time complexity will be at l east d - log n - log d with respect to an explicitly defined probability di stribution. In addition, a nontrivial upper bound on the complexity of such a distribution will be obtained. (C) 1999 Academic Press.