No NP problems averaging over ranking of distributions are harder

AbstractThis paper aims to provide a comparison between the notion of T time on average over ranking of distributions, proposed by Reischuk and Schindelhauer (1993), and the notion of T time on average, proposed by Ben-David et al. (1992). The latter is a direct generalization of Levin's notion of average polynomial time (Levin, 1986). In particular, we show that for any problem D and any ranking function ρ, if ρ(D) is solvable in time T on average over a uniform distribution and ρ is computable in polynomial time, then Dis solvable in time T ο p + q on average over ρ, where p and q are polynomials depending on ρ. We then show that, under a randomized reduction, there is a complete problem (D,ρ) for distributional NP problems with respect to ranking such that ρ(D) ϵ NP and if ρ(D) is solvable in time T on average over a uniform distribution, then D is solvable in time T(O(n)) + p(n) on average over ρ, where p is the time bound for computing ρ. Hence, no NP problems averaging over ranking of distributions are harder than averaging over uniform distributions in the notions of polynomial-time or sub-exponential-time solvability. Finally, we show that there is a reasonable tight hierarchy for the notion of T time on average over uniform distributions