44 1. Classical Computation
If such pseudo-random generators exist, we can use their output instead of
truly random bits in any probabilistic algorithm. The definition of pseudo-
randomness guarantees that this will work, provided the running time of
the algorithm is limited by c

L (for a suitable constant c) and the error
probability ε is smaller than 1/2 δ. (With pseudo-random bits the error√
probability will be ε + δ, which is still less than 1/2. The estimate c L
comes from the simulation of a Turing machine by Boolean circuits, see
Theorem 2.2.) Thus we decrease the number of needed genuine random
bits from L to l. Then we can derandomize the algorithm by trying all
2l
possibilities. If l = O(log L), the resulting computation has polynomial
complexity.
We do not know whether efficiently computable pseudo-random gener-
ators exist. The trouble is that the definition has to be satisfied for “any
Boolean circuit of a given size”; this condition is extremely hard to deal
with. But we may try to reduce this problem to a more fundamental one
obtaining lower bounds for the circuit complexity of Boolean functions.
Even this idea, which sets the most difficult part of the problem aside, took
many years to realize. Much work in this area was done in 1980’s and early
1990’s, but the results were not as strong as needed. Recently there has been
dramatic progress leading to more efficient constructions of pseudo-random
generators and new derandomization techniques. It has been proved that
BPP = P if there is an algorithm with running time exp(O(n)) that com-
putes a sequence of functions with circuit complexity exp(Ω(n)) [32]. We
also mention a new work [69] in which pseudo-random generators are con-
structed from arbitrary hard functions in an optimal (up to a polynomial)
way.
5. The hierarchy of complexity classes
Recall that we identify languages (sets of strings) and predicates (and x L
means L(x) = 1).
Definition 5.1. Let A be some class of languages. The dual class co-A
consists of the complements of all languages in A. Formally,
L co-A
(B∗
\ L) A.
It follows immediately from the definitions that P = co-P, BPP =
co-BPP, PSPACE = co-PSPACE.
5.1. Games machines play. Consider a game with two players called
White (W) and Black (B). A string x is shown to both players. After that,
players alternately choose binary strings: W starts with some string w1, B
Previous Page Next Page