# What is the conjectured relationship between P (PTime) and Type 1 (context-sensitive) languages?

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

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.