|
2
|
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) ? |
||
|
|
|
9
|
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. |
|||
|
