Problemas no conocidos como PSPACE-complete

¿Cuáles son los problemas con las siguientes propiedades:

1) son restricciones de problemas (posiblemente bien conocidos) que están completos en PSPACE;

2) las versiones restringidas están en PSPACE, pero es un problema abierto si son PSPACE-complete (o incluso si son NP-hard).

Cuatro ejemplos de "rompecabezas y C.":

• La complejidad de 1x1 Rush Hour [1] (PSPACE-complete para bloques de tamaño 2x1);
• [ RESUELTO ] La complejidad de Subar Shuffle plano [1] (PSPACE-complete incluso para gráficos planos, se puede descargar un borrador del documento aquí );
• La complejidad del bloqueo lunar sin bloques fijos [1] (PSPACE-complete con bloques fijos);
• (no tan famoso) La complejidad del problema (mi) Switch-network (es una restricción del Sokoban completo de PSPACE, NP-hard en el caso no plano, vea estas preguntas y respuestas en teoría ).

Si tiene muchos, agrúpelos por tema.

[1] Robert A. Hearn, Erik D. Demaine: Juegos, rompecabezas y computación. AK Peters 2009, ISBN 978-1-56881-322-6, págs. I-IX, 1-237

Ajedrez retrógrado. Es -completo si se le permite tener arbitrariamente muchos reyes y ninguno de ellos puede estar bajo control en ningún momento. Si no se permiten reyes (o solo uno por jugador), se sabe que hay posiciones que requieren movimientos exponenciales, pero solo se sabe que el problema es N P -duro.$PSPACE$$NP$

http://arxiv.org/abs/1409.1530

/mathpro/27944/do-there-exist-chess-positions-that-require-exponentially-many-moves-to-reach

No estoy seguro de si esto se ajusta a su noción de restricción, pero aquí va.

El "Problema del tamaño mínimo del circuito del oráculo QBF": dada la tabla de verdad de una función booleana y un parámetro k, ¿hay un circuito de tamaño como máximo k que calcule la función sobre la base AND, OR, NOT y QBF? (Una puerta QBF interpreta su cadena de entrada como una fórmula booleana F totalmente cuantificada, y la salida es 1 si F es verdadero).

El problema definitivamente está en PSPACE, se sabe que está completo bajo las reducciones de ZPP, pero no se sabe por reducciones de tiempo polinomiales deterministas. Probablemente no PSPACE-complete bajo reducciones de espacio de registro! Ver Allender, Holden y Kabanets .

El siguiente problema coincide con el requisito de alguna manera doble ...

$r$$r'$$L(r)\subseteq L(r')$$r$$\Sigma^*$

$L(r)=L(r')$

$r_1\cdots r_n$$r_i$$e=(w_1+\ldots+w_m)$$w_j$$e^*$$e^+$$e?$$e$$a(b+cd)(ab+cde+f)^*d?$

La contención de las expresiones regulares de la cadena aún está completa en PSPACE, pero la equivalencia de las expresiones regulares de la cadena no está clara (aunque se sabe que es coNP-hard y en PSPACE).

Por cierto, el límite superior de PSPACE se sigue fácilmente traduciendo las expresiones en NFA y buscando de forma no determinista un contraejemplo: adivine una cadena letra por letra y realice un seguimiento de los conjuntos de estados que se pueden alcanzar en los NFA.

juegos con solo 2 botones y 2 puertas en los que todas las puertas están cerradas inicialmente:

Los "niveles" son subgrafos finitos de la cuadrícula plana .$\:$ Los vértices se identifican como uno de [inicio, botón, vacío, puerta, finalización]. $\:$ Cada vértice de la puerta tiene un conjunto de botones de apertura y un conjunto de botones de cierre. $\:$ Una puerta k es una puerta que está controlada por un máximo de k botones, y un botón k es un botón que controla la mayoría de las k puertas. $\:$ Siempre que se encuentre en un vértice de botón, se puede presionar el botón, que abre las puertas para las que el botón es un botón de apertura y cierra las puertas para las que el botón es un botón de cierre. $\:$El objetivo es llegar desde el vértice inicial hasta el vértice final sin pasar por puertas cerradas.


Dichos niveles se pueden resolver claramente en FPSPACE, y resolverlos es difícil FNPSPACE
incluso cuando [cada puerta tiene exactamente un botón de apertura y exactamente un botón de cierre]
y [cada botón abre exactamente una puerta y cierra exactamente una puerta].
Por otro lado, este documento afirma que "es un problema abierto si un juego con
2 botones y 2 puertas sigue siendo PSPACE cuando todas las puertas están cerradas inicialmente".


La dureza FNPSPACE cuando todas las puertas están cerradas inicialmente se recuperará si las condiciones exactamente una de cada uno de mi párrafo anterior se modifican de alguna de las siguientes maneras:

permitir que las puertas tengan 2 botones de apertura (además de 1 botón de cierre)
o
permitir que los botones cierren 2 puertas (además de abrir 1 puerta)

.


La página 10 de este documento muestra que determinar la capacidad de solución es NC1, incluso sin botones
ni puertas.$\:$De lo contrario, no conozco ningún resultado de dureza para resolver niveles con 2 botones
y 2 puertas cuando todas las puertas están cerradas inicialmente (incluso sin las condiciones exactamente una de cada).