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.68050MaRDI 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
68Q25: Analysis of algorithms and problem complexity
Related Items
New developments in structural complexity theory, Decompositions of nondeterministic reductions, A survey of space complexity, Bridging across the \(\log(n)\) space frontier, Positive relativizations for log space computability
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item