On bounded query machines

DOI10.1016/0304-3975(85)90168-9zbMath0608.68038OpenAlexW1992440350MaRDI QIDQ1085975

Ronald V. Book, José L. Balcázar, Uwe Schoening

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90168-9

zbMATH Keywords

polynomial-time hierarchyrelativizationcomplexity classessparse oracles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Relativized alternation and space-bounded computation ⋮ Sets with small generalized Kolmogorov complexity ⋮ Complexity of the \(r\)-query tautologies in the presence of a generic oracle ⋮ On the complexity of counting in the polynomial hierarchy

Cites Work

• Bounded query machines: on NP and PSPACE
• Bounded query machines: on NP( ) and NPQUERY( )
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Relationships between nondeterministic and deterministic tape complexities
• The polynomial-time hierarchy and sparse oracles
• On the random oracle hypothesis
• Positive Relativizations of Complexity Classes
• On Restricting the Size of Oracles Compared with Restricting Access to Oracles
• Quantitative Relativizations of Complexity Classes