Log space machines with multiple oracle tapes

DOI10.1016/0304-3975(78)90003-8MaRDI QIDQ1242686zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cites work

• A comparison of polynomial time reducibilities
• A second step toward the polynomial hierarchy
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3586493 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• On the Structure of Polynomial Time Reducibility
• Reducibility among combinatorial problems
• Relationships between nondeterministic and deterministic tape complexities
• Relativization of questions about log space computability
• Relativization of the Theory of Computational Complexity
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Tape bounds for time-bounded Turing machines
• The complexity of theorem-proving procedures

Cited in

(8)

• Relativized alternation and space-bounded computation
• Space-efficient informational redundancy
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
• A note on relativized log space
• On relativizing auxiliary pushdown machines
• Relativization of questions about log space computability
• Relativized logspace and generalized quantifiers over finite ordered structures
• Quantitative coding and complexity theory of \textit{continuous} data. I: Motivation, definition, consequences

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)