2
$\begingroup$

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) ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I like this reduction. If only all proofs were this elegant. :-) $\endgroup$
    – LowerBounds
    Commented Mar 29, 2011 at 7:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .