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