Bounded query machines: on NP and PSPACE
From MaRDI portal
Publication:1158751
DOI10.1016/0304-3975(81)90061-XzbMATH Open0473.68039OpenAlexW1973386461MaRDI QIDQ1158751FDOQ1158751
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
Cites Work
- Relationships between nondeterministic and deterministic tape complexities
- Separating Nondeterministic Time Complexity Classes
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- A hierarchy for nondeterministic time complexity
- Rudimentary Predicates and Relative Computation
- On Languages Accepted in Polynomial Time
- A second step toward the polynomial hierarchy
- Bounded query machines: on NP( ) and NPQUERY( )
- Polynomial Space and Transitive Closure
- On languages specified by relative acceptance
- On languages accepted by space-bounded oracle machines
- Time- and tape-bounded Turing acceptors and AFLs
- The lattices of prefixes and overlaps of traces
Cited In (12)
- 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?
- Complexity of the \(r\)-query tautologies in the presence of a generic oracle
- Polynomial-time compression
- Qualitative relativizations of complexity classes
- On relativizing auxiliary pushdown machines
- The strong exponential hierarchy collapses
- Restricted relativizations of probabilistic polynomial time
- Bounded query machines: on NP( ) and NPQUERY( )
- 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 PSPACE
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1158751)
