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

10

PCSLPCSL

  • 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?PNP

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

  • Wenn , dann (Satz der ), daher .PCSLPNSPACE(O(n))NSPACE(O(n2))PPSpace
  • Wenn , dann gibt es eine Sprache und somit , daher .PCSLlPNSPACE(O(n))lPNLNLP

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

mak
quelle

Antworten:

12

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 .PCSLPDSPACE(n2)

DTIME(t(n))DSPACE(t(n)ϵ)
t(n)ϵ>0
DTIME(t(n))DSPACE(t(n)/logt(n)),
Emil Jeřábek
quelle
Vielen Dank, ich habe diese Antwort jetzt akzeptiert, obwohl angesichts der Art dieser Frage weitere Antworten natürlich immer noch willkommen wären.
mak