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
(gi + X) = G is positive; in other words, if
(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 −
Summing these probabilities over
all u ∈ G, we see that the probability of the event
(gi + X) = G does not
exceed |G|(1 −
Thus condition (5.2) is true if
1 − |X|/|G|
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
ε (i.e., x / ∈ L) and when
1 − ε (i.e., x ∈ L), respectively. Thus we get the inequalities
εm 1 and
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 ε =
Thus we need to solve the system
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
|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.