ESPACIO DE EXPERIENCIA

En la teoría de la complejidad computacional, EXPSPACE es el conjunto de todos los problemas de decisión solvable por una máquina de Turing determinista en espacio exponencial, es decir, en O()2p()n)){displaystyle O(2^{p(n)}} espacio, donde p()n){displaystyle p(n)} es una función polinómica de n{displaystyle n}. Algunos autores restringen p()n){displaystyle p(n)} para ser una función lineal, pero la mayoría de los autores llaman a la clase resultante ESPACE. Si usamos una máquina no determinista, obtenemos la clase NEXPSPACE, que es igual a EXPSPACE por el teorema de Savitch.

Un problema de decisión es EXPSPACE-completo si está en EXPSPACE, y cada problema en EXPSPACE tiene una reducción de muchos a uno en tiempo polinomial. En otras palabras, existe un algoritmo de tiempo polinomial que transforma instancias de uno en instancias del otro con la misma respuesta. Los problemas EXPSPACE-complete pueden considerarse los problemas más difíciles en EXPSPACE.

EXPSPACE es un superconjunto estricto de PSPACE, NP y P y se cree que es un superconjunto estricto de EXPTIME.

Definición formal

En términos de DSPACE y NSPACE,

EXPSPACE=⋃ ⋃ k▪ ▪ NDSPACE()2nk)=⋃ ⋃ k▪ ▪ NNSPACE()2nk){displaystyle {mathsf {fnMicrosoft}=bigcup _{kin mathbb {N}{mthsf {DSPACE}left(2^{n^{k}right)=bigcup _{kin mathbb {N}{mathsf {NSPACE}left(2^{n^{k}right)}

Ejemplos de problemas

Un ejemplo de un problema de EXPSPACE-complete es el problema de reconocer si dos expresiones regulares representan diferentes idiomas, donde las expresiones están limitadas a cuatro operadores: unión, concatenación, la estrella de Kleene (cero o más copias de una expresión) y el cuadrado (dos copias de una expresión).

Si se omite la estrella Kleene, el problema se convierte en NEXPTIME-complete, que es como EXPTIME-complete, excepto que se define en términos de máquinas de Turing no deterministas en lugar de deterministas.

L. Berman también demostró en 1980 que el problema de verificar/falsificar cualquier afirmación de primer orden sobre números reales que involucre solo sumas y comparaciones (pero no multiplicaciones) está en EXPESPACIO.

Alur y Henzinger extendieron la lógica temporal lineal con tiempos (entero) y probaron que el problema de validez de su lógica es EXPSPACE-completo.

El problema de cobertura de Petri Nets es EXPSPACE-completo. Se sabía que el problema de accesibilidad de las redes de Petri era EXPSPACE-difícil durante mucho tiempo, pero se demostró que no era elemental, por lo que es probable que no EXPSPACE.

Relación con otras clases

EXPSPACE es un superconjunto estricto de PSPACE, NP y P. Además, se sospecha que es un superconjunto estricto de EXPTIME, sin embargo, esto no se sabe.