46 1. Classical Computation

Π2: the sets Lb for the same class of games, i.e., the sets of the form

{x : ∀ w1 ∃ b1 B(x, w1,b1)}.

. . .

Σk: the sets Lw for games of length k (the last move is made by W if k

is odd or by B is k is even), i.e., the sets

{x : ∃ w1 ∀ b1 . . . Qk yk W (x, w1,b1,... )}

(if k is even, then Qk = ∀, yk = bk/2; if k is odd, then Qk = ∃, yk =

w(k+1)/2).

Πk: the sets Lb for the same class of games, i.e., the sets

{x : ∀ w1 ∃ b1 . . . Qk yk B(x, w1,b1,... )}

(if k is even, then Qk = ∃, yk = bk/2; if k is odd, then Qk = ∀, yk =

w(k+1)/2).

. . .

Evidently, complements of Σk-sets are Πk-sets and vice versa: Σk =

co-Πk, Πk = co-Σk.

Theorem 5.1 (Lautemann [46]). BPP ⊆ Σ2 ∩ Π2.

Proof. Since BPP=co-BPP, it suﬃces to show that BPP ⊆ Σ2.

Let us assume that L ∈ BPP. Then there exist a predicate R (com-

putable in polynomial time) and a polynomial p such that the fraction

|Sx|/2N

, where

Sx = y ∈

BN

: R(x, y) , N = p(|x|), (5.1)

is either large (greater than 1 − ε for x ∈ L) or small (less than ε for x / ∈ L).

To show that L ∈ Σ2, we need to reformulate the property “X is a large

subset of G” (where G is the set of all strings y of length N) using existential

and universal quantifiers.

This could be done if we impose a group structure on G. Any group

structure will work if the group operations are polynomial-time computable.

For example, we can consider an additive group formed by bit strings of a

given length with bit-wise addition modulo 2.

The property that distinguishes large sets from small ones is the follow-

ing: “several copies of X shifted by some elements cover G”, i.e.,

∃ g1,...,gm

i

(gi + X) = G , (5.2)

where “+” denotes the group operation. To choose an appropriate value for

m, let us see when (5.2) is guaranteed to be true (or false).