En la teoría de la complejidad computacional , EXPSPACE es el conjunto de todos los problemas de decisión que puede resolver una máquina de Turing determinista en un espacio exponencial , es decir, en espacio, donde es una función polinomial de . Algunos autores restringenpara 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 en su lugar, obtenemos la clase NEXPSPACE , que es igual a EXPSPACE según 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 varios uno en tiempo polinomial . En otras palabras, existe un algoritmo de tiempo polinomial que transforma las instancias de una en instancias de la otra con la misma respuesta. Los problemas de EXPSPACE-complete pueden considerarse los problemas más difíciles de EXPSPACE .
EXPSPACE es un superconjunto estricto de PSPACE , NP y P y se cree que es un superconjunto estricto de EXPTIME .
Definicion formal
En términos de DSPACE y NSPACE ,
Ejemplos de problemas
Un ejemplo de un problema de EXPSPACE completo es el problema de reconocer si dos expresiones regulares representan diferentes lenguajes, 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 cuadratura ( dos copias de una expresión). [1]
Si la estrella de Kleene se deja fuera, entonces ese 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.
También ha sido demostrado por L. Berman en 1980 que el problema de verificar / falsificar cualquier enunciado de primer orden sobre números reales que involucre solo suma y comparación (pero no multiplicación ) está en EXPSPACE .
Alur y Henzinger ampliaron la lógica temporal lineal con tiempos (números enteros) y demuestran que el problema de validez de su lógica es EXPSPACE-completo. [2]
El problema de cobertura de las redes de Petri es EXPSPACE -completo. [3] [4] Se sabía que el problema de accesibilidad para las redes de Petri era EXPSPACE, difícil durante mucho tiempo, [5] pero se demostró que no era elemental, [6] por lo que probablemente no está en EXPSPACE .
Relación con otras clases
EXPSPACE es conocido por ser un superconjunto estricto de PSPACE , NP , y P . Además, se sospecha que es un superconjunto estricto de EXPTIME , sin embargo, no se sabe.
Ver también
Referencias
- ^ Meyer, AR y L. Stockmeyer . El problema de equivalencia de expresiones regulares con cuadratura requiere espacio exponencial . 13º Simposio del IEEE sobre Teoría de la Conmutación y Autómatas , octubre de 1972, págs. 125–129.
- ^ Alur, Rajeev; Henzinger, Thomas A. (1 de enero de 1994). "Una lógica realmente temporal". J. ACM . 41 (1): 181–203. doi : 10.1145 / 174644.174651 . ISSN 0004-5411 .
- ^ Lipton, R. (1976). "El problema de la accesibilidad requiere espacio exponencial" . Informe técnico 62 . Universidad de Yale.
- ^ Charles Rackoff (1978). "Los problemas de cobertura y delimitación de los sistemas de adición de vectores". Ciencias de la computación teóricas : 223-231.
- ^ Lipton, R. (1976). "El problema de la accesibilidad requiere espacio exponencial" . Informe técnico 62 . Universidad de Yale.
- ^ Wojciech Czerwiński Sławomir Lasota Ranko S Lazić Jérôme Leroux Filip Mazowiecki (2019). "El problema de la accesibilidad de las redes de Petri no es elemental". STOC 19 .
- Berman, Leonard (1 de mayo de 1980). "La complejidad de las teorías lógicas". Informática Teórica . 11 (1): 71–77. doi : 10.1016 / 0304-3975 (80) 90037-7 .
- Michael Sipser (1997). Introducción a la Teoría de la Computación . Publicación de PWS. ISBN 0-534-94728-X.Sección 9.1.1: Completitud del espacio exponencial, págs. 313–317. Demuestra que determinar la equivalencia de expresiones regulares con exponenciación es EXPSPACE-completo.