×

Hitting sets derandomize BPP. (English) Zbl 1046.68536

Meyer auf der Heide, Friedhelm (ed.) et al., Automata, languages and programming. 23rd international colloquium, ICALP ’96, Paderborn, Germany, July 8-12, 1996. Proceedings. Berlin: Springer (ISBN 3-540-61440-0/pbk). Lect. Notes Comput. Sci. 1099, 357-368 (1996).
Summary: We show that hitting sets can derandomize any probabilistic, two-sided error 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, we generalize this result by showing that the existence of a quick hitting set generator with price \(k\) implies that \(\text{BPTIME}(t)\subset \text{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, this can be considered as another strong indication that the gap between probabilistic and deterministic computational power is not large.
For the entire collection see [Zbl 0851.00043].

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDFBibTeX XMLCite