__
Revision #2 to TR95-039 | 26th July 1999 00:00
__
#### Polynomial Time Samplable Distributions Revision of: TR95-039

**Abstract:**
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.

__
Revision #1 to TR95-039 | 26th July 1999 00:00
__
#### Polynomial Time Samplable Distributions Revision of: TR95-039

**Abstract:**
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.

__
TR95-039 | 11th July 1995 00:00
__

#### Polynomial Time Samplable Distributions

**Abstract:**
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.