Relación entre ESPACIO (n) y E

¿Se sabe si SPACE (n) (la clase de lenguajes reconocidos por TM deterministas con espacio lineal) es un subconjunto apropiado de E (la clase de lenguajes reconocidos por TM deterministas en el tiempo 2 ^ O (n))?

Si, de hecho, DSPACE (n) = E, un argumento de relleno traduciría esto a PSPACE = EXP. De manera similar, si DSPACE (n) E entonces un argumento de relleno traduciría esto a L P.$\neq$$\neq$

Nota antes de leer

La siguiente prueba es errónea, como se señala en un comentario a continuación de Robin Kothari. Estoy agradecido con él por aclarar el punto. Sin embargo, no eliminé esta respuesta, ya que creo que es instructivo tener en cuenta tal falla.

Creo que la parte "adecuada" se puede probar utilizando teoremas de jerarquía de tiempo y espacio. (Ver secciones 7.2 y 7.3 de la Complejidad Computacional de Papadimitriou ).

Para una función construible en el tiempo y en el espacio tenemos:$f(n) \ge n$

$DSPACE(f(n)) \subseteq NSPACE(f(n))$

$\exists k \quad NSPACE(f(n)) \subseteq DTIME(k^{\log n + f(n)})$

$DTIME(f(n)) \subset DTIME(f(n)\log^2 f(n))$

( denota el subconjunto adecuado ).$\subset$

Por lo tanto, para la función lineal , existe una tal que:$f(n)=n$$k$

$DSPACE(n) \subseteq DTIME(k^{\log n + n}) \subseteq DTIME(k^{2n}) \subset DTIME((k^{2n})(\log^2 (k^{2n})))$

El lado derecho es un subconjunto apropiado de E.

El complejo zoológico informa que E no es igual a PSPACE, citando el artículo Comparando clases de complejidad de Ronald V. Book.

Las siguientes oraciones pueden derivarse fácilmente:

SPACE (n) es un subconjunto apropiado de PSPACE. (1) La
unión E de PSPACE no está vacía. (2)

SI en lugar de E tuviéramos EXPTIME, sería fácil deducir que SPACE (n) es un subconjunto adecuado de EXPTIME, debido a (1) y que PSPACE es un subconjunto de EXPTIME.

Para E, la relación entre PSPACE y E no está clara para mí:

1) ¿E está contenido en PSPACE?

De lo contrario, se deduce que ESPACIO (n) es un subconjunto adecuado de E. Para verificar esto, se debe crear un problema que use más que un espacio lineal y menos que el tiempo O (2 ⁿ ).

2) ¿El PSPACE está contenido en E?

Creo que esto es aún más difícil de responder que la pregunta anterior.