Lista de problemas de PSPACE-complete

A continuación se enumeran algunos de los problemas más conocidos que son PSPACE-completos cuando se expresan como problemas de decisión . Esta lista no es exhaustiva.

Juegos y rompecabezas

Versiones generalizadas de:

• Amazonas ^[1]
• Átomo ^[2]
• Damas si se fuerza un empate después de un número polinómico de movimientos que no sean de salto ^[3]
• Juego del telescopio Dyson ^[4]
• Propósitos cruzados ^[5]
• Geografía
• Versión de juego para dos jugadores de Instant Insanity
• Go libre de Ko ^[6]
• Captura de escalera en Go ^[7]
• Gomoku ^[8]
• Hexágono ^[9]
• Cono ^[5]
• Lemmings ^[10]
• Nodo Kayles ^[11]
• Juego Poset ^[12]
• Reversión ^[13]
• Cruce del río ^[14]
• Hora punta ^[14]
• Cómo encontrar el juego óptimo en el solitario Mahjong ^[15]
• Scrabble ^[16]
• Sokoban ^[14]
• Super Mario Bros. ^[17]
• Juego de piedra negra ^[18]
• Juego de piedras blancas y negras ^[19]
• Juego de piedras acíclico ^[20]
• Juego de piedras para un jugador ^[20]
• Ficha sobre juegos de gráficos dirigidos acíclicos : ^[11]

Lógica

• Fórmulas booleanas cuantificadas
• Lógica de primer orden de la igualdad ^[21]
• Probabilidad en lógica proposicional intuicionista
• Satisfacción en lógica modal S4 ^[21]
• Teoría de primer orden de los números naturales bajo la operación sucesora ^[21]
• Teoría de primer orden de los números naturales bajo el orden estándar ^[21]
• Teoría de primer orden de los números enteros bajo el orden estándar ^[21]
• Teoría de primer orden de conjuntos bien ordenados ^[21]
• Teoría de primer orden de cadenas binarias bajo ordenamiento lexicográfico ^[21]
• Teoría de primer orden de un álgebra booleana finita ^[21]
• Satisfacción estocástica ^[22]
• Satisfacción de la lógica temporal lineal y verificación de modelos ^[23]

Cálculo lambda

Problema de habitabilidad de tipos para cálculo lambda de tipos simples

Autómatas y teoría del lenguaje

Teoría de circuitos

Evaluación de circuitos enteros ^[24]

Teoría de autómatas

• Problema verbal para autómatas lineales acotados ^[25]
• Problema verbal para autómatas cuasi-en tiempo real ^[26]
• Problema de vacío para un autómata de estados finitos bidireccional no determinista ^{[27] [28]}
• Problema de equivalencia para autómatas finitos no deterministas ^{[29] [30]}
• Problema de palabras y problema de vacío para autómatas de pila que no borran ^[31]
• Vacío de intersección de un número ilimitado de autómatas finitos deterministas ^[32]
• Una versión generalizada de la hormiga de Langton ^[33]
• Minimización de autómatas finitos no deterministas ^[34]

Lenguajes formales

• Problema de palabras para lenguaje sensible al contexto ^[35]
• Vacío de intersección para un número ilimitado de lenguajes regulares ^[32]
• Expresión regular sin asteriscos ^[36]
• Problema de equivalencia para expresiones regulares ^[21]
• Problema de vacío para expresiones regulares con intersección. ^[21]
• Problema de equivalencia para expresiones regulares sin estrellas con cuadrado. ^[21]
• Cobertura para gramáticas lineales ^[37]
• Equivalencia estructural para gramáticas lineales ^[38]
• Problema de equivalencia para gramáticas regulares ^[39]
• Problema de vacío para gramáticas ET0L ^[40]
• Problema de palabras para gramáticas ET0L ^[41]
• Problema de pertenencia al lenguaje del transductor de árbol para transductores de árbol de estados finitos de arriba hacia abajo ^[42]

Teoría de grafos

