Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR95-039 | 26th July 1999 00:00

Polynomial Time Samplable Distributions Revision of: TR95-039

RSS-Feed




Revision #2
Authors: Tomoyuki Yamakami
Accepted on: 26th July 1999 00:00
Downloads: 3579
Keywords: 


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





Revision #1
Authors: Tomoyuki Yamakami
Accepted on: 26th July 1999 00:00
Downloads: 3582
Keywords: 


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.


Paper:

TR95-039 | 11th July 1995 00:00

Polynomial Time Samplable Distributions





TR95-039
Authors: Tomoyuki Yamakami
Publication: 17th July 1995 02:58
Downloads: 3683
Keywords: 


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.



ISSN 1433-8092 | Imprint