Nondeterministic computations in sublogarithmic space and space constructibility. (English) Zbl 0762.68022

Call a function \(s(n)\) nondeterministically fully space constructible if it can be computed by a nondeterministic Turing machine having a read- only input tape and a read-write scratch tape in such a way that for each \(n\) the space used on the scratch tape while computing \(s(n)\) is bounded by \(s(n)\). This bound holds for all computation paths and is attained for at least one.
The main result of the paper is that there exists no monotone increasing fully space constructible function \(s(n)\) such that \(\sup_{n\to \infty}{s(n)\over\log n}=0\).
The proof uses a careful analysis of computations of such Turing machines using, in particular, the notion of a “\(U\)-turn” - a computation that takes the machine from one configuration to another such that the two configurations differ only with regard to the position of the head on the input tape.
Consequences of the result are the facts that \(\log\log(n)\) and \(\sqrt{\log(n)}\) are not nondeterministically fully space constructible and that various languages are not recognizable in sublogarithmic space.
The paper concludes by summarizing a number of containment relations between space complexity classes which are implied by the main result.
Reviewer: W.Nico (Hayward)


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI