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

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?
• $L$ vs. $NL$ is more analogous problem than $P$ vs. $NP$. – rus9384 Aug 24 '17 at 12:00
• I think you received good enough answers; you may want to accept one. If those two answerers don't know, the question is probably open. Feel free to re-post on Theoretical Computer Science if you think that's helpful, but please make sure to link back here so people don't waste their time writing up the same things. – Raphael Sep 5 '17 at 19:43

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.

• This helps to see the related problems. Thanks for that. – rl1 Jul 31 '17 at 18:09
• You said: "I'm not sure many people have an opinion on the conjecture $\mathsf{DSPACE}(n)\neq \mathsf{NSPACE} (n)$." But the conjecture is still a subject of research, isn't it? – rl1 Aug 1 '17 at 11:03
• If by that you mean subject of active research, I'm not sure. But it will certainly be interesting (for the community) to know the answer. – Yuval Filmus Aug 1 '17 at 11:59
• Why padding argument is tricky? If $\mathsf{L = NL}$ doesn't it mean that DTM needs $O(\log n)$ space to simulate NTM? – rus9384 Aug 3 '17 at 0:42
• @rus9384 Try to actually run the argument to see the difficulty, or take a look at the link. – Yuval Filmus Aug 3 '17 at 5:34
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".

• Thanks! This would answer all my questions, but I don't understand your answer 1. s-t-connectivity (reachability) in directed graphs is an $\mathsf{NL}$-complete problem (NL-complete). So could you explain more the "variant" you mean (or give a link)? – rl1 Aug 2 '17 at 16:01
• @rl1 The encoding of the directed graph is different, and especially its size is O(exp(n)). Basically the transition graph of the corresponding Turing machine (with fixed memory limit). – Thomas Klimpel Aug 2 '17 at 16:15
• Do you have a link for the exact definition of your variant and for the "completenes" proof? – rl1 Aug 3 '17 at 6:36
• @rl1 I checked out some introductory complexity theory books. The treatment in Papadimitriou of that topic is good and detailed, the treatment in Arora/Barak is also good enough. Less sure whether the treatment in Sipser or Goldreich will give you what you want. Papadimitriou also makes sense, because this is an older book and this is an older topic, and because the theme of encoding transition graphs by suitably restricted Turing machines also reoccurs in newer research by Papadimitriou. – Thomas Klimpel Aug 5 '17 at 13:10
• Papadimitriou (Computational Complexity, 1995) gives an exercise that $\mathbf{CSL} = \mathbf{NSPACE}( n)$ (p. 67) and the theorem that "REACHABILITY is $\mathbf{NL}$-complete (p. 398). But this doesn't answer my questions. So, unfortunately, I couldn't find the result you mentioned in your answer in 1. and 2. – rl1 Aug 7 '17 at 16:03

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

$$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