Space Hierarchy Theorem - Refinement of Space Hierarchy

Refinement of Space Hierarchy

If space is measured as the number of cells used regardless of alphabet size, then SPACE(f(n)) = SPACE(O(f(n))) because one can achieve any linear compression by switching to a larger alphabet. However, by measuring space in bits, a much sharper separation is achievable for deterministic space. Instead of being defined up to a multiplicative constant, space is now defined up to an additive constant. However, because any constant amount of external space can be saved by storing the contents into the internal state, we still have SPACE(f(n)) = SPACE(f(n)+O(1)).

Assume that f is space-constructible. SPACE is deterministic.

• For a wide variety of sequential computational models, including for Turing machines, SPACE(f(n)-ω(log(f(n)+n))) ⊊ SPACE(f(n)). This holds even if SPACE(f(n)-ω(log(f(n)+n))) is defined using a different computational model than SPACE(f(n)) because the different models can simulate each other with O(log(f(n)+n)) space overhead.
• For certain computational models, including Turing machines with a fixed number of tapes (with one head per tape) and fixed alphabet size and with delimiters for the visited segment on each tape, SPACE(f(n)-ω(1)) ⊊ SPACE(f(n)).

The proof is similar to the proof of the space hierarchy theorem, but with two complications: The universal Turing machine has to be space-efficient, and the reversal has to be space-efficient. One can generally construct universal Turing machines with O(log(space)) space overhead, and under appropriate assumptions, just O(1) space overhead (which may depend on the machine being simulated). For the reversal, the key issue is how to detect if the simulated machine rejects by entering an infinite (space-constrained) loop. Simply counting the number of steps taken would increase space consumption by about f(n). At the cost of a potentially exponential time increase, loops can be detected space-efficiently as follows:

Modify the machine to erase everything and to go to a specific configuration A on success. Use depth-first search to determine whether A is reachable in the space bound from the starting configuration. The search starts at A and goes over configurations that lead to A. Because of determinism, this can be done in place and without going into a loop. Also (but this is not necessary for the proof), to determine whether the machine exceeds the space bound (as opposed to looping within the space bound), we can iterate over all configurations about to exceed the space bound and check (again using depth-first search) whether the initial configuration leads to any of them.