¿Cuáles son las consecuencias de

Sabemos que $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ y que $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq$ $\mathsf{polyL}$ , donde $\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n)$ . También sabemos que $\mathsf{polyL} \neq \mathsf{P}$porque el último tiene problemas completos bajo el espacio logarítmico reducciones de muchos uno mientras que el primero no (debido al teorema de la jerarquía del espacio). Con el fin de comprender la relación entre $\mathsf{polyL}$ y $\mathsf{P}$ , que puede ayudar a entender primero la relación entre $\mathsf{L}^2$ y $\mathsf{P}$ .

¿Cuáles son las consecuencias de $\mathsf{L}^2 \subseteq \mathsf{P}$ ?

¿Qué pasa con el más fuerte $\mathsf{L}^{k} \subseteq \mathsf{P}$ para $k>2$ , o el más débil $\mathsf{L}^{1 + \epsilon} \subseteq \mathsf{P}$ para $\epsilon > 0$ ?

La siguiente es una consecuencia obvia: implicaría y, por lo tanto, .L ⊊ P L ≠$\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$$\mathsf{L} \subsetneq \mathsf{P}$$\mathsf{L} \neq \mathsf{P}$

Según el teorema de la jerarquía espacial, . Si entonces .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$ refutaría la hipótesis del tiempo exponencial .

Si entonces mediante un argumento de relleno . Esto significa que el problema de satisfacción se puede decidir en pasos, refutando la hipótesis del tiempo exponencial.$\L^2 \subseteq \P$ $\DSPACE(n) \subseteq \DTIME(2^{O(\sqrt n)})$$\mathsf{SAT} \in \DSPACE(n)$$2^{o(n)}$

Más generalmente, para implica .$\DSPACE(\log^{k} n) \subseteq \P$$k\geq1$$\mathsf{SAT} \in \DSPACE(n) \subseteq \DTIME(2^{O(n^{\frac{1}{k}})})$

(Esta respuesta se expande a partir de un comentario de @MichaelWehar).

El isomorfismo grupal (con grupos dados como tablas de multiplicación) estaría en P. Lipton, Snyder y Zalcstein mostraron que este problema está en , pero aún está abierto si está en P. El mejor límite superior actual es tiempo, y debido a que se reduce al isomorfismo gráfico, se erige como un obstáculo significativo para poner la iso del gráfico en P.$\mathsf{L}^2$$n^{O(\log n)}$

Me hace preguntarme a qué otros problemas naturales e importantes se aplicaría esto: es decir, en pero con su cuasi-polinomio de límite superior de tiempo más conocido.$\mathsf{L}^2$

Reclamación: si para algunos , entonces y .$L^k \subseteq P$$k > 2$$P \neq \log(CFL)$$P \neq NL$

Supongamos que para algunos .$L^k \subseteq P$$k > 2$

Desde " Límites de memoria para el reconocimiento de lenguajes sin contexto y sensibles al contexto ", sabemos que . Por el teorema de la jerarquía espacial, sabemos que .$CFL \subseteq DSPACE(\log^2(n))$$DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n))$

Por lo tanto, obtenemos .$\log(CFL) \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$

Además, según el Teorema de Savitch, sabemos que . Por lo tanto, obtenemos .$NL \subseteq L^2$$NL \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$