Jerarquía de clases de complejidad acotadas por espacio

En teoría de la complejidad computacional se utilizan diferentes clases de complejidad para catalogar familias de problemas de decisión en relación con la cantidad de espacio que utilizan para ser resueltos. Estas clases de complejidad pueden ser organizadas en una jerarquía de clases de complejidad acotadas por espacio.

Sea una función $S:\mathbb {N} \rightarrow \mathbb {N}$, la clase de complejidad DSPACE(S(n)) (respectivamente NSPACE(S(n))) está formada por los problemas que pueden ser resueltos en una máquina de Turing determinista (resp. no determinista) utilizando a lo sumo S(n) casillas además de la entrada, para una entrada de longitud n.

Por ejemplo, las clases de complejidad L y NL reciben también los nombres DSPACE(log(n)) y NSPACE(log(n)), respectivamente.

Características

A medida que las clases de complejidad se acotan en espacio por funciones más complejas se obtienen conjuntos de problemas incluidos propiamente:

Si S₁ y S₂ son funciones de espacio constructivo, S₁(n)=Ω(S₂(n)) y S₂(n)=Ω(log(n)) entonces existe al menos un lenguaje en DSPACE(S₁(n)) que no está en DSPACE(S₂(n)). Esta propiedad se demuestra aplicando un argumento de diagonalización.

El Teorema de Savitch permite establecer una relación entre clases basadas en máquinas de Turing deterministas y no deterministas:

Cuando S es una función de espacio completamente constructivo, NSPACE(S(n)) ⊆ DSPACE(S²(n)).

La relación de contención en la jerarquía no determinista de clases acotadas por espacio puede ser trasladada con una función de espacio:

Si S₁, S₂ y f son funciones de espacio completamente constructivo tales que S₁=Ω(n), f==Ω(n), y

NSPACE(S₁(n)) ⊆ NSPACE(S₂(n)),

entonces

NSPACE(S₁(f(n))) ⊆ NSPACE(S₂(f(n))).

• Datos: Q5929281