En

Sabemos que . Del teorema de Savitch, , y, del Teorema de la jerarquía espacial, . Entonces, como no sabemos si , no sabemos si , o sabemos que ? ¿Alguien ha intentado demostrar que \ mathcal L ^ 2 \ subseteq \ mathcal P ? ¿Cuáles son los últimos resultados o esfuerzos de esta manera? He estado tratando de escribir una encuesta sobre este tema, pero no he encontrado nada relevante.$\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}$$\mathcal{N\!L}\subseteq\mathcal{L}^2$$\mathcal{L}\neq\mathcal{L}^2$$\mathcal L\neq\mathcal P$$\mathcal L^2\subseteq\mathcal P$$\mathcal L^2\not\subseteq\mathcal P$$\mathcal L^2\subseteq\mathcal P$

Además, si existe o no un problema $\mathcal{N\!P}$ que no es $\mathcal{N\!P}$ -completo es una pregunta abierta, y tal existencia implicaría $\mathcal L\neq\mathcal{N\!P}$ , como cada $\mathcal L$ problema es completo para $\mathcal L$ . ¿Pero realmente no sabemos que $\mathcal L\neq\mathcal{N\!P}$ ? ¿Alguien ha estado tratando de probar esto? De nuevo, ¿cuáles son los últimos resultados o esfuerzos de esta manera?

Tal vez me estoy perdiendo algo o estoy buscando mal, pero no pude encontrar a nadie trabajando en las preguntas $\mathcal L^2\subseteq \mathcal P$ y $\mathcal L\neq\mathcal{N\!P}$ .

Puede consultar el siguiente documento:

Lemas traslacionales, tiempo polinómico y -space$(\log n)^j$ por Ronald V. Book (1976).

Las figuras 1 y 2 en el documento dan el resumen de lo que se sabe y lo que se desconoce.

Puse el Teorema 3.10 en el documento aquí:

• $DTIME(poly(n)) \neq DSPACE(poly(\log n))$ ;
• para cada , ;$j \geq 1$$DTIME(n^j) \neq DSPACE(poly(\log n))$
• para cada , .D T I M E ( n j ) ≠ D S P A C E ( ( log n ) k$j,k \geq 1$$DTIME(n^j) \neq DSPACE( (\log n)^k )$