A note on universal distributions for polynomial-time computable distributions

摘要

Polynomial-time computable as well as polynomial-time samplable distributions play a central role in the theory of average-case complexity. It is known that for every constant k there are polynomial-time samplable distributions which dominate every distribution that is samplable in time O(n/sup k/). The result is based on the fact that there exists an enumeration of the O(n/sup k/)-time samplable distributions. No such enumeration is known for the polynomial-time computable distributions. In this note we show that never the less for every constant k there are polynomial-time computable distributions which dominate every distribution that is computable in time O(n/sup k/). Both results imply that a paddable set is polynomial-time on average under every polynomial-time samplable (polynomial-time computable) distribution if the set is polynomial time on average under a fixed polynomial-time samplable (polynomial-time computable) distribution. This is not true for sets in general, in particular there is no universal distribution for the set of polynomial-time computable distributions.