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
Previous Page Next Page