Quelle est la relation conjecturée entre les langues P (PTime) et de type 1 (contextuelles)?

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

• $P$ est l'ensemble de tous les langages décidables en temps polynomial sur une machine de Turing déterministe, et
• $CSL$ est la classe des langages contextuels, connue pour être équivalente à , les langages décidés par des automates linéaires.$NSPACE(O(n))$

Pour de nombreuses questions ouvertes, il y a une tendance à une réponse ( à la "la plupart des experts pensent que "). Y a-t-il quelque chose comme ça pour cette question?$P\neq NP$

En particulier, la réponse aurait-elle des conséquences inattendues? Je ne vois que les conséquences attendues (mais non prouvées):

• Si , alors (théorème de la hiérarchie spatiale), d'où .P ⊆ N S P A C E ( O ( n ) ) ⊊ N S P A C E ( O ( n 2 ) ) P ⊊ P S p a c $P\subseteq CSL$$P\subseteq NSPACE(O(n))\subsetneq NSPACE(O(n^2))$$P\subsetneq PSpace$
• Si , alors il y a une langue et donc , par conséquent .l ∈ P ∖ N S P A C E ( O ( n ) ) l ∈ P ∖ N L $P\not\subseteq CSL$$l\in P\setminus NSPACE(O(n))$$l\in P\setminus NL$$NL\subsetneq P$

(Remerciements: la deuxième conséquence de ces deux a été soulignée par Yuval Filmus sur /cs/69614/ )

Si , alors P ⊆ D S P A C E ( n 2 ) . Par un argument de remplissage, cela implique pour chaque fonction superpolynomiale bien comportée et chaque . Je ne pense pas qu'un tel avantage de l'espace dans le temps ne soit pas vrai. Le meilleur résultat actuellement connu dans cette direction est dû à Hopcroft, Paul et Valiant.$\mathrm{P\subseteq CSL}$$\mathrm{P\subseteq DSPACE}(n^2)$ t ( n ) ϵ > 0 D T I M E ( t ( n ) ) ⊆ D S P A C E ( t ( n ) / log t ( n