NONDETERMINISTIC COMPUTATIONS IN SUBLOGARITHMIC SPACE AND SPACE CONSTRUCTIBILITY

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) --> infinity s(n)/log (n) = 0. Consequently, space constructibility of monotone functions cannot be used to separate nondeterministic space from deterministic space, even for a very low-level complexity range, since functions like log log (n) and square-root log (n) are not space constructible by nondeterministic Turing machines. This result is obtained by the extension of the n --> 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.