Qual é a relação conjeturada entre as linguagens P (PTime) e Tipo 1 (sensível ao contexto)?

$P\subseteq CSL$$P\not\subseteq CSL$

• $P$ é o conjunto de todos os idiomas decidíveis em tempo polinomial em uma máquina de Turing determinística, e
• $CSL$ é a classe de linguagens sensíveis ao contexto, conhecida por ser equivalente a , as linguagens decididas por autômatos com limites lineares.$NSPACE(O(n))$

Para muitas perguntas abertas, há uma tendência a uma resposta (à la "a maioria dos especialistas acredita que "). Existe algo assim para esta pergunta?$P\neq NP$

Em particular, a resposta teria consequências inesperadas? Só consigo ver as consequências esperadas (mas não comprovadas):

• Se , (teorema da hierarquia de espaço), portanto, .$P\subseteq CSL$$P\subseteq NSPACE(O(n))\subsetneq NSPACE(O(n^2))$$P\subsetneq PSpace$
• Se , então existe uma língua e, por conseguinte, , portanto, .$P\not\subseteq CSL$$l\in P\setminus NSPACE(O(n))$$l\in P\setminus NL$$NL\subsetneq P$

(Agradecimento: A segunda consequência desses dois foi apontada por Yuval Filmus em /cs/69614/ )

Se , então . Por um argumento de preenchimento, isso implica para cada função superpolinomial bem comportada e a cada . Acredito que não se espera que uma vantagem tão forte do espaço ao longo do tempo. O resultado mais conhecido atualmente nessa direção é devido a Hopcroft, Paul e Valiant.$\mathrm{P\subseteq CSL}$$\mathrm{P\subseteq DSPACE}(n^2)$

$$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}\bigl(t(n)^\epsilon\bigr)$$ $t(n)$$\epsilon>0$ $$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}(t(n)/\log t(n)),$$