We show that polynomially rankable distributions, proposed in [RS93], do not provide harder instances than uniform distributions for NP problems. In particular, we show that if Levin's randomized tiling problem is solvable in polynomial time on average, then every NP problem under any p-rankable distribution is solvable in average polynomial time with respect to rankability. One of the motivations for polynomially rankable distributions was to get average-case hierarchies, and we present a reasonably tight hierarchy result for average-case complexity classes under p-time computable distributions.
Supported in part by NSF under grant CCR-9503601.
Supported in part by NSF under grants CCR-9396331 and CCR-9424164.