2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Take a look at the Wikipedia article. $\endgroup$ – Yuval Filmus May 22 '17 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$ – Don Fanucci May 22 '17 at 7:27
  • $\begingroup$ Did you notice that they changed the language $L$? $\endgroup$ – Yuval Filmus May 22 '17 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 '17 at 10:12
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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