I have a question have to answer, so that, if anyone have the answer, please help me.

The problem is: Give a self-contained proof that $\mathsf{L} \neq \mathsf{PSPACE}$ where:

$\qquad \mathsf{L} = \{ L \mid L \text{ is a language decidable in logarithmic space} \}$ and

$\qquad \mathsf{PSPACE} = \{ L \mid L \text{ is a language decidable in polynomial space}\}$.

  • $\begingroup$ Just take e.g. $f(n)=n^2$ and follow the proof of the space hierarchy theorem. $\endgroup$ – Shaull Mar 25 '13 at 6:45
  • $\begingroup$ This question does not show any effort on your part. What have you tried? $\endgroup$ – Raphael Mar 25 '13 at 10:39

You might start with wikipedia: Space hierarchy theorem.

| cite | improve this answer | |

Your Answer

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