Bounded query machines: on NP and PSPACE

DOI10.1016/0304-3975(81)90061-XzbMath0473.68039OpenAlexW1973386461MaRDI QIDQ1158751

Ronald V. Book

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)90061-x

zbMATH Keywords

languages accepted by deterministic polynomial space-bounded oracle machineslanguages accepted by nondeterministic polynomial space-bounded oracle machines

Mathematics Subject Classification ID

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

Related Items

On bounded query machines, Positive relativizations of the \(P=?\) NP problem, Characterizations of reduction classes modulo oracle conditions, Bounded query machines: on NP( ) and NPQUERY( ), Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?, Restricted relativizations of probabilistic polynomial time, Polynomial-time compression, On relativizing auxiliary pushdown machines, The strong exponential hierarchy collapses, Consistency in nondeterministic storage, Qualitative relativizations of complexity classes, Complexity of the \(r\)-query tautologies in the presence of a generic oracle

Cites Work

• Bounded query machines: on NP( ) and NPQUERY( )
• On languages specified by relative acceptance
• On languages accepted by space-bounded oracle machines
• A second step toward the polynomial hierarchy
• A hierarchy for nondeterministic time complexity
• The lattices of prefixes and overlaps of traces
• Relationships between nondeterministic and deterministic tape complexities
• Time- and tape-bounded Turing acceptors and AFLs
• Polynomial Space and Transitive Closure
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Separating Nondeterministic Time Complexity Classes
• Rudimentary Predicates and Relative Computation
• On Languages Accepted in Polynomial Time