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.
