On bounded query machines
From MaRDI portal
Recommendations
Cites work
- 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
Cited in
(14)- Sets with small generalized Kolmogorov complexity
- Complexity of the \(r\)-query tautologies in the presence of a generic oracle
- scientific article; zbMATH DE number 1405575 (Why is no real title available?)
- On the Structure of Bounded Queries to Arbitrary NP Sets
- scientific article; zbMATH DE number 3990861 (Why is no real title available?)
- scientific article; zbMATH DE number 1424049 (Why is no real title available?)
- On the complexity of counting in the polynomial hierarchy
- Bounded query classes and the difference hierarchy
- Database query processing using finite cursor machines
- On Bounded Queries and Approximation
- Some connections between bounded query classes and non-uniform complexity.
- A finite model-theoretical proof of a property of bounded query classes within PH
- On Bounded Database Schemes and Bounded Horn-Clause Programs
- Relativized alternation and space-bounded computation
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)
