A note on relativized log space

DOI10.1007/BF01744581zbMath0524.68031MaRDI QIDQ3036705

Walter J. Savitch

Publication date: 1983

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

zbMATH Keywords

computationsrecursive oraclelog space

Mathematics Subject Classification ID

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

Related Items (5)

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

Cites Work

• Unnamed Item
• Log space machines with multiple oracle tapes
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Relativization of questions about log space computability

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