Cites work
- A hierarchy for nondeterministic time complexity
- A second step toward the polynomial hierarchy
- Bounded query machines: on NP( ) and NPQUERY( )
- On Languages Accepted in Polynomial Time
- On languages accepted by space-bounded oracle machines
- On languages specified by relative acceptance
- Polynomial Space and Transitive Closure
- Relationships between nondeterministic and deterministic tape complexities
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Rudimentary Predicates and Relative Computation
- Separating Nondeterministic Time Complexity Classes
- The lattices of prefixes and overlaps of traces
- Time- and tape-bounded Turing acceptors and AFLs
Cited in
(12)- Positive relativizations of the \(P=?\) NP problem
- Query complexity, or why is it difficult to separate NP^ A 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)
