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}\}$.


migrated from cstheory.stackexchange.com Mar 25 '13 at 8:52

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.