# Is $\mathsf{NP}\subseteq\mathsf{NSPACE}(n)$?

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.

• 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. Sep 8 at 7:52
• 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.
– plm
Sep 8 at 8:17
• 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. Sep 8 at 8:47
• Thank you @EmilJeřábek. And about comparing NSPACE and DSPACE ?
– plm
Sep 8 at 8:51
• As far as I know, NSPACE does not offer any space reduction over DSPACE. Sep 8 at 8:58