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 suffices 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).
Previous Page Next Page