On bounded query machines
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)].
- Bounded query machines: on NP and PSPACE
- Bounded query machines: on NP( ) and NPQUERY( )
- Complete sets and the polynomial-time hierarchy
- On Restricting the Size of Oracles Compared with Restricting Access to Oracles
- On the random oracle hypothesis
- Positive Relativizations of Complexity Classes
- Quantitative Relativizations of Complexity Classes
- Relationships between nondeterministic and deterministic tape complexities
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- The polynomial-time hierarchy
- The polynomial-time hierarchy and sparse oracles
- Relativized alternation and space-bounded computation
- Bounded query classes and the difference hierarchy
- Some connections between bounded query classes and non-uniform complexity.
- Sets with small generalized Kolmogorov complexity
- Complexity of the \(r\)-query tautologies in the presence of a generic oracle
- Database query processing using finite cursor machines
- scientific article; zbMATH DE number 3990861 (Why is no real title available?)
- On Bounded Database Schemes and Bounded Horn-Clause Programs
- On the Structure of Bounded Queries to Arbitrary NP Sets
- On Bounded Queries and Approximation
- Bounded queries to arbitrary sets
- scientific article; zbMATH DE number 1405575 (Why is no real title available?)
- scientific article; zbMATH DE number 1424049 (Why is no real title available?)
- A finite model-theoretical proof of a property of bounded query classes within PH
- On adaptive versus nonadaptive bounded query machines
- On the complexity of counting in the polynomial hierarchy
This page was built for publication: On bounded query machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085975)
