EXPESPACIO

Conjunto de problemas de decisión

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

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, hay un algoritmo en tiempo polinomial que transforma instancias de uno en instancias del otro con la misma respuesta. Los problemas EXPSPACE-completos podrían considerarse como 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 ,

${\displaystyle {\mathsf {EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}\left(2^{n^{k}}\right)=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}\left(2^{n^{k}}\right)}$

Ejemplos de problemas

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

Alur y Henzinger extendieron la lógica temporal lineal con tiempos (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]

Se sabía desde hace mucho tiempo que el problema de accesibilidad de las redes de Petri era EXPSPACE -duro, ^{[4] pero se demostró que} no era elemental , ^[5] por lo que probablemente no estuviera en EXPSPACE . En 2022 se demostró que era Ackermann -completo. ^{[6] [7]}

Relación con otras clases

Se sabe que EXPSPACE es un superconjunto estricto de PSPACE , NP y P. También se sospecha que es un superconjunto estricto de EXPTIME , aunque esto no se sabe.

Véase también

• Complejidad del juego

Referencias

1. Meyer, AR y L. Stockmeyer . El problema de equivalencia para expresiones regulares con elevación al cuadrado requiere espacio exponencial. 13.º Simposio IEEE sobre conmutación y teoría de autómatas , octubre de 1972, págs. 125-129.
2. 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.
3. Charles Rackoff (1978). "Los problemas de cobertura y acotación para sistemas de adición vectorial". Ciencias de la computación teórica : 223–231.
4. Lipton, R. (1976). "El problema de la accesibilidad requiere espacio exponencial". Informe técnico 62. Universidad de Yale.
5. Wojciech Czerwiński Sławomir Lasota Ranko S Lazić Jérôme Leroux Filip Mazowiecki (2019). "El problema de accesibilidad de las redes de Petri no es elemental". ESTOC 19 .
6. Leroux, Jerome (febrero de 2022). "El problema de accesibilidad de las redes de Petri no es recursivo primitivo". 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) . IEEE. págs. 1241–1252. arXiv : 2104.12695 . doi :10.1109/FOCS52979.2021.00121. ISBN 978-1-6654-2055-6.
7. Brubaker, Ben (4 de diciembre de 2023). "Un problema que parece fácil produce números demasiado grandes para nuestro universo". Revista Quanta .

• Berman, Leonard (1 de mayo de 1980). "La complejidad de las teorías lógicas". Theoretical Computer Science . 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 . PWS Publishing. 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.