# 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. – Yuval Filmus 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. – Don Fanucci May 22 '17 at 7:27
• Did you notice that they changed the language $L$? – Yuval Filmus 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

## 1 Answer

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.