Separation with the Ruzzo, Simon, and Tompa relativization implies Dspace(log n) ≠ Nspace(log n)
- 20 April 1987
- journal article
- Published by Elsevier in Information Processing Letters
- Vol. 25 (1) , 13-15
- https://doi.org/10.1016/0020-0190(87)90087-1
Abstract
No abstract availableThis publication has 7 references indexed in Scilit:
- Quantitative Relativizations of Complexity ClassesSIAM Journal on Computing, 1984
- Space-bounded hierarchies and probabilistic computationsJournal of Computer and System Sciences, 1984
- A note on relativized log spaceTheory of Computing Systems, 1983
- Relativization of questions about log space computabilityTheory of Computing Systems, 1976
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975
- Characterizations of Pushdown Machines in Terms of Time-Bounded ComputersJournal of the ACM, 1971
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970