Consider the class of all subsets of and define subclasses and . One of the approaches to study the relativized question is to compare the two subclasses and to see which one is larger. In this subsection, we give a brief introduction to this study based on the probability theory on the space .
To define the notion of probability on the space , it is most convenient to identify each element with its characteristic sequence (i.e., the kth bit of αX is 1 if and only if the kth string of , under the lexicographic ordering, is in X) and treat as the set of all infinite binary sequences or, equivalently, the Cartesian product . We can define a topology on by letting the set {0,1} have the discrete topology and forming the product topology on . This is the well-known Cantor space. We now define the uniform probability measure μ on as the product measure of the simple equiprobable measure on {0,1}, that is, . In other words, for any integer n ≥ 1, the nth bit of a random sequence has the equal probability to be 0 or 1. If we identify each real number in with its binary expansion, then this measure μ is the Lebesgue measure on .5
For any , let Γu be the set of all infinite binary sequences that begin with u, that is, . Each set Γu is called a cylinder. All cylinders Γu, , together form a basis of open neighborhoods of the space (under the product topology). It is clear that for all . The smallest σ-field containing all Γu, for all , is called the Borel field.6 Each set in the Borel field, called a Borel set, is measurable.
The question of which of the two subclasses and is larger can be formulated, in this setting, as to whether is greater than . In the following, we show that .
An important idea behind the proof is Kolmogorov's zero–one law of tail events, which implies that if an oracle class is insensitive to a finite number of bit changes, then its probability is either zero or one. This property holds for the classes and as well as most other interesting oracle classes.
Theorem 4.18
Proof
Now we prove the main result of this section.
Theorem 4.19
Proof
The above type of random oracle separation results holds for many complexity classes. see Exercise 4.15 and Section 9.5.
4.8 Structure of Relativized NP
Although the meaning of relativized collapsing and relativized separation results is still not clear, many relativized results have been proven. These results show a variety of possible relations between the well-known complexity classes. In this section, we demonstrate some of these relativized results on complexity classes within NP to show what the possible relations are between P, NP, , and UP. The relativized results on the classes beyond the class NP, that is, those on NP, PH, and PSPACE, will be discussed in later chapters.
The proofs of the following results are all done by the stage-construction diagonalization. The proofs sometimes need to satisfy simultaneously two or more potentially conflicting requirements that make the proofs more involved.
Theorem 4.20
Proof
Similar relations between relativized UP and the relativized P and NP can be proved using the same proof techniques. We leave them as exercises.
Theorem 4.21
Exercises
4.1 Let k ≥ 1. An NTM M is k-ambiguous if for any input x, there are at most k distinct accepting computations in M(x). Let k-UP denote the class of sets acceptable by polynomial-time k-ambiguous NTMs. Prove that if and only if -UP.
4.2 Let DGISO be the problem of determining whether two directed graphs are isomorphic. Show that DGISO and GISO are equivalent under the -reducibility.
4.3 Prove Theorem 4.4.
4.4 Recall the notion of strong NP reducibility defined in Exercise 3.1. Prove that if , then there is a set that is not -complete for NP.
4.5 a. Prove Proposition 4.10(b).
For any complexity class , let denote the class . Prove that there exists a one-way function such that restricted to is not polynomial-time computable if and only if .
Prove that there exists a one-way function such that and that restricted to is not polynomial-time computable if and only if .
4.6 In electronic data communication, a digital signature sent by a party X to a party Y is a message M that has the following properties: (i) Y must be able to verify that M is indeed sent by X; (ii) It is not possible for anyone except X, including Y, to forge the message M; (iii) X cannot deny sending the message M. Describe how to implement digital signatures in a public-key cryptosystem (allowing a negligible error).
4.7 Intuitively, a pseudorandom generator is a function that takes a random seed s of length n and outputs a string x of length l(n), where such that no feasible algorithm can predict the last bit of x from the first bits of x. Formally, we say that a function is a pseudorandom generator if
for all inputs x of length n, ; and
for any polynomial-time computable function , and any polynomial function p,
for almost all n > 0, where and .
A commonly used function to generate pseudorandom numbers is the linear congruence generator: Let m be a fixed integer and a,b be two integers less than m. Let , where and for . Prove that the function is not a pseudorandom generator in the above sense if . In other words, find a polynomial-time algorithm g that, on given , can find xk if and if .
4.8 We continue the last exercise. Let n be a positive integer and . Define if i ≥ 0, and let xn,i be the square root of if i < 0. Let be the parity of xn,i, that is, it is 1 if xn,i is odd and is 0 if xn,i is even. The quadratic residue generator is the function . Prove that QRG is a pseudorandom generator if for some fixed polynomial p, assuming that the sets QRn are strongly unpredictable in the sense of Section 4.2. That is, prove that if QRn are strongly unpredictable, then there exists an infinite set N of integers such that for any polynomial-time computable function and any polynomial functions p and q,
for almost all .
4.9 In this exercise, we study the application of one-way functions to the problem of finding a random bit to be shared by two parties. Suppose two parties X and Y need to have an unbiased random bit to be shared by both parties. One way to do it is to let each of X and Y pick a random bit bX and bY, respectively, write them down on a piece of paper, and then let them exchange the bits bX and bY and use as the random bit, where is the exclusive-or operation. As X and Y must commit their own bit before seeing the other party's bit, neither of the parties can create a biased bit as long as the other bit is unpredictable. Assume, however, that the two parties are in two remote locations and cannot exchange their random bits bX and bY both efficiently and reliably. Then, we need to use one-way functions to implement this idea. In each of the following communication environments, design a protocol to implement the above idea to find the shared random bit efficiently and reliably (assuming the existence of strong one-way functions).
X and Y communicate in a computer network with the software capable of efficiently generating large primes and performing multiplications of large integers.
X and Y communicate through a telephone line. They have two identical copies of a 1000-page telephone directory. (Note that this scheme should work even if . Can this scheme be implemented in a computer network?)
4.10 For each set A, let denote the class of sets B for which there exist a polynomial-space oracle DTM M and a polynomial function p such that for every x, if and only if MA accepts x and the total number of queries made by M in the computation tree of is bounded by . For any two sets , let .
Prove that for each set A, .
Prove that if and only if .
4.11 Recall the definition of tally and sparse sets in Exercise 1.30. Also recall the relativized polynomial-time hierarchy defined in Exercise 3.1. In this exercise, we study the power of tally and sparse oracles in relativization.
Prove that if and only if for all tally sets T, .
Prove that for k ≥ 2, if and only if for all sparse sets S, .
Prove that if and only if for all sparse sets S, .
4.12 Assume that . Prove that for any polynomial-time oracle NTM M, there exists a polynomial-time oracle DTM M1 such that for any input , outputs an accepting computation of , and for any input , rejects x.
4.13 Use the relativized separation results of Section 4.5 to show that the relation is not transitive.
4.14 a. In the following, we let w be a fixed finite binary string in and β be a fixed infinite binary sequence in . For any infinite binary sequence , we write to denote the kth bit of α and write αk to denote the string of the first k bits of α. We say an infinite binary sequence is recursive if the set X with is recursive. For each set Λi, , of infinite binary sequences defined below, verify that it satisfies the assumption of the zero–one law and, hence, is either 0 or 1:
occurs in α infinitely often}.
occurs in α for all .
is recursive}.
the series converges}.
For each , decide whether is equal to 0 or 1.
4.15 Prove that with probability one, (a) and (b) .
4.16 a. Prove Theorem 4.20(a).
Prove that there exists an oracle A relative to which .
4.17 Prove Theorem 4.21
Historical Notes
The existence of problems in that are not NP-complete was first suggested by Karp (1972), who listed the problems primality testing, GISO, and linear programming as candidates. (Linear programming was later shown to be in P; see Khachiyan (1979) and Karmarkar (1984). Primality testing was shown to be in P by Agrawal et al. (2004).) Theorem 4.3 is from Ladner (1975a). Schöning (1982) discussed the technique of delayed diagonalization. The complexity of problem QR has been widely studied; see, for instance, Kranakis (1986), Loxton (1990), and Bach and Shallit (1996) for more references. The complexity of the problem GISO will be further studied in Chapter 10. The class UP was defined by Valiant (1976). The relation between the class UP and one-way functions (Proposition 4.10) was first proved by Ko (1985a) and Grollman and Selman (1988). The notion of public-key cryptography was introduced by Diffie and Hellman (1976). The RSA cryptosystem was designed by Rivest et al. (1978). Rabin (1979) relates the security of the RSA cryptosystem and the complexity of integer factoring. The relativization results on P, NP, and coNP (Theorems 4.14 and 4.20) were first presented by Baker et al. (1975). The independence result of Theorem 4.15 is from Hartmanis and Hopcroft (1976), which includes some other independence results in computer science. The positive relativization result of Theorem 4.17 is from Book et al. (1984). Book et al. (1985) contains results on different types of positive relativization. Random oracles were first studied by Bennett and Gill (1981). Theorem 4.19 is from there. For more results on random oracles, see Chapters 8 and 9 and the survey paper by Vollmer and Wagner (1997). Relativization results on the relation between UP and NP (Theorem 4.21) were proved in Rackoff (1982).
Digital signatures and pseudorandom generators are important topics in cryptography; see any cryptography textbook for more references. For the linear congruence generator, see Plumstead (1982) and Frieze et al. (1984). For the quadratic residue generator, see Blum et al. (1986). In general, pseudorandom generators exist if strong one-way functions exist. See Håstad et al. (1999) for the detailed discussion. Exercise 4.11 is from Long and Selman (1986). The relativized separation of the second level of PH (Exercise 4.16(b)) was first proved by Heller (1984). The relativized separation of the higher levels of PH will be studied in Chapter 9.
of all subsets of 
and define subclasses 
and 
. One of the approaches to study the relativized 
question is to compare the two subclasses 
and 
to see which one is larger. In this subsection, we give a brief introduction to this study based on the probability theory on the space 
.
, it is most convenient to identify each element 
with its characteristic sequence 
(i.e., the kth bit of αX is 1 if and only if the kth string of 
, under the lexicographic ordering, is in X) and treat 
as the set of all infinite binary sequences or, equivalently, the Cartesian product 
. We can define a topology on 
by letting the set {0,1} have the discrete topology and forming the product topology on 
. This is the well-known Cantor space. We now define the uniform probability measure μ on 
as the product measure of the simple equiprobable measure on {0,1}, that is, 
. In other words, for any integer n ≥ 1, the nth bit of a random sequence 
has the equal probability to be 0 or 1. If we identify each real number in 
with its binary expansion, then this measure μ is the Lebesgue measure on 
.5
, let Γu be the set of all infinite binary sequences that begin with u, that is, 
. Each set Γu is called a cylinder. All cylinders Γu, 
, together form a basis of open neighborhoods of the space 
(under the product topology). It is clear that 
for all 
. The smallest σ-field containing all Γu, for all 
, is called the Borel field.6 Each set in the Borel field, called a Borel set, is measurable.
and 
is larger can be formulated, in this setting, as to whether 
is greater than 
. In the following, we show that 
.
and 
as well as most other interesting oracle classes.
, and UP. The relativized results on the classes beyond the class NP, that is, those on NP, PH, and PSPACE, will be discussed in later chapters.
if and only if 
-UP.
-reducibility.
defined in Exercise 3.1. Prove that if 
, then there is a set 
that is not 
-complete for NP.
, let 
denote the class 
. Prove that there exists a one-way function 
such that 
restricted to 
is not polynomial-time computable if and only if 
.
such that 
and that 
restricted to 
is not polynomial-time computable if and only if 
.
that takes a random seed s of length n and outputs a string x of length l(n), where 
such that no feasible algorithm can predict the last bit of x from the first 
bits of x. Formally, we say that a function 
is a pseudorandom generator if
; and
, and any polynomial function p,
and 
.
, where 
and 
for 
. Prove that the function 
is not a pseudorandom generator in the above sense if 
. In other words, find a polynomial-time algorithm g that, on given 
, can find xk if 
and if 
.
. Define 
if i ≥ 0, and let xn,i be the square root of 
if i < 0. Let 
be the parity of xn,i, that is, it is 1 if xn,i is odd and is 0 if xn,i is even. The quadratic residue generator is the function 
. Prove that QRG is a pseudorandom generator if 
for some fixed polynomial p, assuming that the sets QRn are strongly unpredictable in the sense of Section 4.2. That is, prove that if QRn are strongly unpredictable, then there exists an infinite set N of integers such that for any polynomial-time computable function 
and any polynomial functions p and q,
.
as the random bit, where 
is the exclusive-or operation. As X and Y must commit their own bit before seeing the other party's bit, neither of the parties can create a biased bit 
as long as the other bit is unpredictable. Assume, however, that the two parties are in two remote locations and cannot exchange their random bits bX and bY both efficiently and reliably. Then, we need to use one-way functions to implement this idea. In each of the following communication environments, design a protocol to implement the above idea to find the shared random bit efficiently and reliably (assuming the existence of strong one-way functions).
. Can this scheme be implemented in a computer network?)
denote the class of sets B for which there exist a polynomial-space oracle DTM M and a polynomial function p such that for every x, 
if and only if MA accepts x and the total number of queries made by M in the computation tree of 
is bounded by 
. For any two sets 
, let 
.
.
if and only if 
.
if and only if for all tally sets T, 
.
if and only if for all sparse sets S, 
.
if and only if for all sparse sets S, 
.
. Prove that for any polynomial-time oracle NTM M, there exists a polynomial-time oracle DTM M1 such that for any input 
, 
outputs an accepting computation of 
, and for any input 
, 
rejects x.
is not transitive.
and β be a fixed infinite binary sequence in 
. For any infinite binary sequence 
, we write 
to denote the kth bit of α and write αk to denote the string of the first k bits of α. We say an infinite binary sequence 
is recursive if the set X with 
is recursive. For each set Λi, 
, of infinite binary sequences defined below, verify that it satisfies the assumption of the zero–one law and, hence, 
is either 0 or 1:
occurs in α infinitely often}.
occurs in α for all 
.
is recursive}.
the series 
converges}.
, decide whether 
is equal to 0 or 1.
and (b) 
.
.
that are not NP-complete was first suggested by Karp (1972), who listed the problems primality testing, GISO, and linear programming as candidates. (Linear programming was later shown to be in P; see Khachiyan (1979) and Karmarkar (1984). Primality testing was shown to be in P by Agrawal et al. (2004).) Theorem 4.3 is from Ladner (1975a). Schöning (1982) discussed the technique of delayed diagonalization. The complexity of problem QR has been widely studied; see, for instance, Kranakis (1986), Loxton (1990), and Bach and Shallit (1996) for more references. The complexity of the problem GISO will be further studied in Chapter 10. The class UP was defined by Valiant (1976). The relation between the class UP and one-way functions (Proposition 4.10) was first proved by Ko (1985a) and Grollman and Selman (1988). The notion of public-key cryptography was introduced by Diffie and Hellman (1976). The RSA cryptosystem was designed by Rivest et al. (1978). Rabin (1979) relates the security of the RSA cryptosystem and the complexity of integer factoring. The relativization results on P, NP, and coNP (Theorems 4.14 and 4.20) were first presented by Baker et al. (1975). The independence result of Theorem 4.15 is from Hartmanis and Hopcroft (1976), which includes some other independence results in computer science. The positive relativization result of Theorem 4.17 is from Book et al. (1984). Book et al. (1985) contains results on different types of positive relativization. Random oracles were first studied by Bennett and Gill (1981). Theorem 4.19 is from there. For more results on random oracles, see Chapters 8 and 9 and the survey paper by Vollmer and Wagner (1997). Relativization results on the relation between UP and NP (Theorem 4.21) were proved in Rackoff (1982).