5. The hierarchy of complexity classes 47

It is obvious that condition (5.2) is false if

m|X| |G|. (5.3)

On the other hand, (5.2) is true if for independent random g1,...,gm ∈ G

the probability of the event

i

(gi + X) = G is positive; in other words, if

Pr

i

(gi + X) = G 1. Let us estimate this probability.

The probability that a random shift g + X does not contain a fixed

element u ∈ G (for a given X and random g) is 1−|X|/|G|. When g1,...,gm

are chosen independently, the corresponding sets g1 + X, . . . , gm + X do not

cover u with probability (1 −

|X|/|G|)m.

Summing these probabilities over

all u ∈ G, we see that the probability of the event

i

(gi + X) = G does not

exceed |G|(1 −

|X|/|G|)m.

Thus condition (5.2) is true if

|G|

(

1 − |X|/|G|

)m

1. (5.4)

Let us now apply these results to the set X = Sx (see formula (5.1)).

We want to satisfy (5.3) and (5.4) when

|Sx|/2N

ε (i.e., x / ∈ L) and when

|Sx|/2N

1 − ε (i.e., x ∈ L), respectively. Thus we get the inequalities

εm 1 and

2N εm

1, which should be satisfied simultaneously by a

suitable choice of m. This is not always possible if N and ε are fixed.

Fortunately, we have some flexibility in the choice of these parameters. Using

“amplification of probability” by repeating the computation k times, we

increase N by factor of k, while decreasing ε exponentially. Let the initial

value of ε be a constant, and λ given by (4.1). The amplification changes N

and ε to N = kN and ε =

λk.

Thus we need to solve the system

λkm

1,

2kN λkm

1

by adjusting m and k. It is obvious that there is a solution with m = O(N)

and k = O(log N).

We have proved that x ∈ L is equivalent to the following

Σ2-condition:

∃g1,...,gm ∀y

(

|y| = p (|x|)

)

⇒

(

(y ∈ g1 + Sx) ∨ · · · ∨ (y ∈ gm + Sx)

)

.

Here p (n) = kp(|x|) (k and m also depend on |x|), whereas Sx is the “am-

plified” version of Sx.

In other words, we have constructed a game where W names m strings

(group elements) g1,...,gm, and B chooses some string y. If y is covered by

some gi + Sx (which is easy to check: it means that y − gi belongs to Sx),

then W wins; otherwise B wins. In this game W has a winning strategy if

and only if Sx is big, i.e., if x ∈ L.