AN AVERAGE COMPLEXITY MEASURE THAT YIELDS TIGHT HIERARCHIES

A new definition is given for the average growth of a function f : Sig ma --> N with respect to a probability measure mu on Sigma*. This all ows us to define meaningful average distributional complexity classes for arbitrary time bounds (previously, one could not guarantee arbitra ry good precision). it is shown that, basically, only the ranking of t he inputs by decreasing probabilities is of importance. To compare the average and worst case complexity of problems, we study average compl exity classes defined by a time bound and a bound on the complexity of possible distributions. Here, the complexity is measured by the time to compute the rank functions of the distributions. We obtain tight an d optimal separation results between these average classes. Also, the worst case classes can be embedded into this hierarchy. They are shown to be identical to average classes with respect to distributions of e xponential complexity.