From this Swapping Lemma, we obtain the following decisive characterization of BPP. By changing the above quantifier Observe that in the direction (a) In the last section, we proved that BPP is contained in the second level of the polynomial-time hierarchy, but we do not know whether BPP is contained in NP or whether NP is contained in BPP. In this section, we study this question in the relativized form. First, we need to define the oracle PTMs and to extend the class BPP to the relativized class BPPA relative to a set A. The oracle probabilistic Turing machine M can be easily defined as an oracle DTM To allow simulation and diagonalization, we need an effective enumeration of polynomial-time oracle PTMs. Such an enumeration exists because the class of all polynomial-time deterministic oracle machines We now consider the relation between BPPA, PA, and NPA. First, we show that relative to a random oracle A, Next we consider the relation between BPP and NP. The following result follows immediately from the above result and Theorem 4.19. In the following, we show that some other possible relations between the classes P, RP, coRP, BPP, and NP are possible. First, we show separation results. Finally, we remark that it is possible that the class NPA collapses to the class RPA but not to PA(see Exercise 8.19), and it is possible that NPA is different from PA and yet RPA collapses to PA (by Theorems 4.19 and 8.35). 8.1 Based on Lemma 8.5, find a polynomial-time algorithm that computes the Legendre–Jacobi symbols 8.2 The problem STRING MATCHING asks, for given strings 8.3 Prove Proposition 8.8. Note that if 8.4 Consider the following alternative model of probabilistic Turing machines. A PTM M is a DTM equipped with a random-bit generator and three distinguished states: the random state, the zero state, and the one state. When M is not in the random state, it behaves exactly the same as a deterministic machine. When M is in the random state, the random-bit generator generates a bit 8.5 The above PTMs use a fixed random-bit generator ϕ. We extend it to allow the random number generator to generate a random number in any given range. Let M be a PTM defined as in Exercise 8.4 that is equipped with a random number generator ψ that on any input k > 0 outputs a number 8.6 For any polynomial-time PTM M, let 8.7 Show that the class PP is closed under union, intersection, and complementation. [Hint: For intersection, we need to find a PTM M such that 8.8 A polynomial-time oracle DTM M is called a log-query machine if for any input x of length and for any oracle A, it makes at most 8.9 Compare the class 8.10 Formally, define the notion of space complexity of a PTM. Let 8.11 Prove the following second form of the Swapping Lemma: Let 8.12 Let 8.13 Let Let 8.14 Recall the notion of pseudorandom generators introduced in Exercise 4.7. We say a pseudorandom generator f is an nc-generator, where c > 0 is a constant, if 8.15 For each n ≥ 1, let 8.16 Let almost-P be the class of sets that are computable in deterministic polynomial time with respect to a random oracle, that is, 8.17 8.18 Prove that there exists an oracle A such that 8.19 Prove that there exists an oracle A such that Randomized algorithms can probably be traced back to the early days of programming. Two seminal papers on randomized algorithms for primality testing are Rabin (1976, 1980) and Solovay and Strassen (1977). Our Example 8.4 is based on Solovay and Strassen's algorithm. Adleman and Huang (1987) gave a proof that the problem PRIME is in ZPP. Rabin (1976) also includes randomized algorithms for problems in computational geometry. Our Example 8.2 is based on the algorithms given in Schwartz (1980), and Example 8.24 is from Adleman, Manders, and Miller (1977). For a more complete treatment of randomized algorithms, see Motwani and Raghavan (1995). PTMs were first formally defined and studied in Gill (1977). The complexity classes PP, BPP, RP, and ZPP and their basic properties were all defined there. Theorem 8.22 was first observed in Rabin (1976). The fact that RP has polynomial-size circuits was first proved by Adleman (1978). Theorem 8.27 is based on the same idea and was first pointed out by Bennett and Gill (1981). Theorem 8.30 is from Ko (1982) and Zachos (1983). The result that BPP is contained in the polynomial-time hierarchy was first proved by Sipser and Gacs (see Sipser (1983b)). A simpler version was later published in Lautemann (1983). Our proof using the Swapping Lemma is from Zachos and Heller (1986). Zachos (1986) contains a survey on the relations between probabilistic complexity classes. The algorithm for the string matching problem in Exercise 8.2 is due to Karp and Rabin (1987). Beigel, Reingold, and Spielman (1991) showed that PP is closed under intersection (Exercise 8.7). Exercise 8.8 is from Beigel, Hemachandra, and Wechsung (1991). The space-bounded probabilistic classes have been studied in Gill (1977), Simon et al. (1980), Simon (1981), Ruzzo et al. (1984), and Saks and Zhou (1995). Exercise 8.10 is from these papers. Yao (1982) and Nisan and Wigderson (1994) studied the existence of pseudorandom generators and the collapsing of complexity classes. Exercise 8.14 is from these papers. The notion almost-P was first defined by Bennett and Gill (1981). Exercise 8.16 is from there. This notion can be generalized to almost-Lemma 8.31
Remark
Proof
Theorem 8.32
Proof
to 
, we obtain immediately the following relation.Corollary 8.33
(b) of Theorem 8.32, the proof did not use the fact that Q is polynomial-time computable. Thus, it actually shows that if a set A satisfies (8.3) with respect to any predicate Q and any polynomial function q, then it can be characterized as in (8.1), with the predicate R polynomial-time computable relative to Q. This observation will be useful in Chapter 10, when we study other complexity classes defined by alternating 
and 
quantifiers. We state this more general result as the generalized BPP theorem.Theorem 8.34
8.8 Relativized Probabilistic Complexity Classes
together with a random-bit generator ϕ. For any fixed 
, the computation of 
is just the same as an oracle DTM. The concepts of accepting probability, error probability, and time complexity of M can be defined exactly as those of an ordinary PTM. Let A be an arbitrary set. The class PPA is defined to be the class of sets accepted by polynomial-time oracle PTMs M, relative to the oracle A. The classBPPA is the class of all sets accepted by polynomial-time oracle PTMs M relative to A such that the error probability of 
is bounded by some constant 
.4 The class RPA is defined, in a similar way, to be the class of sets accepted by polynomial-time oracle PTMs M relative to A such that the error probability of 
is bounded by some constant 
and the error probability of 
for 
is 0. It is easy to verify that all the properties of BPP and RP proved in the previous sections also hold with respect to BPPA and RPA, respectively, for all sets A.
satisfying properties (1) and (2) of Section 8.1 is enumerable.
. That is, given a random oracle A, a deterministic machine is able to use oracle A to simulate the random bit generator of a randomized machine. For the notion of random oracles, refer to Section 4.7.Theorem 8.35
Proof
Corollary 8.36
Theorem 8.37
Proof
Corollary 8.38
Proof
Exercises
.
, whether w occurs in s as a substring. Assume that 
, 
and for each 
, let sj be the jth bit of s. The brute-force deterministic algorithm B compares w with each substring 
, character by character, and needs deterministic time 
in the worst case. For each string 
, let iw be the integer such that w is its binary expansion (with leading zeros allowed). For each prime p > 1, let 
. Now consider the following two randomized algorithms R1 and R2:Algorithm R1
.
to 
do
then if 
then accept and halt;
to 
doBegin
End;Reject.
then if 
then accept and halt
, but 
for some j) is bounded by 
.
can be computed from 
in time 
as follows: 
. Also, to generate a random prime p, we can use the randomized algorithm for PRIME of Example 8.4 to test whether a random integer p is a prime.)
halts in 
moves and 
halts in 
moves with 
, then neither 
nor 
.
and then M enters the zero state or the one state according to the bit b. In other words, machine M requests a random bit only when it needs it.
with 
for all j, 
. Show that for any ε > 0, there exists a PTM M1 with the standard random-bit generator ϕ such that 
, and for all x of length n, 
.
be the number of accepting paths of M(x) subtracting the number of rejecting paths of M(x). For any two polynomial-time PTMs M1 and M2, show that there exist polynomial-time PTMs M3 and M4 such that for all x,
, and
.
if and only if 
and 
. Such a function 
cannot be realized as a polynomial on 
and 
. However, if we treat 
and 
as continuous functions, then the function 
can be approximated by a rational function on 
and 
. (This is well known in numerical analysis.) Now apply Exercise 8.6 to show that such a rational function can be defined as fM for some polynomial-time PTM M.]
queries, where c is a constant. Let 
denote the class of sets computable by polynomial-time 
-query oracle machines with an oracle in NP. Prove that 
.
with PP. That is, prove that 
or find an oracle A such that 
.
be the class of sets accepted by PTMs with space bound s(n).
.
.
is closed under complementation.
be a predicate that holds only if 
and 
for some polynomials p and q. Assume that for some x of length n, it holds that 
. Then, for some polynomial r, it holds that 
, where 
with each wi of length q(n), and 
means “for the majority of 
.”
denote the union of all classes BPPA for all 
. Prove that 
. Is it true that 
? Why or why not?
be the class of sets A for which there exist a polynomial-time predicate R and a polynomial p such that for all x,
be the class of sets A for which there exist a polynomial-time predicate R and a polynomial p such that for all x,
.
and 
.
, then the polynomial-time hierarchy collapses to BPP.
, and an nc-pseudorandom generator f is strongly unpredictable if the range of f is strongly unpredictable as defined in Definition 4.12.
for every ε > 0.
of circuits approximates a set 
if for every polynomial function p, 
for almost all n ≥ 1. Prove that if there exists a set 
that is not approximable by any polynomial-size circuits 
, then for every c > 0, there exists a strongly unpredictable nc-pseudorandom generator f and, hence, 
for every ε > 0.
. Prove that 
.
. Prove that 
.
. [Hint: cf. Theorem 4.21.]
.
.Historical Notes
for any complexity class 
. See, for instance, Nisan and Wigderson (1994). The relativized separation of BPP and RP from P was first studied by Rackoff (1982). Exercises 8.17(b) and 8.19 are from there. Rackoff (1982) also gave a constructive proof for the result that 
. Our proofs are based on the random oracle technique developed in Bennett and Gill (1981). Ko (1990) contains more results on relativized probabilistic complexity classes.