This paper studies the complexity of the polynomial-time samplable
(P-samplable) distributions, which can be approximated within an
exponentially small factor by sampling algorithms in time polynomial
in the length of their outputs. The paper shows common assumptions in
complexity theory that yield the separation of polynomial-time
samplable distributions from the polynomial-time computable
distributions with respect to polynomial domination,
average-polynomial domination, polynomial equivalence, and
average-polynomial equivalence.

This paper studies the complexity of the polynomial-time
samplable (P-samplable) distributions, which can be approximated
within an exponentially small factor by sampling algorithms in time
polynomial in the length of their outputs. The paper shows common
assumptions in complexity theory that yield the separation of
polynomial-time samplable distributions from the polynomial-time
computable distributions with respect to polynomial domination,
average-polynomial domination, polynomial equivalence, and
average-polynomial equivalence.

This paper studies distributions which
can be ``approximated'' by sampling algorithms in time polynomial in
the length of their outputs. First, it is known that if
polynomial-time samplable distributions are polynomial-time
computable, then NP collapses to P. This paper shows by a simple
counting argument that every polynomial-time samplable distribution is
computable in polynomial time if and only if so is every #P
function. By this result, the class of polynomially samplable
distributions contains no universal distributions if FP=#P.
Second, it is also known that there exists polynomially samplable
distributions which are not polynomially dominated by any
polynomial-time computable distribution if strongly one-way functions
exist. This paper strengthens this statement and shows that an
assumption, namely, NP\subseteq\BPP leads to the same
consequence. Third, this paper shows that P=NP follows from the
assumption that every polynomial-time samplable distribution is
polynomially equivalent to some polynomial-time computable
distribution.