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

DOI10.1016/0304-3975(81)90062-1zbMATH Open0473.68040OpenAlexW2055421995MaRDI QIDQ1158752FDOQ1158752

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

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

Cited In (10)

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

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)