文章基本信息

标题：Computational Indistinguishability -- Algorithms vs. Circuits
本地全文：下载
作者：Oded Goldreich, Bernd Meyer
期刊名称：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.