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))$?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.