<p>It is well-known that <a href="https://mathoverflow.net/questions/40770/how-do-we-know-that-p-linspace-without-knowing-if-one-is-a-subset-of-the-othe/40771#40771"><span class="math-container">$\mathsf{P}\neq\mathsf{SPACE}(n)$</span></a>, either for <span class="math-container">$\mathsf{SPACE}=\mathsf{DSPACE}$</span> or <span class="math-container">$\mathsf{NSPACE}$</span>, and it is conjectured that both <span class="math-container">$\mathsf{P}\not\subseteq\mathsf{DSPACE}(n)$</span> and <span class="math-container">$\mathsf{P}\not\supseteq\mathsf{DSPACE}(n)$</span>. Now by <a href="https://www.sciencedirect.com/science/article/pii/S002200007080006X?via%3Dihub" rel="nofollow noreferrer">Savitch's theorem</a> <span class="math-container">$\mathsf{NSPACE}(n)\subseteq\mathsf{DSPACE}(n^2)$</span> and it seems that at least <span class="math-container">$\mathsf{DSPACE}(n\log n)\subseteq\mathsf{NSPACE}(n)$</span>. At any rate we know that <span class="math-container">$\text{SAT}\in\mathsf{DSPACE}(n)$</span> and is <span class="math-container">$\mathsf{NP}$</span>-complete under logspace reduction -see the comments <a href="https://cs.stackexchange.com/questions/83072/proving-sat-is-in-l">here</a>. Then my question is whether i am right to deduce from the above, without having worked it out rigorously, that <span class="math-container">$\mathsf{NP}\subseteq\mathsf{NSPACE}(n)$</span> -or at least <span class="math-container">$\mathsf{NP}\subseteq\mathsf{DSPACE}(n^2)$</span> ? 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.</p>
<p>EDIT: Note that the argument that proves that <span class="math-container">$\mathsf{P}\neq\mathsf{SPACE}(n)$</span> -essentially a reformulation of the space hierarchy theorem for polynomial bounds of different degrees- proves that <span class="math-container">$\mathsf{P}\neq\mathsf{SPACE}(n^k)$</span> for all <span class="math-container">$k$</span>, and also proves that <span class="math-container">$\mathsf{NP}\neq\mathsf{SPACE}(n^k)$</span>. As Emil Jeřábek explains what makes <span class="math-container">$\mathsf{NP}$</span> or <span class="math-container">$\mathsf{P}$</span> probably not contained in <span class="math-container">$\mathsf{SPACE}(n^k)$</span> for any <span class="math-container">$k$</span> 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 <span class="math-container">$\mathsf{SPACE}(n^k)$</span> when starting from complicated enough problems inside it -even in the intersection <span class="math-container">$\mathsf{P}$</span> or <span class="math-container">$\mathsf{NP}\cap\mathsf{SPACE}(n^k)$</span>. The unlikely hypotheses <span class="math-container">$\mathsf{P}$</span> or <span class="math-container">$\mathsf{NP}=\mathsf{PSPACE}$</span> also imply that <span class="math-container">$\mathsf{P}$</span> or <span class="math-container">$\mathsf{NP}\supsetneq\mathsf{SPACE}(n^k)$</span> for all <span class="math-container">$k$</span>, by the inequality above.</p>

CC BY-SA 4.0
2023-09-08T07:52:52.997Z
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.
Emil Jeřábek
CC BY-SA 4.0
2023-09-08T08:17:19.743Z
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
CC BY-SA 4.0
2023-09-08T08:47:55.943Z
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.
Emil Jeřábek
CC BY-SA 4.0
2023-09-08T08:51:27.590Z
Thank you @EmilJeřábek. And about comparing NSPACE and DSPACE ?
plm
CC BY-SA 4.0
2023-09-08T08:58:21.457Z
As far as I know, NSPACE does not offer any space reduction over DSPACE.
Emil Jeřábek
<cc.complexity-theory><np-hardness><space-complexity>
Is $\mathsf{NP}\subseteq\mathsf{NSPACE}(n)$?
plm
# Is $\mathsf{NP}\subseteq\mathsf{NSPACE}(n)$?

(Asked by: username_0 on 2023-09-08)

It is well-known that [$\mathsf{P}\neq\mathsf{SPACE}(n)$](https://mathoverflow.net/questions/40770/how-do-we-know-that-p-linspace-without-knowing-if-one-is-a-subset-of-the-othe/40771#40771), 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](https://www.sciencedirect.com/science/article/pii/S002200007080006X?via%3Dihub) $\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](https://cs.stackexchange.com/questions/83072/proving-sat-is-in-l). 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 username_1 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.

**Tags:** cc.complexity-theory, np-hardness, space-complexity

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: Thank you @EmilJeřábek. And about comparing NSPACE and DSPACE ?  
> **username_1**: As far as I know, NSPACE does not offer any space reduction over DSPACE.  

---

## 0 answers

