期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We present a simple proof to the existence of a probability ensemble
with tiny support which cannot be distinguished from the uniform ensemble
by any recursive computation.
Since the support is tiny (i.e, sub-polynomial),
this ensemble can be distinguish from the uniform ensemble
by a (non-uniform) family of small circuits.
It also provides an example of an ensemble which cannot be (recursively)
distinguished from the uniform by one sample, but can be so distinguished
by two samples.
In case we only wish to fool probabilistic polynomial-time algorithms
the ensemble can be constructed in slightly super-exponential time.
