Edición de «EXPSPACE»

En [[teoría de la complejidad computacional]], la clase de complejidad '''EXPSPACE''' comprende el conjunto de [[problema de decisión|problemas de decisión]] que pueden resolverse mediante una [[máquina de Turing]] determinista utilizando una cantidad de [[espacio (complejidad computacional)|espacio]] acotada por una función exponencial en el tamaño de la entrada. Formalmente, EXPSPACE incluye todos los problemas que pueden resolverse en espacio '''O'''(2<sup>''p''(''n'')</sup>), donde ''p''(''n'') es una función [[polinomio|polinomial]] sobre ''n'', el tamaño de la entrada.

De acuerdo con el [[teorema de Savitch]], esta clase es equivalente a su contraparte no determinista, lo que significa que EXPSPACE = NEXPSPACE. Esta propiedad no se cumple necesariamente en otras clases como [[P (clase de complejidad)|P]] y [[NP]].

Cuando la función polinomial ''p''(''n'') se restringe a ser lineal, es decir, del orden de ''n'', la clase resultante se denomina [[ESPACE]], que agrupa los problemas que pueden resolverse en espacio '''O'''(2<sup>''n''</sup>).

EXPSPACE contiene otras clases importantes como [[PSPACE]] y [[EXPTIME]], aunque se desconoce si estas inclusiones son estrictas.
En términos de [[DSPACE]],

:<math>\mbox{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(2^{n^k})</math>

La clase de complejidad '''EXPSPACE-completo''' es la clase de los problemas que están en EXPSPACE tales que todo problema de EXPSPACE tiene una [[transformación polinomial]] hacia cada uno de los problemas de EXPSPACE-completo. Dicho de otra forma, existe un [[algoritmo]] que trabaja en [[tiempo polinómico]] que transforma las instancias de un problema en las instancias del otro con la misma respuesta. El conjunto EXPSPACE-completo puede ser visto como el conjunto de los problemas más difíciles de EXPSPACE.

EXPSPACE contiene de forma estricta las clases [[PSPACE]], [[NP-completo]], [[NP (clase de complejidad)|NP]] y [[tiempo polinómico|P]] y se cree que también contiene estrictamente el conjunto [[EXPTIME]].

Un ejemplo de problema en EXPSPACE-completo es el de decidir si dos [[expresión regular|expresiones regulares]] representan lenguajes diferentes, cuando los operadores regulares utilizados son la unión, la concatenación, la [[clausura de Kleene]] (cero o más copias de una expresión), y el cuadrado (dos copias de una expresión). 

Si no se incluye la clausura de Kleene, el problema es [[NEXPTIME]]-completo, que es como [[EXPTIME]]-completo, salvo que se define según las máquinas de Turing no-deterministas.

En 1980, L. Berman demostró que el problema de verificar o falsificar cualquier expresión de primer orden sobre los [[número real|números reales]] que solo utiliza suma y comparación (pero no multiplicación) está en EXPSPACE.

== Referencias ==

* L. Berman ''The complexity of logical theories'', Theoretical Computer Science 11:71-78, 1980.

{{Control de autoridades}}
[[Categoría:Clases de complejidad]]