Une langue dans NSPACE (O (n)) et très probablement pas dans DSPACE (O (n))

En fait, j'ai trouvé que l'ensemble des langues contextuelles, $\mathbf{CSL}$ ( $\mathbf{=NSPACE(O(n)) = LBA}$ langues acceptées) ne sont pas aussi largement discutées que $\mathbf{REG}$ (langues régulières) ou $\mathbf{CFL}$ (langues sans contexte). Et aussi le problème ouvert $\mathbf{DSPACE(O(n))} =^{?} \mathbf{NSPACE(O(n))}$ n'est pas aussi célèbre que le problème "analogue": "$\mathbf{P} =^{?} \mathbf{NP}$ ".

Eh bien, y a-t-il vraiment une telle analogie:?

1. Existe-t-il une langue en $\mathbf{CSL}$ qui ne puisse pas être prouvée en $\mathbf{DSPACE(O(n))}$ (comme $\mathbf{NP}$ langues complètes)?
2. De plus: existe-t-il un langage $L$ en $\mathbf{CSL}$ qui est "complet" dans le sens suivant: si l'on peut prouver que $L$ est en $\mathbf{DSPACE(O(n))}$ on obtient que $\mathbf{DSPACE(O(n)) = NSPACE(O(n))}$ ?
3. (Peut-être juste une question d'opinion) Les deux problèmes sont-ils au même niveau de difficulté?

La version la plus connue de ces questions est le question. Si L = N L, un argument de remplissage (légèrement délicat) montre que D S P A C E ( n ) = N S P A C E ( n ) , et donc D S P A C E ( n ) ≠ N S P A C E ( n $\mathsf{L} \stackrel?= \mathsf{NL}$$\mathsf{L} = \mathsf{NL}$$\mathsf{DSPACE}(n) = \mathsf{NSPACE}(n)$$\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$implique la conjecture bien connue .$\mathsf{L} \neq \mathsf{NL}$

La conjecture est considéré (par certains) pour être plus accessible que la conjecture P ≠ N P . Je ne suis pas sûr que beaucoup de gens aient une opinion sur la conjecture 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)$

La plus grande image ici est de savoir si le théorème de Savitch , qui déclare que pour t ( n ) ≥ log n raisonnable , est serré . Alors que N P S P A C E = P S P A C $\mathsf{NSPACE}(t(n)) \subseteq \mathsf{DSPACE}(t(n)^2)$$t(n) \geq \log n$$\mathsf{NPSPACE} = \mathsf{PSPACE}$, Je pense que la plupart des gens croient que . D'un autre côté, je ne suis pas sûr que les gens croient que t ( n ) 2 est l'explosion optimale; peut-être qu'un exposant plus petit fonctionne également, du moins dans certains cas. Voir par exemple un article arXiv récent , La complexité de l'espace paramétré de la logique de premier ordre à variable bornée de vérification de modèle , par Yijia Chen, Michael Elberfeld et Moritz Müller.$\mathsf{NSPACE}(n^k) \neq \mathsf{DSPACE}(n^k)$$t(n)^2$

1. Oui, il existe des langues complètes CSL sous les réductions DSPACE (O (n)) . Fondamentalement, il s'agit toujours d'une variante d'accessibilité dirigée, qui peut être limitée à l'accessibilité acyclique si vous le souhaitez.
2. Oui, voir 1.

3. Vous voulez dire, la question DSPACE (O (n)) = ^? NSPACE (O (n)) au même niveau de difficulté que la question P = ^? NP ? Eh bien, nous avons de bonnes raisons de croire que P est un sous-ensemble strict de NP , mais je ne connais pas de raisons tout aussi bien établies de croire que DSPACE (O (n)) est un sous-ensemble strict de NSPACE (O (n)) . Permettez-moi de me concentrer sur la question plus facile . Les promenades aléatoires ne sont "pas mauvaises" pour explorer (en ce qui concerne l'accessibilité) les graphiques non orientés associés à SL$\mathsf{L} \stackrel?= \mathsf{NL}$. La marche aléatoire analogue, triviale et évidente, sur un graphe dirigé échouera gravement à l'exploration d'un graphe dirigé (en ce qui concerne l'accessibilité). Mais il existe peut-être d'autres façons aléatoires similaires d'explorer un graphe orienté (ou un graphe acyclique en couches). Sur la base du théorème de Savitch, je suppose même qu'il existe de telles façons, si nous sommes prêts à enregistrer un ensemble changeant de positions dans le graphe orienté pendant le processus d'exploration aléatoire. Et le défi serait alors de comprendre si la sauvegarde de moins de O ( log n ) positions ne permettra pas une bonne exploration aléatoire.$O(\log n)$$O(\log n)$

   Même après avoir compris que nous croyions , prouvant qu'il sera probablement tout aussi impossible que prouver P ≠ N P . Ryan Williams donne une raison explicite et dit:$\mathsf{L} \neq \mathsf{NL}$$\mathsf{P} \neq \mathsf{NP}$

   Au-delà de cela, je ne connais aucune raison particulière de croire qu'il est "difficile à prouver" autre que l'observation que beaucoup de gens ont essayé et aucun n'a encore réussi.

   répondre ALogTime! = PH est-il difficile à prouver (et inconnu)? Lance Fortnow a essentiellement soulevé la question et n'est toujours pas d'accord. Ma propre leçon a été:

   Cela signifie que l'instruction "ALogTime! = PH" est exactement l'endroit où les difficultés pour prouver les résultats de séparation commencent. Il peut être noté que cette déclaration est en fait équivalente à "ALogTime! = NP", car "ALogTime = NP" impliquerait "P = NP = PH".

En plus des autres réponses, il existe une notion de réductibilité et d'exhaustivité pour le problème CSL vs DCSL, à savoir la réductibilité log-lin, et il existe des problèmes tout à fait naturels CSL-complete. Par exemple, le problème d'inéquivalence pour les expressions régulières. Voici une question très similaire à la vôtre, ainsi qu'une réponse fournissant des informations supplémentaires et des références: /cstheory/1905/completeness-and-context-sensitive-languages

$SAT$$NTIME(n) \subseteq DSPACE(n)$$L = P$$NP$$DSPACE(n)$$DSPACE(n)$$L = NL$$DSPACE(n) = NSPACE(n)$$L = NL$$L = P$$NP$$NSPACE(n)$. However, $CSL = NSPACE(n)$ and thus $CSL \neq NP$ and hence, there could not be the case that some $CSL-complete$ problem is in $NP$ because that would imply a contradiction with $CSL \neq NP$ that we obtained after assuming $L = P$.

In addition, you could see a possible attempt of proving $L = P$ here:

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