<p>If $\mathrm{P\subseteq CSL}$, then $\mathrm{P\subseteq DSPACE}(n^2)$. By a padding argument, this implies
$$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}\bigl(t(n)^\epsilon\bigr)$$
for every superpolynomial well-behaved function $t(n)$ and every $\epsilon&gt;0$. I believe such a strong advantage of space over time is not expected to be true. The best currently known result in this direction is
$$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}(t(n)/\log t(n)),$$
due to Hopcroft, Paul, and Valiant.</p>

CC BY-SA 3.0
2017-02-04T20:14:51.267Z
Thanks, I have accepted this answer now, although, given the nature of this question, further replies would of course still be welcome.
mak
CC BY-SA 3.0
2017-02-01T16:12:22.057Z
2017-02-01T16:12:22.057Z
Emil Jeřábek
<p>It is unknown whether $P\subseteq CSL$ or $P\not\subseteq CSL$, where</p>

<ul>
<li>$P$ is the set of all languages decidable in polynomial time on a deterministic Turing machine, and</li>
<li>$CSL$ is the class of context-sensitive languages, known to be equivalent to $NSPACE(O(n))$, the languages decided by linear-bounded automata.</li>
</ul>

<p>For many open questions, there is a tendency towards one answer (<em>a la</em> "most experts believe that $P\neq NP$"). Is there something like this for this question?</p>

<p>In particular, would either answer have unexpected consequences? I can only see expected (but unproven) consequences:</p>

<ul>
<li>If $P\subseteq CSL$, then $P\subseteq NSPACE(O(n))\subsetneq NSPACE(O(n^2))$ (space hierarchy theorem), hence $P\subsetneq PSpace$.</li>
<li>If $P\not\subseteq CSL$, then there is a language $l\in P\setminus NSPACE(O(n))$ and therefore $l\in P\setminus NL$, hence $NL\subsetneq P$.</li>
</ul>

<p>(Acknowledgement: The second consequence of these two was pointed out by Yuval Filmus at <a href="https://cs.stackexchange.com/questions/69614/">https://cs.stackexchange.com/questions/69614/</a>)</p>

<cc.complexity-theory><fl.formal-languages><polynomial-time>
What is the conjectured relationship between P (PTime) and Type 1 (context-sensitive) languages?
mak
# What is the conjectured relationship between P (PTime) and Type 1 (context-sensitive) languages?

(Asked by: username_0 on 2017-02-01)

It is unknown whether $P\subseteq CSL$ or $P\not\subseteq CSL$, where

* $P$ is the set of all languages decidable in polynomial time on a deterministic Turing machine, and
* $CSL$ is the class of context-sensitive languages, known to be equivalent to $NSPACE(O(n))$, the languages decided by linear-bounded automata.

For many open questions, there is a tendency towards one answer (*a la* "most experts believe that $P\neq NP$"). Is there something like this for this question?

In particular, would either answer have unexpected consequences? I can only see expected (but unproven) consequences:

* If $P\subseteq CSL$, then $P\subseteq NSPACE(O(n))\subsetneq NSPACE(O(n^2))$ (space hierarchy theorem), hence $P\subsetneq PSpace$.
* If $P\not\subseteq CSL$, then there is a language $l\in P\setminus NSPACE(O(n))$ and therefore $l\in P\setminus NL$, hence $NL\subsetneq P$.

(Acknowledgement: The second consequence of these two was pointed out by Yuval Filmus at <https://cs.stackexchange.com/questions/69614/>)

**Tags:** cc.complexity-theory, fl.formal-languages, polynomial-time

---

## 1 answers

### Answer by username_1 on 2017-02-01. Score: 12 | Accepted answer

If $\mathrm{P\subseteq CSL}$, then $\mathrm{P\subseteq DSPACE}(n^2)$. By a padding argument, this implies
$$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}\bigl(t(n)^\epsilon\bigr)$$
for every superpolynomial well-behaved function $t(n)$ and every $\epsilon>0$. I believe such a strong advantage of space over time is not expected to be true. The best currently known result in this direction is
$$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}(t(n)/\log t(n)),$$
due to Hopcroft, Paul, and Valiant.

> **Comments:**
> **username_0**: Thanks, I have accepted this answer now, although, given the nature of this question, further replies would of course still be welcome.  

---

