Levin 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-David et al. use the notation of ( C, F) to denote the set of randomized decision problems (L, +) such that L is 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 that L is 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, V), where P-comp denotes the set of density functions whose distributions are computable in polynomial time, and V 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 worstcase 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 polynomialtime computations for arbitrary distributions from a fixed set, and it is used to characterize the worst-case complexity classes 2 p k and 7 p k of the polynomial-time hierarchy.