Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
Viliam Geffert · SIAM Journal on Computing · 1991
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.