This research paper mainly discusses relativations of the following famous open problems:
( 1 ) P = ? NP
( 2 ) NP = ? co-NP
( 3 ) Does the polynomial-time hierarchy collapse?
After the result of Baker, Gill, and Solovay [1], it was obvious that the answers to the relativized questions depend heavily on the oracle set, but it was not clear what such answers mean for the unrelativized original problems. It is natural to expect that the answers to (1)–(3) relativized to an oracle set A depend on the structure and/or density of A . A is tally iff A ⊆ { 1 }*, and A is sparse iff the number of elements of A of length ≤ n is bounded by a polynomial p ( n ). Regarding (1) and (2), this paper shows that if the answer is positive, then it is so for the relativized questions with respect to every tally set A, and conversely. But the classes in (1), as well as in (2), can be separated by relativizing to a sparse oracle set which is not tally, as the construction by Baker et al. shows. Now what about the analogue question at higher levels of the polynomial hierarchy: for k ≥ 2 , i.e., question ( 3 )?
If the answer to (3) is positive, then it is so for the relativized questions with respect to every sparse set A, and conversely. But, more recently, Yao [2] showed that the polynomial hierarchy may be separated when relativized to some other oracle set. About the converse, it is enough to require a positive answer to (3) relativized to any oracle set. This is proved in the paper by Balcázar et al. [3] which is published simultaneously. This means that the answer of (3) is not affected by relativizing it with respect to any sparse oracle set. While the proof technique in [3] is more abstract and machine independent and may be more powerful (“quantifier-coding” technique), the machine theoretic argument by Long and Selman is interesting in its own right. Some readers will certainly prefer to read this paper first.