• Versiones sucintas de muchos problemas de gráficos, con gráficos representados como circuitos booleanos, ^[43] diagramas de decisión binaria ordenados ^[44] u otras representaciones relacionadas:
  • Problema de accesibilidad para gráficos sucintos. Es básicamente el mismo que el problema de existencia de plan más simple en la planificación y programación automatizadas .
  • planaridad de grafos sucintos
  • aciclicidad de grafos sucintos
  • Conectividad de gráficos sucintos
  • Existencia de caminos eulerianos en un grafo sucinto
• Lógica de restricción limitada para dos jugadores ^[11]
• Problema del viajero canadiense . ^[45]
• Determinar si las rutas seleccionadas por el Protocolo de Puerta de Enlace Fronteriza eventualmente convergerán a un estado estable para un conjunto dado de preferencias de ruta ^[46]
• Lógica de restricción determinista (ilimitada) ^[47]
• Fiabilidad de gráficos dinámicos. ^[22]
• Juego de colorear gráficos ^[48]
• Juego de Kayles de nodos y juego de formación de camarillas : ^[49] dos jugadores seleccionan vértices de forma alternada y el subgrafo inducido debe ser un conjunto independiente (o camarilla). El último en jugar gana.
• Lógica de restricciones no determinista (ilimitada) ^[11]

Otros

• POMDP de horizonte finito (procesos de decisión de Markov parcialmente observables). ^[50]
• Modelos ocultos de múltiples dispositivos (hmMDP). ^[51]
• Proceso dinámico de Markov. ^[22]
• Detección de dependencias de inclusión en una base de datos relacional ^[52]
• Cálculo de cualquier equilibrio de Nash de un juego de forma normal de dos jugadores , que puede obtenerse mediante el algoritmo de Lemke-Howson . ^[53]
• El problema de la disposición de mosaicos en el corredor: dado un conjunto de mosaicos Wang , un mosaico elegido y un ancho dado en notación unaria, ¿existe alguna altura tal que un rectángulo pueda ser dispuesto en mosaicos de tal manera que todos los mosaicos del borde sean ? ^{[54] [55]} ${\displaystyle T_{0}}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n\times m}$ ${\displaystyle T_{0}}$

Véase también

• Lista de problemas NP-completos

Notas

1. RA Hearn (2 de febrero de 2005). "Amazons es PSPACE-completo". arXiv : cs.CC/0502013 .
2. Markus Holzer y Stefan Schwoon (febrero de 2004). "Ensamblar moléculas en ATOMIX es difícil". Ciencias Informáticas Teóricas . 313 (3): 447–462. doi : 10.1016/j.tcs.2002.11.002 .
3. Aviezri S. Fraenkel (1978). "La complejidad de las damas en un tablero N x N - informe preliminar". Actas del 19.º Simposio Anual sobre Ciencias de la Computación : 55–64.
4. Erik D. Demaine (2009). La complejidad del rompecabezas del telescopio Dyson . Vol. Juegos sin azar 3.
5. Robert A. Hearn (2008). "Amazons, Konane y Cross Purposes son PSPACE-completos". Games of No Chance 3 .
6. Lichtenstein; Sipser (1980). "Go es difícil en el espacio polinomial". Revista de la Asociación de Maquinaria Computacional . 27 (2): 393–401. doi : 10.1145/322186.322201 . S2CID  29498352.
7. Las escaleras de Go son PSPACE-completas Archivado el 30 de septiembre de 2007 en Wayback Machine.
8. Stefan Reisch (1980). "Gobang ist PSPACE-vollstandig (Gomoku es PSPACE completo)". Acta Informática . 13 : 59–66. doi :10.1007/bf00288536. S2CID  21455572.
9. Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex es PSPACE-completo)". Acta Informática (15): 167–191.
10. Viglietta, Giovanni (2015). "Lemmings es PSPACE-Completo" (PDF) . Ciencias Informáticas Teóricas . 586 : 120–134. arXiv : 1202.6581 . doi : 10.1016/j.tcs.2015.01.055 .
11. Erik D. Demaine; Robert A. Hearn (2009). Jugar con algoritmos: teoría de juegos combinatorios algorítmicos. Vol. Juegos sin azar 3.
12. Grier, Daniel (2013). "Decidir el ganador de un juego de conjuntos finitos arbitrarios es PSPACE-completo". Autómatas, lenguajes y programación . Apuntes de clase en informática. Vol. 7965. págs. 497–503. arXiv : 1209.1750 . doi :10.1007/978-3-642-39206-1_42. ISBN . 978-3-642-39205-4. Número de identificación del sujeto  13129445.
13. Shigeki Iwata y Takumi Kasai (1994). "El juego Othello en un tablero n*n es PSPACE-completo". Ciencias Informáticas Teóricas . 123 (2): 329–340. doi : 10.1016/0304-3975(94)90131-7 .
14. Hearn ; Demaine (2002). "PSPACE-Completitud de rompecabezas de bloques deslizantes y otros problemas a través del modelo de computación de lógica de restricciones no determinista". arXiv : cs.CC/0205005 .
15. A. Condon , J. Feigenbaum, C. Lund y P. Shor , Debatientes aleatorios y la dificultad de aproximar funciones estocásticas, SIAM Journal on Computing 26:2 (1997) 369-400.
16. Lampis, Michael; Mitsou, Valia; Sołtys, Karolina (2015). "El Scrabble es PSPACE-completo". Revista de procesamiento de la información .
17. Demaine, Erik D.; Viglietta, Giovanni; Williams, Aaron (junio de 2016). "Super Mario Bros. es más difícil/más fácil de lo que pensábamos" (PDF) . 8.ª Conferencia Internacional de Diversión con Algoritmos .
    Resumen para legos: Sabry, Neamat (28 de abril de 2020). "Super Mario Bros es más difícil/más fácil de lo que pensábamos". Medium .
