4. Probabilistic algorithms and the class BPP 43
1/2n
among all pairs with r = r∗. However, there are only
2n
such pairs
(corresponding to
2n
possibilities for x). The only way the fraction of bad
pairs can be smaller than
1/2n
is that there are no bad pairs at all!
Thus we conclude that there is a particular string r∗ that produces cor-
rect answers for all x of length n.
The machine M can be transformed into a polynomial-size circuit with
input (x, r). Then we fix the value of r (by setting r = r∗) and obtain a
polynomial-size circuit with input x that decides L(x) for all n-bit strings x.
This is a typical nonconstructive existence proof: we know that a “good”
string r∗ exists (by probability counting) but have no means of finding it,
apart from exhaustive search.
Remark 4.3. It might well be the case that BPP = P. Let us explain
briefly the motivation of this conjecture and why it is hard to prove.
Speaking about proved results, it is clear that BPP PSPACE. Indeed,
the algorithm that counts all values of the string r that lead to the answer
“yes” runs in polynomial space. Note that the running time of this algorithm
is
2N
poly(n), where N = |r| is the number of random bits.
On the other hand, there is empirical evidence that probabilistic algo-
rithms usually work well with pseudo-random bits instead of truly random
ones. So attempts have been made to construct a mathematical theory of
pseudo-random numbers. The general idea is as follows. A pseudo-random
generator is a function g :
Bl

BL
which transforms short truly random
strings (of length l, which can be as small as O(log L)) into much longer
pseudo-random strings (of length L). “Pseudo-random” means that any
computational device with limited resources (say, any Boolean circuit of a
given size N computing a function F :
BL
B) is unable to distinguish
between truly random and pseudo-random strings of length L. Specifically,
we require that
Pr F(g(x)) = 1 Pr F(y) = 1 δ, x
Bl,
y
BL
for some constant δ 1/2, where x and y are sampled from the uniform
distributions. (In this definition the important parameters are l and N,
while L should fit the number of input bits of the circuit. For simplicity
let us require that L = N: it will not hurt if the pseudo-random generator
produces some extra bits.)
It is easy to show that pseudo-random generators g :
BO(log L)

BL
ex-
ist: if we choose the function g randomly, it fulfills the above condition with
high probability. What we actually need is a sequence of efficiently com-
putable pseudo-random generators gL :
Bl(L)

BL,
where l(L) = O(log L).
Previous Page Next Page