Log space machines with multiple oracle tapes
From MaRDI portal
Publication:1242686
DOI10.1016/0304-3975(78)90003-8zbMATH Open0368.68058OpenAlexW1980326341MaRDI QIDQ1242686FDOQ1242686
Authors: Nancy Lynch 
Publication date: 1978
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(78)90003-8
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Turing machines and related notions (03D10)
Cites Work
- Reducibility among combinatorial problems
- Relationships between nondeterministic and deterministic tape complexities
- On the Structure of Polynomial Time Reducibility
- Relativization of questions about log space computability
- Title not available (Why is that?)
- The complexity of theorem-proving procedures
- Title not available (Why is that?)
- A comparison of polynomial time reducibilities
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- A second step toward the polynomial hierarchy
- Title not available (Why is that?)
- Tape bounds for time-bounded Turing machines
- Relativization of the Theory of Computational Complexity
Cited In (7)
- Relativized logspace and generalized quantifiers over finite ordered structures
- Relativized alternation and space-bounded computation
- On relativizing auxiliary pushdown machines
- A note on relativized log space
- Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
- Space-efficient informational redundancy
- Relativization of questions about log space computability
This page was built for publication: Log space machines with multiple oracle tapes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1242686)
