Precise Average Case Complexity Measures

TitlePrecise Average Case Complexity Measures
Publication TypeTechnical Report
Year of Publication1993
AuthorsReischuk, R.
Other Numbers837

(Pages: 36) A new definition is given for the average growth of a function f : ?* ? IN with respect to a probability measure ? on ?*. This allows us to define meaningful average case distributional complexity classes for arbitrary time bounds (previously, one could not guarantee arbitrary good precision). It is shown that basically only the ranking of the inputs by decreasing probabilities are of importance.To compare the average and worst case complexity of problems we study average case complexity 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 and optimal separation results between these average case classes. Also the worst case classes can be embedded into this hierarchy. They are shown to be identical to average case classes with respect to distributions of exponential complexity.

Bibliographic Notes

ICSI Technical Report TR-93-049

Abbreviated Authors

R. Reischuk

ICSI Publication Type

Technical Report