Eine Sprache in NSPACE (O (n)) und sehr wahrscheinlich nicht in DSPACE (O (n))

Tatsächlich habe ich festgestellt, dass die Menge der kontextsensitiven Sprachen ( akzeptierte Sprachen) nicht so häufig diskutiert wird wie (reguläre Sprachen). oder (kontextfreie Sprachen). Und auch das offene Problem ist nicht so berühmt wie das "analoge" Problem: " ".$\mathbf{CSL}$$\mathbf{=NSPACE(O(n)) = LBA}$$\mathbf{REG}$$\mathbf{CFL}$$\mathbf{DSPACE(O(n))} =^{?} \mathbf{NSPACE(O(n))}$$\mathbf{P} =^{?} \mathbf{NP}$

Gibt es wirklich eine solche Analogie?

1. Gibt es eine Sprache in die nicht in (wie vollständige Sprachen in )?D S P A C E ( O ( n ) ) N $\mathbf{CSL}$$\mathbf{DSPACE(O(n))}$$\mathbf{NP}$
2. Außerdem: Gibt es eine Sprache in die im folgenden Sinne "vollständig" ist: Wenn wir beweisen können, dass in wir diese ?C S L L D S P A C E ( O ( n ) ) D S P A C E ( O ( n ) ) = N S P A C E ( O ( n ) $L$$\mathbf{CSL}$$L$$\mathbf{DSPACE(O(n))}$$\mathbf{DSPACE(O(n)) = NSPACE(O(n))}$
3. (Vielleicht nur eine Ansichtssache) Sind beide Probleme auf dem gleichen Schwierigkeitsgrad?

Die bekanntere Version dieser Fragen ist die Frage . Wenn dann zeigt ein (etwas kniffliges) , dass und damit impliziert die bekannte Vermutung .L = N L D S P A C E ( n ) = N S P A C E ( n ) D S P A C E ( n ) ≠ N S P A C E ( n ) L ≠ N $\mathsf{L} \stackrel?= \mathsf{NL}$$\mathsf{L} = \mathsf{NL}$$\mathsf{DSPACE}(n) = \mathsf{NSPACE}(n)$$\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$$\mathsf{L} \neq \mathsf{NL}$

Die Vermutung wird (von einigen) als als die Vermutung . Ich bin nicht sicher, ob viele Leute eine Meinung zu der Vermutung .P ≠ N P D S P A C E ( n ) ≠ N S P A C E ( n $\mathsf{L} \neq \mathsf{NL}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$

Das größere Bild hier ist, ob der Satz von Savitch , der besagt, dass für vernünftiges , ist eng. Während , denke ich, dass die meisten Leute glauben, dass . Andererseits bin ich mir nicht sicher, ob die Leute glauben, dass die optimale Explosion ist; Vielleicht funktioniert auch ein kleinerer Exponent, zumindest in einigen Fällen. Siehe zum Beispiel ein kürzlich veröffentlichtes arXiv-Papier , Die parametrisierte Raumkomplexität der Modellprüfung begrenzter variabler Logik erster Ordnung , von Yijia Chen, Michael Elberfeld und Moritz Müller.t ( n ) ≥ log n N P S P A C E = P S P A C E N S P. A C E ( n k ) ≠ D S $\mathsf{NSPACE}(t(n)) \subseteq \mathsf{DSPACE}(t(n)^2)$$t(n) \geq \log n$$\mathsf{NPSPACE} = \mathsf{PSPACE}$$\mathsf{NSPACE}(n^k) \neq \mathsf{DSPACE}(n^k)$$t(n)^2$

1. Ja, es gibt vollständige CSL- Sprachen unter DSPACE (O (n)) -Reduktionen. Grundsätzlich noch eine Variante der gerichteten Erreichbarkeit, die auf Wunsch auf die azyklische Erreichbarkeit beschränkt werden kann.
2. Ja, siehe 1.

3. Sie meinen, ist die Frage DSPACE (O (n)) = ^? NSPACE (O (n)) auf dem gleichen Schwierigkeitsgrad wie die Frage P = ^? NP ? Nun, wir haben gute Gründe zu glauben, dass P eine strenge Teilmenge von NP ist , aber mir sind keine ähnlich gut ausgearbeiteten Gründe bekannt, um zu glauben, dass DSPACE (O (n)) eine strenge Teilmenge von NSPACE (O (n)) ist. . Lassen Sie mich auf die einfachere Frage . Zufällige Spaziergänge sind "nicht schlecht", um (in Bezug auf die Erreichbarkeit) die mit SL verbundenen ungerichteten Graphen zu erkunden$\mathsf{L} \stackrel?= \mathsf{NL}$. Der offensichtliche triviale analoge Zufallslauf auf einem gerichteten Graphen schlägt beim Erkunden eines gerichteten Graphen (in Bezug auf die Erreichbarkeit) schlecht fehl. Aber vielleicht gibt es andere ähnliche zufällige Möglichkeiten, um einen gerichteten Graphen (oder einen geschichteten azyklischen Graphen) zu untersuchen. Basierend auf dem Satz von Savitch würde ich sogar vermuten, dass es solche Möglichkeiten gibt, wenn wir bereit sind, während des zufälligen Explorationsprozesses einen sich ändernden Satz von -Positionen innerhalb des gerichteten Graphen zu speichern . Und dann wäre die Herausforderung zu verstehen, ob das Speichern von weniger als O ( log n ) -Positionen keine gute randomisierte Exploration ermöglicht.$O(\log n)$$O(\log n)$

   Auch nach dem, ob das Verständnis sollten wir glauben , erweist es wahrscheinlich ebenso unmöglich sein wird , als Beweis P ≠ N P . Ryan Williams gibt einen expliziten Grund an und sagt:$\mathsf{L} \neq \mathsf{NL}$$\mathsf{P} \neq \mathsf{NP}$

   Darüber hinaus kenne ich keinen besonderen Grund zu der Annahme, dass es "schwer zu beweisen" ist, außer der Beobachtung, dass viele Menschen es versucht haben und noch keiner erfolgreich war.

   zu beantworten Ist ALogTime! = PH schwer zu beweisen (und unbekannt)? Lance Fortnow sprach die Frage grundsätzlich an und ist immer noch anderer Meinung. Meine eigene Lektion war:

   Dies bedeutet, dass die Aussage "ALogTime! = PH" genau der Ort ist, an dem die Schwierigkeiten zum Nachweis der Trennungsergebnisse beginnen. Es kann angemerkt werden, dass diese Aussage tatsächlich "ALogTime! = NP" entspricht, da "ALogTime = NP" "P = NP = PH" implizieren würde.

Zusätzlich zu den anderen Antworten gibt es einen Begriff der Reduzierbarkeit und Vollständigkeit für das CSL- vs. DCSL-Problem, nämlich die Log-Lin-Reduzierbarkeit, und es gibt ganz natürliche CSL-vollständige Probleme. Zum Beispiel das Ungleichwertigkeitsproblem für reguläre Ausdrücke. Hier ist eine sehr ähnliche Frage wie Ihre, zusammen mit einer Antwort, die weitere Hintergrundinformationen und Verweise enthält: /cstheory/1905/completeness-and-context-sensitive-languages

$SAT$ ist in$NTIME(n) \subseteq DSPACE(n)$ . Unter der Annahme von$L = P$ ist$NP$ streng in$DSPACE(n)$ da wir Polynomzeitreduktionen in logarithmische Raumreduktionen und D S P A C E ( n ) umwandeln können.$DSPACE(n)$wird unter logarithmischen Raumverkleinerungen geschlossen. Sie sind aufgrund des Hierarchiesatzes nicht gleich. Wenn jedoch $L = NL$ dann ist $DSPACE(n) = NSPACE(n)$ als Ergebnis der Anwendung des Füllarguments. Da $L = NL$ wenn $L = P$ dann ist $NP$ streng in $NSPACE(n)$. Jedoch $CSL = NSPACE(n)$ und damit $CSL \neq NP$ und somit könnte es nicht der Fall sein , dass einige $CSL-complete$ Problem ist $NP$ weil dies einen Widerspruch zu $CSL \neq NP$ implizieren würde , den wir erhalten haben, nachdem wir $L = P$ .

Außerdem konnten Sie hier einen möglichen Versuch sehen, $L = P$ beweisen :

https://hal.archives-ouvertes.fr/hal-01999029