4. Probabilistic algorithms and the class BPP 37

wrong with probability

perror ≤

S⊆{1,...,k},

|S|≤k/2

(1 −

ε)|S|εk−|S|

=

(

(1 − ε)ε

)k/2

S⊆{1,...,k},

|S|≤k/2

ε

1 − ε

k/2−|S|

(1 − ε)ε

k

2k

=

λk,

where λ = 2 ε(1 − ε) 1.

(4.1)

If k is big enough, the effective error probability will be as small as we

wish. This is called amplification of probability. To make the quantity perror

smaller than a given number ε , we need to set k = Θ(log(1/ε )). (Since ε

and ε are constants, k does not depend on the input. Even if we require

that ε = exp(−p(n)) for an arbitrary polynomial p, the composite TM still

runs in polynomial time.)

Let us we give an equivalent definition of the class BPP using predicates

in two variables (this definition is similar to Definition 3.2).

Definition 4.2. A predicate L belongs to BPP if there exist a polynomial

p and a predicate R, decidable in polynomial time, such that

L(x) = 1 ⇒ the fraction of strings r of length p(|x|) satisfying R(x, r)

is greater than 1 − ε;

L(x) = 0 ⇒ the fraction of strings r of length p(|x|) satisfying R(x, r)

is less than ε.

Theorem 4.1. Definitions 4.1 and 4.2 are equivalent.

Proof. Definition 4.1 ⇒ Definition 4.2. Let R(x, r) be the following pred-

icate: “M says ‘yes’ for the input x using r1,...,rpn as the random bits”

(we assume that a coin is tossed at each step of M). It is easy to see that

the requirements of Definition 4.2 are satisfied.

Definition 4.2 ⇒ Definition 4.1. Assume that p and R are given. Con-

sider a PTM that (for input x) randomly chooses a string r of length p(|x|),

making p(|x|) coin tosses, and then computes R(x, r). This machine satisfies

Definition 4.1 (with a different polynomial p instead of p).

Definition 4.2 is illustrated in Figure 4.1. We represent a pair (x, y) of

strings as a point and draw the set S = (x, y) : (|y| = p(|x|)) ∧ R(x, y) .

For each x we consider the x-section of S defined as Sx = {y : (x, y) ∈ S}.

The set S is rather special in the sense that, for any x, either Sx is large

(contains at least 1 − ε fraction of all strings of length p(|x|) ) or is small