# non deterministic space hierarchy

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?

• Take a look at the Wikipedia article. May 22 '17 at 7:25
• @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. May 22 '17 at 7:27
• Did you notice that they changed the language $L$? May 22 '17 at 7:37
• 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!
– Raphael
May 22 '17 at 10:12

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