On bounded query machines (Q1085975): Difference between revisions

Simple proofs are given for each of the following results: (a) \(P=PSPACE\) if and only if, for every set A, \(P(A)=PQUERY(A)\) \textit{[A. L. Selman}, \textit{Xu Mei-Rui} and \textit{R. V. Book}, SIAM J. Comput. 12, 565-579 (1983; Zbl 0551.68043)]; (b) \(NP=PSPACE\) if and only if, for every set A, \(NP(A)=NPQUERY(S)\) [\textit{R. V. Book}, Theor. Comput. Sci. 15, 27-39 (1981; Zbl 0473.68039)]; (c) \(PH=PSPACE\) if and only if, for every set A, \(PH(A)=PQH(A)\) [\textit{R. V. Book} and \textit{C. Wrathall}, ibid. 15, 41-50 (1981; Zbl 0473.68040)]; (d) \(PH=PSPACE\) if and only if, for every sparse set S, \(PH(S)=PQH(S)=PSPACE(S)\) [the authors, ''The polynomial-time hierarchy and sparse oracles'', J. Assoc. Comput. Mach. (to appear); \textit{T. Long} and \textit{A. Selman}, ''Relativizing complexity classes with sparse oracles'', ibid. (to appear)].