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 eﬃciently 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 diﬃcult 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 eﬃcient 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