Is every language in PTime also context-sensitive?

Context-sensitive languages are exactly those that can be recognised using linearly bounded automata, i.e., those in NSPACE(O($n$)). This subsumes all languages that can be recognised in linear time, i.e., DTIME(O($n$)), since you can only use n memory cells in n steps.

However, this leaves open the possibility that some super-linear polynomial time problems are not context-sensitive. Is this likely or even known? Are there examples?

Here are some general facts that one should be aware of:

• There are PSpace-complete problems in NSPACE(O($n$)), e.g., TrueQBF. One might think that this answers my question, since PTime is contained in PSpace.

• However, not all PSpace-complete problems are in NSPACE(O($n$)). Indeed, we know that there are strictly more languages in NSPACE(O($n^2$)) than in NSPACE(O($n$)) (space-hierarchy theorem). In other words, PSpace is strictly larger than NSPACE(O($n$)), i.e., some PSpace languages are not context-sensitive.

• PTime is subsumed by PSpace, but not necessarily by NSPACE(O(n)) (hence my question). Indeed, it seems unlikely that today's answer to my question is "All PTime languages are context-sensitive." If we would know this for sure, then (using 2.) we would know that PTime is strictly smaller than PSpace, which is an open conjecture today.

However, I don't see an immediate reason why there should not be a known example of a non-context-sensitive language in PTime.

Conclusion after reading the answer: We know very little. Mostly, we know $NL\subseteq NSPACE(O(n))\subseteq PSpace$ and $NL\subseteq P\subseteq NP\subseteq PSpace$. It is unclear how $NSPACE(O(n))$ (CSL) compares to $P$ and $NP$. If we could show that $P\subseteq NSPACE(O(n))$, this would show $P\subsetneq PSpace$ (open); if we could show $P\not\subseteq NSPACE(O(n))$, then this would show $NL\subsetneq P$ (open). Both of these open conjectures are expected to be true, which is not of any help for making a guess regarding the answer to my question.

It is an open question to separate $\mathsf{L}$ (that is, $\mathsf{DSPACE}(\log n)$) and $\mathsf{P}$ (what you call PTime), so in particular we have no example of a polytime language which requires superlogarithmic space.

StackExchange Computer Science Q#69614, answer score: 6