42 1. Classical Computation
Note that U
(l)
= {1} and V
(l)
= {1}. Specifically, both U
(l)
and V
(l)
contain
the residues that correspond to −1. Indeed, both U and V contain −1, and
(−1)l
= −1 since l is odd.
Going from right to left, we find the first place where one of the sets
U
(m),
V
(m)
contains an element different from 1. It other words, we find
t =
2sl
such that 0 s k, U
(2t)
= {1}, V
(2t)
= {1}, and either U
(t)
= {1}
or V
(t)
= {1}.
We will prove that Test 2 shows (with probability at least 1/2) that q is
composite. By our assumption
a2t
= 1, so we need to know the probability
of the event
at
= ±1. Let us consider two possibilities.
Case 2a. One of the sets U
(t),
V
(t)
equals {1} (for example, let U
(t)
=
{1}). This means that for any a the pair
(
(at
mod u),
(at
mod v)
)
has 1 as
the first component. Therefore
at
= −1, since −1 is represented by the pair
(−1, −1).
At the same time, V
(t)
= {1}; therefore the probability that
at
has 1 in
the second component is at most 1/2 (by Lagrange’s theorem; cf. proof of
Lemma 4.2). Thus Test 2 says “composite” with probability at least 1/2.
Case 2b. Both sets U
(t)
and V
(t)
contain at least two elements: |U
(t)|
=
c 2, |V
(t)|
= d 2. In this case
at
has 1 in the first component with
probability 1/c (there are c equiprobable possibilities) and has 1 in the
second component with probability 1/d. These events are independent due
to the Chinese remainder theorem, so the probability of the event
at
= 1
is 1/cd. For similar reasons the probability of the event
at
= −1 is either
0 or 1/cd. In any case the probability of the event
at
= ±1 is at most
2/cd 1/2.
4.3. BPP and circuit complexity.
Theorem 4.4. BPP P/ poly.
Proof. Let L(x) be a BPP-predicate, and M a probabilistic TM that de-
cides L(x) with probability at least 1 ε. By running M repeatedly we
can decrease the error probability. Recall that a polynomial number of rep-
etitions leads to the exponential decrease. Therefore we can construct a
polynomial probabilistic TM M that decides L(x) with error probability
less that ε
1/2n
for inputs x of length n.
The machine M uses a random string r (one random bit for each step).
For each input x of length n, the fraction of strings r that lead to an incorrect
answer is less than
1/2n.
Therefore the overall fraction of “bad” pairs (x, r)
among all such pairs is less than
1/2n.
[If one represents the set of all pairs
(x, r) as a unit square, the “bad” subset has area
1/2n.]
It follows that
there exists r = r∗ such that the fraction of bad pairs (x, r) is less than
Previous Page Next Page