I want to prove the non deterministic space hierarchy theorem.

Let $f(n),g(n)\geq\log n$ be space constructible functions such that $f(n)=o(g(n))$, Prove:

$$NSPACE(f(n))\subsetneq NSPACE(g(n))$$

I feel that the standard way of constructing a TM that takes as an input a TM and simulates the machine on itself, then flipping the output won't work because the input is a nondetrministic TM maybe. Can someone suggest a hint?

  • $\begingroup$ Take a look at the Wikipedia article. $\endgroup$ May 22, 2017 at 7:25
  • $\begingroup$ @YuvalFilmus I actually looked there but their change of proof from the deterministic proof, is not clear since they change stage 4 and know it is not clear why L is still acceptable in NSPACE(g(n)), I mean can you explain why their language L is acceptable in NSPACE(g(n)), because their machine is wrong. $\endgroup$ May 22, 2017 at 7:27
  • $\begingroup$ Did you notice that they changed the language $L$? $\endgroup$ May 22, 2017 at 7:37
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    May 22, 2017 at 10:12

2 Answers 2


The Wikipedia proof for the non-deterministic doesn't flip the output. It considers the language $$ L = \{ (\langle M \rangle, 1^t) : \text{$M$ accepts $(\langle M \rangle, 1^t)$ in space $g(|(\langle M \rangle, 1^t)|)$} \}. $$ This language is in $\mathsf{NSPACE}(g)$. The Immerman–Szelepcsényi theorem shows that if $L \in \mathsf{NSPACE}(f)$ then also $\overline{L} \in \mathsf{NSPACE}(f)$, which leads to a contradiction.


This is just an elaboration of the proof noted above. Consider the following algorithm:

A(x) {

Step 1: If x is not of the form $(M,1^{t})$ for some nondeterministic Turing machine $M$ and integer $t$, reject.

Step 2: Compute $q = 2^{g(n)}$ where $n$ is the length of $x$.
/ * Needs $O(g(n))$ deterministic space, assuming $g$ is constructible */

Step 3: Using a universal Turing machine, simulate $M$ on $x$ for $q$ steps. If $M$ accepts $x$, accept $x$. Otherwise, reject $x$.
/ * This simulation requires only $O(g(n))$ space */

Claim: $L(A)$ is not equal to $L(M)$ for any $O(f(n))$ space non deterministic Turing machine if $f(n) = o(g(n))$ and $f(n)$ is constructible.

Proof: For the sake of contradiction, assume that a non deterministic Turing machine $M$ accepts $L(A)$ in $O(f(n))$ space. Then, by Immerman-Szelepscsenyi theorem, there exists a machine $N$ that accepts the complement of $L$ in $O(f(n))$ space.

Consider a string $x$ of the form $x = (N, 1^{t})$ of length $n$ such that $t$ is large enough to ensure that the simulation of $N$ on input $x$ in step 3 of the algorithm runs to completion on all computational paths of $N$.

Now suppose $(N, 1^{t})\in L(A)$. By Step 3 of the algorithm, this means that $N$ accepts $(N, 1^{t})$ on at least one computational path - that is, $(N, 1^{t})\in L(N)$. However, both $A$ and $N$ cannot accept the input $(N, 1^{t})$ because of our assumption that $L(N)$ is the complement of $L(A)$.

Hence, we conclude that $A$ does not accept $(N, 1^{t})$. But this too is contradictory. By Step 3 of the algorithm, $N$ must reject $(N, 1^{t})$ on all computational paths. In other words, $N$ must reject $(N, 1^{t})$. But both $A$ and $N$ cannot reject $(N, 1^{t})$ as $L(N)$ was assumed to the the complement of $L(A)$.

We conclude that our assumption that $M$ accepts $L(A)$ is contradictory and that $L(A)$ is different from the language accepted by any non deterministic Turing machine that uses $O(f(n))$ space for any $f(n)=o(g(n))$.


Your Answer

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

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