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.

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


Your Answer

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