期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
