Positive relativizations for log space computability (Q2639638)

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.