A language in NSPACE(O(n)) and very likely not in DSPACE(O(n))

Question

Actually I found that the set of context-sensitive Languages, $\mathbf{CSL}$ ($\mathbf{=NSPACE(O(n)) = LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular languages) or $\mathbf{CFL}$ (context-free languages). And also the open problem $\mathbf{DSPACE(O(n))} =^{?} \mathbf{NSPACE(O(n))}$ is not so famous as the "analogous" problem: "$\mathbf{P} =^{?} \mathbf{NP}$".

Well, is there really such an analogy:?

1. Is there a language in $\mathbf{CSL}$ which couldn't be proved to be in $\mathbf{DSPACE(O(n))}$ (like $\mathbf{NP}$ complete languages)?
2. Moreover: Is there a language $L$ in $\mathbf{CSL}$ which is "complete" in the following sense: if we can prove that $L$ is in $\mathbf{DSPACE(O(n))}$ we get that $\mathbf{DSPACE(O(n)) = NSPACE(O(n))}$?
3. (Maybe just a matter of opinion) Are both problems on the same level of difficulty?

Answer 1

The more well-known version of these questions is the $\mathsf{L} \stackrel?= \mathsf{NL}$ question. If $\mathsf{L} = \mathsf{NL}$ then a (slightly tricky) padding argument shows that $\mathsf{DSPACE}(n) = \mathsf{NSPACE}(n)$, and so $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$ implies the well-known conjecture $\mathsf{L} \neq \mathsf{NL}$.

The conjecture $\mathsf{L} \neq \mathsf{NL}$ is considered (by some) to be more approachable than the conjecture $\mathsf{P} \neq \mathsf{NP}$. I'm not sure many people have an opinion on the conjecture $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$.

The bigger picture here is whether Savitch's theorem, which states that $\mathsf{NSPACE}(t(n)) \subseteq \mathsf{DSPACE}(t(n)^2)$ for reasonable $t(n) \geq \log n$, is tight. While $\mathsf{NPSPACE} = \mathsf{PSPACE}$, I think that most people believe that $\mathsf{NSPACE}(n^k) \neq \mathsf{DSPACE}(n^k)$. On the other hand, I'm not sure that people believe that $t(n)^2$ is the optimal blowup; perhaps a smaller exponent also works, at least in some cases. See for example a recent arXiv paper, The parameterized space complexity of model-checking bounded variable first-order logic, by Yijia Chen, Michael Elberfeld, and Moritz Müller.

Answer 2

1. Yes, there are CSL complete languages under DSPACE(O(n)) reductions. Basically still a variant of directed reachability, which can be restricted to acyclic reachability if desired.
2. Yes, see 1.

3. You mean, is the question DSPACE(O(n))=^?NSPACE(O(n)) on the same level of difficulty as the question P=^?NP? Well, we have good reasons to believe that P is a strict subset of NP, but I am not aware of similarly well worked out reasons to believe that DSPACE(O(n)) is a strict subset of NSPACE(O(n)). Let me focus on the easier question $\mathsf{L} \stackrel?= \mathsf{NL}$. Random walks are "not bad" for exploring (with respect to reachability) the undirected graphs associated with SL. The obvious trivial analogous random walk on a directed graph will fail badly at exploring a directed graph (with respect to reachability). But maybe there are other similar randomized ways to explore a directed graph (or a layered acyclic graph). Based on Savitch's theorem, I would even guess that there are such ways, if we are willing to save a changing set of $O(\log n)$ positions within the directed graph during the random exploration process. And then the challenge would be to understand whether saving fewer than $O(\log n)$ positions won't allow good randomized exploration.

   Even after understanding whether we should believe $\mathsf{L} \neq \mathsf{NL}$, proving it will likely be just as impossible as proving $\mathsf{P} \neq \mathsf{NP}$. Ryan Williams gives one explicit reason and says:

   Beyond that, I know of no particular reason to believe it is "hard to prove" other than the observation that many people have tried and none have succeeded yet.

   to answer Is ALogTime != PH hard to prove (and unknown)? Lance Fortnow basically brought up the question and still disagrees. My own lesson was:

   This means that the statement "ALogTime != PH" is exactly the place where the difficulties for proving separation results start. It may be noted that this statement is actually equivalent to "ALogTime != NP", since "ALogTime = NP" would imply "P=NP=PH".

Answer 3

Adding to the other answers, there is a notion of reducibility and completeness for the CSL vs. DCSL problem, namely log-lin reducibility, and there are quite natural CSL-complete problems. For example, the inequivalence problem for regular expressions. Here is a very similar question to yours, together with an answer providing further background and references: https://cstheory.stackexchange.com/questions/1905/completeness-and-context-sensitive-languages

Answer 4

$SAT$ is in $NTIME(n) \subseteq DSPACE(n)$. Under the assumption of $L = P$, then $NP$ is strictly contained in $DSPACE(n)$ since we can transform polynomial time reductions into logarithmic space reductions and $DSPACE(n)$ is closed under logarithmic space reductions. They are not equal due to the Hierarchy Theorem. However, when $L = NL$ then $DSPACE(n) = NSPACE(n)$ as result of applying the padding argument. Since $L = NL$ when $L = P$ then $NP$ is strictly contained in $NSPACE(n)$. However, $CSL = NSPACE(n)$ and thus $CSL \neq NP$ and hence, there could not be the case that some $CSL-complete$ problem is in $NP$ because that would imply a contradiction with $CSL \neq NP$ that we obtained after assuming $L = P$.

In addition, you could see a possible attempt of proving $L = P$ here:

https://hal.archives-ouvertes.fr/hal-01999029