18. Gilbert, Lengauer y RE Tarjan: El problema de Pebbling está completo en el espacio polinomial. SIAM Journal on Computing, volumen 9, número 3, 1980, páginas 513-524.
19. Philipp Hertel y Toniann Pitassi : Black-White Pebbling es PSPACE-Complete Archivado el 8 de junio de 2011 en Wayback Machine.
20. Takumi Kasai, Akeo Adachi y Shigeki Iwata: Clases de juegos de guijarros y problemas completos , SIAM Journal on Computing, volumen 8, 1979, páginas 574-586.
21. K. Wagner y G. Wechsung. Complejidad computacional . D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 
22. Christos Papadimitriou (1985). "Juegos contra la naturaleza". Revista de Ciencias Informáticas y de Sistemas . 31 (2): 288–301. doi : 10.1016/0022-0000(85)90045-5 .
23. APSistla y Edmund M. Clarke (1985). "La complejidad de las lógicas temporales lineales proposicionales". Revista de la ACM . 32 (3): 733–749. doi : 10.1145/3828.3837 . S2CID  47217193.
24. Evaluación de circuitos enteros
25. Garey y Johnson (1979), AL3.
26. Garey y Johnson (1979), AL4.
27. Garey y Johnson (1979), AL2.
28. Galil, Z. Jerarquías de problemas completos . En Acta Informatica 6 (1976), 77-88.
29. Garey y Johnson (1979), AL1.
30. LJ Stockmeyer y AR Meyer. Problemas verbales que requieren tiempo exponencial. En Actas del 5.º Simposio sobre teoría de la computación, páginas 1 a 9, 1973.
31. JE Hopcroft y JD Ullman. Introducción a la teoría de autómatas, lenguajes y computación , primera edición, 1979.
32. D. Kozen. Límites inferiores para sistemas de prueba naturales. En Proc. 18th Symp. on the Foundations of Computer Science, páginas 254–266, 1977.
33. Problema de la hormiga de Langton Archivado el 27 de septiembre de 2007 en Wayback Machine . "El problema de la hormiga de Langton simétrico generalizado es PSPACE-completo" por YAMAGUCHI EIJI y TSUKIJI TATSUIE en el Informe técnico del IEIC ( Instituto de ingenieros en electrónica, información y comunicación )
34. T. Jiang y B. Ravikumar. Los problemas de NFA mínimos son difíciles. SIAM Journal on Computing, 22(6):1117–1141, diciembre de 1993.
35. S.-Y. Kuroda, "Clases de lenguajes y autómatas linealmente acotados", Información y Control , 7 (2): 207–223, junio de 1964.
36. Bernátsky, László. "La ausencia de estrellas de expresión regular es PSPACE-Complete" (PDF) . Consultado el 13 de enero de 2021 .
37. Garey y Johnson (1979), AL12.
38. Garey y Johnson (1979), AL13.
39. Garey y Johnson (1979), AL14.
40. Garey y Johnson (1979), AL16.
41. Garey y Johnson (1979), AL19.
42. Garey y Johnson (1979), AL21.
43. Antonio Lozano y Jose L. Balcazar. La complejidad de problemas de grafos para grafos representados sucintamente. En Manfred Nagl, editor, Graph-Theoretic Concepts in Computer Science, 15th International Workshop, WG'89, número 411 en Lecture Notes in Computer Science, páginas 277–286. Springer-Verlag, 1990.
44. J. Feigenbaum y S. Kannan y MY Vardi y M. Viswanathan, Complejidad de problemas en gráficos representados como OBDD, Chicago Journal of Theoretical Computer Science, vol 5, no 5, 1999.
45. CH Papadimitriou; M. Yannakakis (1989). "Caminos más cortos sin un mapa". Apuntes de clase en informática . Proc. 16.º ICALP. Vol. 372. Springer-Verlag . págs. 610–620.
46. Alex Fabrikant y Christos Papadimitriou . La complejidad de la dinámica de los juegos: oscilaciones de BGP, equilibrios de sumidero y más allá. Archivado el 5 de septiembre de 2008 en Wayback Machine . En SODA 2008.
47. Erik D. Demaine; Robert A. Hearn (23-26 de junio de 2008). Constraint Logic: A Uniform Framework for Modeling Computation as Games (Lógica de restricciones: un marco uniforme para modelar la computación como juegos). Actas de la 23.ª Conferencia Anual del IEEE sobre Complejidad Computacional (Complejidad 2008). College Park, Maryland. Págs. 149-162.{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
48. Costa, Eurinardo; Pessoa, Victor Lage; Soares, Ronan; Sampaio, Rudini (2020). "Completitud de PSPACE de dos juegos de coloración de gráficos". Ciencias de la Computación Teórica . 824–825: 36–45. doi :10.1016/j.tcs.2020.03.022. S2CID  218777459.
49. Schaefer, Thomas J. (1978). "Sobre la complejidad de algunos juegos de información perfecta para dos personas". Journal of Computer and System Sciences . 16 (2): 185–225. doi : 10.1016/0022-0000(78)90045-4 .
50. CH Papadimitriou; JN Tsitsiklis (1987). "La complejidad de los procesos de decisión de Markov" (PDF) . Matemáticas de la investigación de operaciones . 12 (3): 441–450. doi :10.1287/moor.12.3.441. hdl : 1721.1/2893 .
51. I. Chades; J. Carwardine; TG Martin; S. Nicol; R. Sabbadin; O. Buffet (2012). MOMDP: una solución para modelar problemas de gestión adaptativa . AAAI'12.
52. Casanova, Marco A.; et al. (1984). "Dependencias de inclusión y su interacción con dependencias funcionales". Journal of Computer and System Sciences . 28 : 29–59. doi : 10.1016/0022-0000(84)90075-8 .
53. PW Goldberg y CH Papadimitriou y R. Savani (2011). La complejidad del método de homotopía, selección de equilibrio y soluciones de Lemke-Howson . Proc. 52.° FOCS. IEEE . págs. 67–76.
54. Maarten Marx (2007). "Complejidad de la lógica modal". En Patrick Blackburn; Johan FAK van Benthem; Frank Wolter (eds.). Manual de lógica modal . Elsevier. pág. 170.
55. Lewis, Harry R. (1978). Complejidad de casos resolubles del problema de decisión para el cálculo de predicados . 19.° Simposio Anual sobre Fundamentos de la Ciencia de la Computación. IEEE. págs. 35–47.

Referencias

• Garey, MR ; Johnson, DS (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . Nueva York: WH Freeman. ISBN 978-0-7167-1045-5.
• Página de Eppstein sobre la complejidad computacional de los juegos
• La complejidad de la aproximación de problemas PSPACE-completos para especificaciones jerárquicas