The justification for this paper is that it presents proofs of four existing results on complexity classes in short forms that are technically more accessible than the original proofs (whose sources are cited), and therefore more likely to ensure their understanding in future work.
The class PQUERY is defined as follows: For every set A, let PQUERY ( A ) be the class of languages L ∈ PSPACE ( A ) such that there exists a deterministic polynomial space-bounded oracle machine M, where M recognizes L relative to A, and there is a polynomial p such that, for all x, there are at most p ( | x | )oracle queries in every computation of M on x. NPQUERY is defined in the same way, where “deterministic” is replaced by “non-deterministic.”
The theorems involve characterizations of P and NP classes and the union of the Polynomial-time Hierarchy (PH). The two results that are immediately understandable in terms of the material above are as follows:
(1) P = PSPACE iff P ( A ) = PQUERY ( A ) for every set A.
(2) NP = PSPACE iff NP ( A ) = NPQUERY ( A ) for every set A.
In addition, for a particular relativization of PSPACE denoted by PQH, the paper gives demonstrations of two possible conditions for PH = PSPACE: iff PH ( A ) = PQH ( A ) for every set A, and iff PH ( S ) = PQH ( S ) = PSPACE ( S ) for every sparse set S. Technically, the first two proofs hinge on a lemma which states that PQUERY ( A) = P ( C ⊕ A ) and NPQUERY ( A ) = NP ( C ⊕ A ), where C is any set that is ≤TP -complete for PSPACE. A similar kind of argument is used for the other results. The proofs meet the authors’ criteria for being short and not too esoteric.
