Welche Beziehung besteht zwischen den Sprachen P (PTime) und Typ 1 (kontextsensitiv)?

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

• $P$ ist die Menge aller Sprachen, die in der Polynomzeit auf einer deterministischen Turing-Maschine entscheidbar sind, und
• $CSL$ ist die Klasse der kontextsensitiven Sprachen, die bekanntermaßen , den Sprachen, die von linear begrenzten Automaten bestimmt werden.$NSPACE(O(n))$

Bei vielen offenen Fragen besteht die Tendenz zu einer Antwort ( a la "die meisten Experten glauben, dass "). Gibt es so etwas für diese Frage?$P\neq NP$

Hätte eine der Antworten insbesondere unerwartete Konsequenzen? Ich kann nur erwartete (aber unbewiesene) Konsequenzen sehen:

• Wenn , dann (Satz der ), daher .$P\subseteq CSL$$P\subseteq NSPACE(O(n))\subsetneq NSPACE(O(n^2))$$P\subsetneq PSpace$
• Wenn , dann gibt es eine Sprache und somit , daher .$P\not\subseteq CSL$$l\in P\setminus NSPACE(O(n))$$l\in P\setminus NL$$NL\subsetneq P$

(Anerkennung: Die zweite Konsequenz dieser beiden wurde von Yuval Filmus unter /cs/69614/ hervorgehoben. )

Wenn , dann . Durch ein Auffüllargument impliziert dies für jede superpolynomische gut verhaltene Funktion und jedes . Ich glaube, dass ein so starker Vorteil des Raums gegenüber der Zeit nicht wahr sein dürfte. Das derzeit bekannteste Ergebnis in dieser Richtung ist aufgrund von Hopcroft, Paul und Valiant .$\mathrm{P\subseteq CSL}$$\mathrm{P\subseteq DSPACE}(n^2)$