3
$\begingroup$

It is well-known that $\mathsf{P}\neq\mathsf{SPACE}(n)$, either for $\mathsf{SPACE}=\mathsf{DSPACE}$ or $\mathsf{NSPACE}$, and it is conjectured that both $\mathsf{P}\not\subseteq\mathsf{DSPACE}(n)$ and $\mathsf{P}\not\supseteq\mathsf{DSPACE}(n)$. Now by Savitch's theorem $\mathsf{NSPACE}(n)\subseteq\mathsf{DSPACE}(n^2)$ and it seems that at least $\mathsf{DSPACE}(n\log n)\subseteq\mathsf{NSPACE}(n)$. At any rate we know that $\text{SAT}\in\mathsf{DSPACE}(n)$ and is $\mathsf{NP}$-complete under logspace reduction -see the comments here. Then my question is whether i am right to deduce from the above, without having worked it out rigorously, that $\mathsf{NP}\subseteq\mathsf{NSPACE}(n)$ -or at least $\mathsf{NP}\subseteq\mathsf{DSPACE}(n^2)$ ? Or equivalently, i believe, that nondeterministic linear space is large enough to contain the closure of deterministic linear space under logspace reduction -which from SAT yields the same class as linear space and many-one polytime reductions. Thank you.

EDIT: Note that the argument that proves that $\mathsf{P}\neq\mathsf{SPACE}(n)$ -essentially a reformulation of the space hierarchy theorem for polynomial bounds of different degrees- proves that $\mathsf{P}\neq\mathsf{SPACE}(n^k)$ for all $k$, and also proves that $\mathsf{NP}\neq\mathsf{SPACE}(n^k)$. As Emil Jeřábek explains what makes $\mathsf{NP}$ or $\mathsf{P}$ probably not contained in $\mathsf{SPACE}(n^k)$ for any $k$ is that the reductions under which the former are closed increase the size of instances by a polynomial, thus a priori taking us outside of $\mathsf{SPACE}(n^k)$ when starting from complicated enough problems inside it -even in the intersection $\mathsf{P}$ or $\mathsf{NP}\cap\mathsf{SPACE}(n^k)$. The unlikely hypotheses $\mathsf{P}$ or $\mathsf{NP}=\mathsf{PSPACE}$ also imply that $\mathsf{P}$ or $\mathsf{NP}\supsetneq\mathsf{SPACE}(n^k)$ for all $k$, by the inequality above.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ No, very likely NP is not included in NSPACE($n^k$) for any fixed $k$. Your deduction is wrong because the logspace reduction may (and indeed will) increase the input size from $n$ to $n^c$, where $c$ is a constant depending on the NP-language being reduced. $\endgroup$
    – Emil Jeřábek
    Sep 8 at 7:52
  • $\begingroup$ Thank you very much @EmilJeřábek. Just to make things clearer in my mind, could you explain on a simple example how the size of an instance increases when logspace reducing ? Also, do we know how to compare exactly -at least more precisely than what Savitch and the trivial $\mathsf{DCLASS}\subseteq\mathsf{NCLASS}$ provide- $\mathsf{NSPACE}(n)$ and $\mathsf{DSPACE}(f(n))$ for some $f$ faster than linear ? Do we at least know that $\mathsf{DSPACE}(f(n))\subseteq\mathsf{NSPACE}(n)$ for some $f=\omega(n)$ ? Thanks again. $\endgroup$
    – plm
    Sep 8 at 8:17
  • 1
    $\begingroup$ Just look at how the reduction works. The standard reduction of $L\in\mathrm{NTIME}(n^c)$ to SAT introduces variables encoding an accepting run of the NTM for $L$, which is $n^c$ configurations, each of size $n^c$. Thus, the resulting CNF has about $n^{2c}$ variables, and at least as many clauses. $\endgroup$
    – Emil Jeřábek
    Sep 8 at 8:47
  • $\begingroup$ Thank you @EmilJeřábek. And about comparing NSPACE and DSPACE ? $\endgroup$
    – plm
    Sep 8 at 8:51
  • 1
    $\begingroup$ As far as I know, NSPACE does not offer any space reduction over DSPACE. $\endgroup$
    – Emil Jeřábek
    Sep 8 at 8:58

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.