Quelles sont les conséquences de

On sait que $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ et $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq$ $\mathsf{polyL}$ , où $\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n)$ . Nous savons aussi que $\mathsf{polyL} \neq \mathsf{P}$parce que ce dernier a des problèmes complets dans les réductions logarithmiques d’espaces multiples, alors que ce n’est pas le cas (en raison du théorème de la hiérarchie spatiale). Afin de mieux comprendre la relation entre $\mathsf{polyL}$ et $\mathsf{P}$ , il peut être utile de comprendre d'abord la relation entre $\mathsf{L}^2$ et $\mathsf{P}$ .

Quelles sont les conséquences de $\mathsf{L}^2 \subseteq \mathsf{P}$ ?

Qu'en est- il le plus fort $\mathsf{L}^{k} \subseteq \mathsf{P}$ pour $k>2$ , ou plus faible $\mathsf{L}^{1 + \epsilon} \subseteq \mathsf{P}$ pour $\epsilon > 0$ ?

La conséquence suivante est évidente: impliquerait et donc .L ⊊ P L ≠$\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$$\mathsf{L} \subsetneq \mathsf{P}$$\mathsf{L} \neq \mathsf{P}$

Selon le théorème de la hiérarchie de l'espace, . Si alors .L 1 + ε ⊆ P L ⊊ L 1 + ε ⊆ $\forall \epsilon > 0: \mathsf{L} \subsetneq \mathsf{L}^{1+\epsilon}$$\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$$\mathsf{L} \subsetneq \mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$

$\newcommand{\DSPACE}{\mathsf{DSPACE}} \newcommand{\L}{\mathsf{L}} \newcommand{\P}{\mathsf{P}} \newcommand{\DTIME}{\mathsf{DTIME}}$

$\L^2 \subseteq \P$ réfuterait l' hypothèse du temps exponentiel .

Si un argument de remplissage . Cela signifie que le problème de satisfiabilité peut être résolu en étapes, ce qui réfute l'hypothèse du temps exponentiel.$\L^2 \subseteq \P$ $\DSPACE(n) \subseteq \DTIME(2^{O(\sqrt n)})$$\mathsf{SAT} \in \DSPACE(n)$$2^{o(n)}$

Plus généralement, pour implique .$\DSPACE(\log^{k} n) \subseteq \P$$k\geq1$$\mathsf{SAT} \in \DSPACE(n) \subseteq \DTIME(2^{O(n^{\frac{1}{k}})})$

(Cette réponse est développée à partir d'un commentaire de @MichaelWehar.)

L'isomorphisme de groupe (avec les groupes donnés sous forme de tables de multiplication) serait dans P. Lipton, Snyder et Zalcstein a montré que ce problème est dans , mais il est toujours possible de savoir s'il est dans P. La meilleure limite supérieure actuelle est -time, et comme il se réduit à un isomorphisme de graphe, il constitue un obstacle important à la mise en iso de graphes dans P.$\mathsf{L}^2$$n^{O(\log n)}$

Je me demande à quels autres problèmes naturels et importants cela pourrait s’appliquer: c’est-à-dire, en mais avec leur meilleur temps connu quasi-polynomial.$\mathsf{L}^2$

Revendication: Si pour certains , alors et .$L^k \subseteq P$$k > 2$$P \neq \log(CFL)$$P \neq NL$

Supposons que pour certains .$L^k \subseteq P$$k > 2$

D'après " Limites de la mémoire pour la reconnaissance des langages sans contexte et sensibles au contexte ", nous savons que . D'après le théorème de la hiérarchie de l'espace, nous savons que .$CFL \subseteq DSPACE(\log^2(n))$$DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n))$

Par conséquent, nous obtenons .$\log(CFL) \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$

Aussi, par le théorème de Savitch, nous savons que . Par conséquent, nous obtenons .$NL \subseteq L^2$$NL \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$