文章基本信息

标题：Hitting sets derandomize BPP
本地全文：下载
作者：Alexander E. Andreev ; Andrea E. F. Clementi ; Jose' D. P. Rolim 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that hitting sets can derandomize any BPP-algorithm. This gives a positive answer to a fundamental open question in probabilistic algorithms. More precisely, we present a polynomial time deterministic algorithm which uses any given hitting set to approximate the fractions of 1's in the output of any boolean circuit of polynomial size. This new algorithm implies that if a quick hitting set generator with logarithmic price exists then BPP=P. Furthermore, the algorithm can be applied in order to show that the existence of a quick hitting set generator with price k implies that BPTIME(t) <= DTIME(2^{O(k(t^{O(1)}))}). The existence of quick hitting set generators is thus a new weaker sufficient condition to obtain BPP=P.
关键词：Approximation Algorithms, derandomization, Probabilistic Complexity Classes