# Language in Space(n) but not in NP

For $lim_{n \rightarrow \infty} \frac{ f(n) \log n } { g(n) } = 0$ we can construct languages in $DTime(g(n))$ but not in $DTime(f(n))$.

We know how to prove $Space(n) \neq NP$. Since $x \Rightarrow x 1^{|x|^2}$ is closed under NP but not Space due to the Space hierarchy theorem.

Question: do we know of any langauges in Space(n), but not in NP; or any languages in NP but not Space(n) ?

-

Neither part of your question is known. To see this, note that $PSPACE$ contains $SPACE(n)$ (and $NP$), so exhibiting a language in $SPACE(n)$ not in $NP$ would separate $PSPACE$ and $NP$ - this is not known.

$SPACE(n)$ contains $L$ (logspace), and it is open whether $NP=L$ (note that $NP$ contains $L$). Thus, giving a language which is in $NP$ but not in $SPACE(n)$ would separate $NP$ and $L$ - also not known.

-
I like this reduction. If only all proofs were this elegant. :-) –  LowerBounds Mar 29 '11 at 7:34