<p>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). </p>

<p>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}$.</p>

<p>So I have two questions:</p>

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

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

CC BY-SA 3.0
2017-09-06T04:20:38.277Z
Neat question!  :)
Michael Wehar
CC BY-SA 3.0
2017-09-06T08:21:02.853Z
Just take any language complete for NSPACE(n) under linear-time reductions.
Emil Jeřábek
CC BY-SA 3.0
2017-09-06T08:31:32.347Z
$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 Steinke
CC BY-SA 3.0
2017-09-07T05:35:30.600Z
@Thomas, I already pointed that this is more analogous to $L$ vs. $NL$.
rus9384
CC BY-SA 3.0
2017-09-07T08:37:51.357Z
@EmilJeřábek Are there many known $\mathbf{CSL}$-languages which are complete under linear-time reductions?  Can you recommend a book or link for this?
rl1
CC BY-SA 3.0
2017-09-07T14:10:27.237Z
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
CC BY-SA 3.0
2017-09-07T16:46:13.157Z
@EmilJeřábek Thanks! I meant with "many" something like the sites with $\mathbf{NP}$-complete problems, e.g.
 https://en.wikipedia.org/wiki/List_of_NP-complete_problems
rl1
<cc.complexity-theory><complexity-classes><np-complete><space-complexity>
Is there a language in NSPACE(O(n)) and (very likely) not in DSPACE(O(n))?
rl1
# Is there a language in NSPACE(O(n)) and (very likely) not in DSPACE(O(n))?

(Asked by: username_0 on 2017-09-06)

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>

**Tags:** cc.complexity-theory, complexity-classes, np-complete, space-complexity

> **Comments:**
> **username_1**: Neat question!  :)  
> **username_2**: Just take any language complete for NSPACE(n) under linear-time reductions.  
> **username_3**: $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$.  
> **username_4**: @Thomas, I already pointed that this is more analogous to $L$ vs. $NL$.  
> **username_0**: @EmilJeřábek Are there many known $\mathbf{CSL}$-languages which are complete under linear-time reductions?  Can you recommend a book or link for this?  
> **username_2**: 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.  
> **username_0**: @EmilJeřábek Thanks! I meant with "many" something like the sites with $\mathbf{NP}$-complete problems, e.g.  https://en.wikipedia.org/wiki/List_of_NP-complete_problems  

---

## 0 answers

