Structural Average Case Complexity

AbstractLevin introduced an average-case complexity measure, based on a notion of “polynomial on average,” and defined “average-case polynomial-time many-one reducibility” among randomized decision problems. We generalize his notions of average-case complexity classes, Random-NP and Average-P. Ben-Davidet al. use the notation of 〈C, F〉 to denote the set of randomized decision problems (L, μ) such thatLis a set in C andμis a probability density function in F. This paper introduces Aver〈C, F〉 as the class of randomized decision problems (L, μ) such thatLis computed by a type-C machine onμ-average andμis a density function in F. These notations capture all known average-case complexity classes as, for example, Random-NP= 〈NP, P-comp〉 and Average-P=Aver〈P, ∗〉, where P-comp denotes the set of density functions whose distributions are computable in polynomial time, and ∗ denotes the set of all density functions. Mainly studied are polynomial-time reductions between randomized decision problems: many–one, deterministic Turing and nondeterministic Turing reductions and the average-case versions of them. Based on these reducibilities, structural properties of average-case complexity classes are discussed. We give average-case analogues of concepts in worst-case complexity theory; in particular, the polynomial time hierarchy and Turing self-reducibility, and we show that all known complete sets for Random-NP are Turing self-reducible. A new notion of “real polynomial-time computations” is introduced based on average polynomial-time computations for arbitrary distributions from a fixed set, and it is used to characterize the worst-case complexity classesΔpkandΣpkof the polynomial-time hierarchy