Positive relativizations for log space computability

DOI10.1016/0304-3975(90)90168-HMaRDI QIDQ2639638zbMATH OpenOpenAlexFDO

Authors Seinosuke Toda

Publication date 1990

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(90)90168-h

zbMATH Keywords

log-space bounded Turing machinesoracle Turing machinespolynomial-time computabilitypositive relativizations

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

The open problem whether the inclusions DL \(\subseteq NL \subseteq P \subseteq NP\) are proper or not is considered (DL resp. NL denote the class of languages accepted by log-space bounded deterministic (nondeterministic) Turing machines). The author develops positive relativizations for these questions and gives characterisations of the form: DL \(= NL\) if and only if \(DL^ T = NL^ T\) for all tally sets T.; DL \(= P\) iff \(DL^ T = P^ T\) for all tally sets T, etc. Using oracle Turing machines deterministically queried \textit{W. L. Ruzzo, J. Simon} and \textit{M. Tompa} [J. Comput. Syst. Sci. 28, 216-230 (1984; Zbl 0573.68021)], characterisations of the form DL \(= NL\) if and only if \(DL^ A = NL^ ARST\) for all oracle A, are given.

Recommendations

• A positive relativization of polynomial time versus polylog space
• Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n) NSPACE( \,n)
• scientific article; zbMATH DE number 4045155
• Bridging across the (n) space frontier
• Positive Relativizations of Complexity Classes

Cites work

• A note on relativized log space
• A second step toward the polynomial hierarchy
• Alternation
• Bounded query machines: on NP( ) and NPQUERY( )
• On Restricting the Size of Oracles Compared with Restricting Access to Oracles
• Positive Relativizations of Complexity Classes
• Qualitative relativizations of complexity classes
• Quantitative Relativizations of Complexity Classes
• Relationships between nondeterministic and deterministic tape complexities
• Relativization of questions about log space computability
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• RelativizedNC
• Relativizing Time, Space, and Time-Space
• Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n) NSPACE( \,n)
• Space-bounded hierarchies and probabilistic computations

Cited in

(5)

• Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n) NSPACE( \,n)
• A positive relativization of polynomial time versus polylog space
• Supportive oracles for parameterized polynomial-time sub-linear-space computations in relation to L, NL, and P
• scientific article; zbMATH DE number 4045155 (Why is no real title available?)
• scientific article; zbMATH DE number 8798 (Why is no real title available?)

This page was built for publication: Positive relativizations for log space computability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2639638)