Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\)
From MaRDI portal
Publication:1094139
DOI10.1016/0020-0190(87)90087-1zbMath0629.68050OpenAlexW2009546147MaRDI QIDQ1094139
Bernd Kirsig, Klaus-Joern Lange
Publication date: 1987
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(87)90087-1
Related Items (5)
Positive relativizations for log space computability ⋮ Decompositions of nondeterministic reductions ⋮ New developments in structural complexity theory ⋮ A survey of space complexity ⋮ Bridging across the \(\log(n)\) space frontier
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Space-bounded hierarchies and probabilistic computations
- Relationships between nondeterministic and deterministic tape complexities
- A note on relativized log space
- Quantitative Relativizations of Complexity Classes
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativization of questions about log space computability
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
This page was built for publication: Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\)
