Bridging across the \(\log(n)\) space frontier (Q1271619)

This paper establishes the importance of even the lowest possible level of space bounded computations. We show that DLOG does not coincide with NLOG if and only if there exists a tally set in \(\text{NSPACE}(\log\log n)\setminus\text{DSPACE}(\log \log n)\). This result stands in perfect analogy to the related results concerning linear space or exponential time. Moreover, the above problem is equivalent to the existence of a function \(s(n)\), with arbitrarily slow or rapid growth rate, that is nondeterministically fully space constructible but cannot be constructed deterministically. We also present a ``hardest'' fully space constructible \(s(n)\in O(\log\log n)\), a functional counterpart of log-space complete languages. These nonrelativized results are obtained by the use of oracle machines consuming much larger amount of space, in range between \(n\) and \(2^{d\cdot n}\).