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.