Bounded query machines: on NP and PSPACE
From MaRDI portal
Publication:1158751
DOI10.1016/0304-3975(81)90061-XzbMath0473.68039OpenAlexW1973386461MaRDI QIDQ1158751
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
languages accepted by deterministic polynomial space-bounded oracle machineslanguages accepted by nondeterministic polynomial space-bounded oracle machines
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
