Breakdown of the Space Hierarchy Theorem

Question

Say that we have two deterministic space complexity classes $SPACE(n^k)$ and $SPACE(f(n))$ where $f(n) = n^{k-1}$ when $n$ is odd and $f(n) = n^{k+1}$ when $n$ is even. Obviously, if $f(n)$ were always $n^{k+1}$, we would able to say $SPACE(n^k) \subseteq SPACE(f(n))$ by the Space Hierarchy Theorem, and I believe that as $n$ grows we can still generally say $SPACE(n^k) \subseteq SPACE(f(n))$ (correct me if I'm wrong), but given the condition when $n$ is odd, do we just have to say that always $SPACE(n^k) \neq SPACE(f(n))$?

Answer 1

Here is a strengthening of the space hierarchy theorem.

Suppose that $f(n) \geq \log n$ is space-constructible, that $g(n) = o(f(n))$, and that $h(n) = g(n)$ infinitely often (that is, for infinitely many $n$). Then $\mathrm{SPACE}(f(n)) \not\subseteq \mathrm{SPACE}(h(n))$.

Here $\mathrm{SPACE}(f(n))$ consists of all languages decided by multi-tape Turing machines which use $O(f(n))$ space.

Proof. We closely follow the Wikipedia proof of the space hierarchy theorem. Let $$ L = \{ (\langle M \rangle, 1^m) : \text{when $M$ is run on $x = (\langle M \rangle, 1^m)$, it uses $\le f(|x|)$ space and rejects} \} $$ Here $1^m$ is just $1$ repeated $n$ times, and we encode the input such that its size is exactly $C_M + m$, for some constant $C_M$ depending only on $M$.

The language $L$ is clearly in $\mathrm{SPACE}(f(n))$. Suppose that it is also in $\mathrm{SPACE}(h(n))$, say accepted by a machine $M$ which uses space $Ch(n)$. Since there are infinitely many $n$ such that $h(n) = g(n)$ and $g(n) = o(f(n))$, we can find $m$ such that $Ch(C_M + m) = Cg(C_M + m) \leq f(C_M + m)$. When running $M$ on $x = (\langle M \rangle, 1^m)$, it uses at most $Ch(|x|) = Cg(|x|) \leq f(|x|)$, and so $(\langle M \rangle, 1^m) \in L$ iff $M$ doesn't accept $(\langle M \rangle, 1^m)$, contradicting the assumption that $M$ computes $L$. $\square$

Using this, you can check that $\mathrm{SPACE}(n^k)$ and $\mathrm{SPACE}(f(n))$, where $f(n)$ is the function defined in your post, are incomparable: none is contained in the other.