文章基本信息

标题：Polynomial Time Samplable Distributions
本地全文：下载
作者：Tomoyuki Yamakami
期刊名称：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.
关键词：average-case complexity, domination condition, sampling algorithm, strong one-way functions