Revision #1 Authors: A. E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

Accepted on: 9th February 1996 00:00

Downloads: 1353

Keywords:

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.

TR95-061 Authors: Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

Publication: 6th December 1995 19:25

Downloads: 1062

Keywords:

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, we

generalize this result by showing 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; this can be

considered as another strong indication that the gap between

probabilistic and deterministic computational power is not large.