A note on relativized log space

DOI10.1007/BF01744581zbMATH Open0524.68031MaRDI QIDQ3036705FDOQ3036705

Walter Savitch

Publication date: 1983

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

computationsrecursive oraclelog space

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Title not available (Why is that?)
• Relativization of questions about log space computability
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Log space machines with multiple oracle tapes

Cited In (5)

• Decompositions of nondeterministic reductions
• Relativized alternation and space-bounded computation
• Positive relativizations for log space computability
• Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\)
• A survey of space complexity

This page was built for publication: A note on relativized log space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3036705)