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

DOI10.1016/0304-3975(81)90062-1MaRDI QIDQ1158752zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

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

Cited in

(10)

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

This page was built for publication: Bounded query machines: on NP( ) and NPQUERY( )

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1158752)