Bounded query machines: on NP( ) and NPQUERY( )

DOI10.1016/0304-3975(81)90062-1zbMath0473.68040OpenAlexW2055421995MaRDI QIDQ1158752

Ronald V. Book, Celia Wrathall

Publication date: 1981

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

Full work available at URL: https://doi.org/10.1016/0304-3975(81)90062-1

zbMATH Keywords

PSPACEunion of the polynomial-time hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

On bounded query machines ⋮ Positive relativizations for log space computability ⋮ Positive relativizations of the \(P=?\) NP problem ⋮ Characterizations of reduction classes modulo oracle conditions ⋮ Bounded query machines: on NP and PSPACE ⋮ Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A? ⋮ Polynomial-time compression ⋮ On relativizing auxiliary pushdown machines ⋮ Consistency in nondeterministic storage ⋮ Qualitative relativizations of complexity classes

Cites Work

• Bounded query machines: on NP and PSPACE
• On counting problems and the polynomial-time hierarchy
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• On languages accepted by space-bounded oracle machines
• A second step toward the polynomial hierarchy
• The lattices of prefixes and overlaps of traces
• A generator of context-sensitive languages
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Rudimentary Predicates and Relative Computation
• Properties of deterministic top down grammars
• Studies in abstract families of languages