A note on relativized log space

DOI10.1007/BF01744581MaRDI QIDQ3036705zbMATH OpenFDO

Authors 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

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Log space machines with multiple oracle tapes
• Relativization of questions about log space computability
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

Cited in

(5)

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

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)