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 eﬃciently com-

putable pseudo-random generators gL :

Bl(L)

→

BL,

where l(L) = O(log L).