EXPSPACE-problemas completos

Actualmente estoy tratando de encontrar problemas completos de EXPSPACE (principalmente para encontrar inspiración para una reducción), y estoy sorprendido por la pequeña cantidad de resultados que se presentan.

Hasta ahora, encontré estos, y tengo problemas para expandir la lista:

• universalidad (u otras propiedades) de expresiones regulares con exponenciación.
• problemas relacionados con los sistemas de adición de vectores
• juegos no observables (ver, por ejemplo, este blog )
• algún fragmento de FO-LTL, en Sobre la complejidad computacional de fragmentos decidibles de lógicas temporales lineales de primer orden

¿Conoces otros contextos cuando la completitud de EXPSPACE aparece naturalmente?

Extendiendo el ejemplo señalado por Emil Jerabek en los comentarios, -los problemas completos surgen naturalmente en toda la geometría algebraica. Esto comenzó (creo) con el problema de membresía ideal ( Mayr-Meyer y Mayr ) y, por lo tanto, el cálculo de las bases de Gröbner. Esto se extendió luego al cálculo de las sizigias ( Bayer y Stillman ). Muchos problemas naturales en la geometría algebraica computacional terminan siendo equivalentes a uno de estos problemas. Ver también la encuesta Bayer-Mumford "¿Qué se puede calcular en geometría algebraica?"$\mathsf{EXPSPACE}$

Muchos problemas que son PSPACE-complete se convierten en EXPSPACE-complete cuando la entrada se proporciona "sucintamente", es decir, mediante alguna codificación que le permite describir entradas que normalmente serían de tamaño exponencial.

Aquí hay un ejemplo de autómatas finitos (equivalentemente, en gráficos dirigidos con bordes etiquetados): decidir si dos autómatas aceptan el mismo idioma (tienen el mismo conjunto de rutas etiquetadas desde un nodo de origen a un destino) es completo para PSPACE. Si los autómatas (gráficos) están dados por fórmulas booleanas (los nodos son valoraciones v, v ', ... y hay fórmulas booleanas que indican si va-> v' es un borde), el problema se convierte en EXPSPACE-complete. NB: hay muchas otras formas de definir sucintamente un gran gráfico / autómata, consulte, por ejemplo, este documento .

El ejemplo con expresiones regulares se ajusta a este patrón. La introducción de una notación ".. ^ 2" para el cuadrado le permite escribir expresiones compactas regulares que serían muy grandes si expandiera cada "(foo) ^ 2" por "foo foo" y "((bar) ^ 2) ^ 2 "por" bar bar bar bar ". Naturalmente, algunos problemas que son completos para PSPACE sin cuadrar se vuelven completos para EXPSPACE con el cuadrado permitido, aquí está la referencia clásica . [Nota: otros ejemplos, como las expresiones regulares con intersección o con complementos, obviamente no se ajustan al patrón de notación nueva que se expande en una entrada exponencialmente mayor en notación estándar.]

De manera similar, un problema de LOGSPACE-complete (por ejemplo, accesibilidad en gráficos dirigidos) puede convertirse en EXPSPACE-complete si su codificación sucinta permite la descripción de gráficos de tamaño doblemente exponencial.

En pocas palabras : puede encontrar fácilmente problemas nuevos, aunque quizás artificiales, con EXPSPACE completo, considerando los problemas clásicos de PSPACE o LOGSPACE (de los cuales encontrará muchos) y permitiendo una codificación compacta / sucinta / ... de la entrada.

La planificación temporal con acciones concurrentes es EXPSPACE-complete, como se muestra en

J. Rintanen, "Complejidad de la planificación temporal concurrente", Actas de la 17ª Conferencia Internacional sobre Planificación y Programación Automatizadas, págs. 280–287, 2007

$A$$O$$o=(d,P_s,P_e,P_o,E_s,E_e)$

• $d\in\mathbb{N}$
• $P_s$$P_e$$P_o$$A$
• $E_s$$E_e$$A$

$I$$G$$I$$G$

$d$

La mayoría de las clases estándar de PSPACE en adelante (bueno, incluso para NP, si lo desea) tienen algún problema de mosaico como un problema completo. Tales problemas de mosaico no están tan lejos de los problemas completos basados ​​en la máquina de Turing natural, pero a menudo son bastante convenientes como punto de partida para las reducciones. En pocas palabras, un problema de mosaico le proporciona un conjunto de mosaicos permitidos (es decir: tipos de mosaico desde los que puede usar tantos mosaicos como desee) y determina cómo se pueden combinar, a menudo mediante un conjunto H de pares de mosaicos permitidos horizontalmente mosaicos y un conjunto V de tipos verticalmente permitidos. Además, se puede proporcionar un primer mosaico y un último mosaico y, dependiendo de la versión real, y cuántas filas y / o columnas debería tener el mosaico. La pregunta algorítmica es, si existe un mosaico correcto, es decir, una asignación de posiciones a mosaicos, que obedece todas las restricciones y tiene el mosaico de inicio en la posición inferior izquierda y el último mosaico en la posición superior derecha. (Hay muchas variaciones en cuanto a las definiciones exactas).

Para la clase en cuestión, EXPSPACE, puede elegir entre (al menos) dos versiones:

• mosaico de corredor de ancho exponencial, donde se proporciona un parámetro n y la pregunta es si hay un mosaico con 2 ^ n columnas y cualquier número de filas
• juego de mosaico exp-times-exp, donde, dado n, el mosaico será de tamaño 2 ^ n multiplicado por 2 ^ n, donde el objetivo del primer jugador es alcanzar un mosaico correcto y el segundo jugador intenta evitarlo.

Los documentos a considerar para esto son - Bogdan S. Chlebus: "Domino-Tiling Games". J. Comput. Syst. Sci. 32 (3): 374-392 (1986) - Peter van Emde Boas: "La conveniencia de las inclinaciones", en: Complejidad, teoría de la lógica y la recursión, apuntes en matemáticas puras y aplicadas, vol. 187, 1997, págs. 331-363.

en Introducción a la teoría de los autómatas, los idiomas y la computación Hopcroft / Ullman Thm13.16 se da un ejemplo y prueba de que cualquier algoritmo no determinista para la teoría de primer orden de los reales con adición es NExpTime-hard. por lo tanto, presumiblemente también es NExpSpace-hard a menos que algún avance teórico demuestre que se puede resolver "en un espacio más estrecho", pero por supuesto esa pregunta es similar (¿casi idéntica?) a L =? P. (en otras palabras, todos los problemas conocidos de NExpTime-hard también son candidatos básicos para NExpSpace-hard, y si alguno no es demostrable, probablemente significaría una resolución innovadora de una separación de clase de complejidad abierta y larga). La prueba proviene de Fischer, Rabin 1974, "Complejidad súper exponencial de la aritmética de Presburger", Complejidad de la computación(R. Karp ed.). Actas del Simposio SIAM-AMS en Matemática Aplicada.