Malign Distributions for Average Case Circuit Complexity (Extended Abstract)

In contrast to machine models like Turing machines or random access machines, circuits are a rigid computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. Therefore, in complexity theory only worst case complexity measures have been used to analyse this model. In [JRS 94] we have defined an average case measure for the time complexity of circuits. Using this notion tight upper and lower bounds could be obtained for the average case complexity of several basic Boolean functions. In this paper we will examine the asymptotic average case complexity of the set of n-input Boolean functions. In contrast to the worst case a simple counting argument does not work. We prove that almost all Boolean function require at least n \Gamma log n \Gamma llog n expected time even for the uniform probability distribution. On the other hand, we show that there are significant subsets of functions that can be computed with a constant average..