# Is there 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))$ $= \mathbf{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)) \stackrel?= \mathbf{NSPACE}(O(n))$ is not so famous as the "analogous" problem: $\mathbf{P} \stackrel?= \mathbf{NP}$.

So I have two questions:

1. Is there a language in $\mathbf{CSL}$ which couldn't be proved to be in $\mathbf{DSPACE}(O(n))$?
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)) = \mathbf{CSL}$?

Notice: I have asked these questions in cs.stackexchange and got some interesting Answers but not a concrete (proven) example for such a language: https://cs.stackexchange.com/questions/79528/a-language-in-nspaceon-and-very-likely-not-in-dspaceon

• Neat question! :) – Michael Wehar Sep 6 '17 at 4:20
• Just take any language complete for NSPACE(n) under linear-time reductions. – Emil Jeřábek Sep 6 '17 at 8:21
• $NPSPACE=NSPACE(poly(n))=DSPACE(poly(n))=PSPACE$ So my prior is that $NSPACE(O(n))$ and $DSPACE(O(n))$ are fairly close and not analogous to $P$ versus $NP$. – Thomas Sep 6 '17 at 8:31
• @Thomas, I already pointed that this is more analogous to $L$ vs. $NL$. – rus9384 Sep 7 '17 at 5:35
• I don’t know what is many, but it’s certainly straightforward to construct examples of such languages: e.g., $L_1=\{\langle M,w\rangle:\text{$M$is an NTM and accepts$w$within space$|w|$}\}$, or $L_2={}$ succinct $s$-$t$-connectivity (i.e., the set of Boolean circuits $C$ in $2n$ variables such that there is a directed path from $\vec0$ to $\vec1$ in the directed graph on vertex set $\{0,1\}^n$ whose edge relation is computed by $C$). Surely some such have been given in the literature, but I can’t point you to a book. – Emil Jeřábek Sep 7 '17 at 14:10