4
$\begingroup$

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:

  1. 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.
  2. 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.
  3. 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.

$\endgroup$
3
  • 1
    $\begingroup$ Actually context-sensitive languages correspond to $\mathsf{NSPACE}(n)$ rather than $\mathsf{DPSACE}(n)$. $\endgroup$ Jan 31, 2017 at 21:55
  • $\begingroup$ @Yuval Filmus Thanks, fixed in question. $\endgroup$
    – mak
    Feb 1, 2017 at 11:02
  • 1
    $\begingroup$ I have now posted a follow-up question regarding the conjectured answer to this open question at cstheory: cstheory.stackexchange.com/questions/37450 $\endgroup$
    – mak
    Feb 1, 2017 at 15:24

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Btw. I am writing "PTime" rather than P in the question to make this more findable in search engines. $\endgroup$
    – mak
    Feb 1, 2017 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.