Nondeterministic Computations in Sublogarithmic Space and Space Constructibility

Abstract

The open problem of nondeterministic space constructibility for sublogarithmic functions is resolved. It is shown that there are no unbounded monotone increasing nondeterministically space constructible functions such that $\sup _{n \to \infty } s(n) / \log (n) = 0$. Consequently, space constructibility of monotone functionscannot be used to separate nondeterministic space from deterministic space, even for a very low-level complexity range, since functions like $\log \log (n)$ and ,$\sqrt {\log (n)} $ are not space constructible by nondeterministic Turing machines. This result is obtained by the extension of the $n \to n + n!$ method, described in [Hierarchies of memory limited computations, IEEE Conference Record on Switching Circuit Theory and Logical Design, 1965, pp. 179–190], to the nondeterministic case.