# Relationship between L and PSPACE

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.comMar 25 '13 at 8:52

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

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