A Sharp Separation of Sublogarithmic Space Complexity Classes

Abstract

We present very sharp separation results for Turing machine sublogarithmic space complexity classes which are of the form: For any, arbitrarily slow growing, recursive nondecreasing and unbounded function s there is a k in N and an unary language L such that L in SPACE(s(n)+k) setminus SPACE(s(n-1)). For a binary L the supposition łims = infty is sufficient. The witness languages differ from each language from the lower classes on infinitely many words. We use so called demon (Turing) machines where the tape limit is given automatically without any construction. The results hold for deterministic and nondeterministic demon machines and also for alternating demon machines with a constant number of alternations, and with unlimited number of alternations. The sharpness of the results is ensured by using a very sensitive measure of space complexity of Turing computations which is defined as the amount of the tape required by the simulation (of the computation in question) on a fixed universal machine. As a proof tool we use a succint diagonalization method.