Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
List of PSPACE-complete problems
List article

Here are some of the more commonly known problems that are PSPACE-complete when expressed as decision problems. This list is in no way comprehensive.

Games and puzzles

Generalized versions of:

Logic

Lambda calculus

Type inhabitation problem for simply typed lambda calculus

Automata and language theory

Circuit theory

Integer circuit evaluation36

Automata theory

Formal languages

Graph theory

  • succinct versions of many graph problems, with graphs represented as Boolean circuits,59 ordered binary decision diagrams60 or other related representations:
    • s-t reachability problem for succinct graphs. This is essentially the same as the simplest plan existence problem in automated planning and scheduling.
    • planarity of succinct graphs
    • acyclicity of succinct graphs
    • connectedness of succinct graphs
    • existence of Eulerian paths in a succinct graph
  • Bounded two-player Constraint Logic61
  • Canadian traveller problem.62
  • Determining whether routes selected by the Border Gateway Protocol will eventually converge to a stable state for a given set of path preferences63
  • Deterministic constraint logic (unbounded)64
  • Dynamic graph reliability.65
  • Graph coloring game66
  • Node Kayles game and clique-forming game:67 two players alternately select vertices and the induced subgraph must be an independent set (resp. clique). The last to play wins.
  • Nondeterministic Constraint Logic (unbounded)68

Others

  • Finite horizon POMDPs (Partially Observable Markov Decision Processes).69
  • Hidden Model MDPs (hmMDPs).70
  • Dynamic Markov process.71
  • Detection of inclusion dependencies in a relational database72
  • Computation of any Nash equilibrium of a 2-player normal-form game, that may be obtained via the Lemke–Howson algorithm.73
  • The Corridor Tiling Problem: given a set of Wang tiles, a chosen tile T 0 {\displaystyle T_{0}} and a width n {\displaystyle n} given in unary notation, is there any height m {\displaystyle m} such that an n × m {\displaystyle n\times m} rectangle can be tiled such that all the border tiles are T 0 {\displaystyle T_{0}} ?7475

See also

Notes

References

  1. R. A. Hearn (February 2, 2005). "Amazons is PSPACE-complete". arXiv:cs.CC/0502013. /wiki/Bob_Hearn ↩

  2. Markus Holzer and Stefan Schwoon (February 2004). "Assembling molecules in ATOMIX is hard". Theoretical Computer Science. 313 (3): 447–462. doi:10.1016/j.tcs.2002.11.002. https://doi.org/10.1016%2Fj.tcs.2002.11.002 ↩

  3. Aviezri S. Fraenkel (1978). "The complexity of checkers on an N x N board - preliminary report". Proceedings of the 19th Annual Symposium on Computer Science: 55–64. ↩

  4. Erik D. Demaine (2009). The complexity of the Dyson Telescope Puzzle. Vol. Games of No Chance 3. ↩

  5. Robert A. Hearn (2008). "Amazons, Konane, and Cross Purposes are PSPACE-complete". Games of No Chance 3. /wiki/Bob_Hearn ↩

  6. Lichtenstein; Sipser (1980). "Go is polynomial-space hard". Journal of the Association for Computing Machinery. 27 (2): 393–401. doi:10.1145/322186.322201. S2CID 29498352. https://doi.org/10.1145%2F322186.322201 ↩

  7. Go ladders are PSPACE-complete Archived 2007-09-30 at the Wayback Machine http://homepages.cwi.nl/~tromp/lad.ps ↩

  8. Stefan Reisch (1980). "Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete)". Acta Informatica. 13: 59–66. doi:10.1007/bf00288536. S2CID 21455572. /wiki/Doi_(identifier) ↩

  9. Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Informatica (15): 167–191. ↩

  10. Robert A. Hearn (2008). "Amazons, Konane, and Cross Purposes are PSPACE-complete". Games of No Chance 3. /wiki/Bob_Hearn ↩

  11. Viglietta, Giovanni (2015). "Lemmings Is PSPACE-Complete" (PDF). Theoretical Computer Science. 586: 120–134. arXiv:1202.6581. doi:10.1016/j.tcs.2015.01.055. http://giovanniviglietta.com/papers/lemmings2.pdf ↩

  12. Erik D. Demaine; Robert A. Hearn (2009). Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. Vol. Games of No Chance 3. /wiki/Bob_Hearn ↩

  13. Grier, Daniel (2013). "Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-Complete". Automata, Languages, and Programming. Lecture Notes in Computer Science. Vol. 7965. pp. 497–503. arXiv:1209.1750. doi:10.1007/978-3-642-39206-1_42. ISBN 978-3-642-39205-4. S2CID 13129445. 978-3-642-39205-4 ↩

  14. Shigeki Iwata and Takumi Kasai (1994). "The Othello game on an n*n board is PSPACE-complete". Theoretical Computer Science. 123 (2): 329–340. doi:10.1016/0304-3975(94)90131-7. https://doi.org/10.1016%2F0304-3975%2894%2990131-7 ↩

  15. Hearn; Demaine (2002). "PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation". arXiv:cs.CC/0205005. /wiki/Bob_Hearn ↩

  16. Hearn; Demaine (2002). "PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation". arXiv:cs.CC/0205005. /wiki/Bob_Hearn ↩

  17. A. Condon, J. Feigenbaum, C. Lund, and P. Shor, Random debaters and the hardness of approximating stochastic functions, SIAM Journal on Computing 26:2 (1997) 369-400. /wiki/Anne_Condon ↩

  18. Lampis, Michael; Mitsou, Valia; Sołtys, Karolina (2015). "Scrabble is PSPACE-complete". Journal of Information Processing. https://www.jstage.jst.go.jp/article/ipsjjip/23/3/23_284/_article ↩

  19. Hearn; Demaine (2002). "PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation". arXiv:cs.CC/0205005. /wiki/Bob_Hearn ↩

  20. Demaine, Erik D.; Viglietta, Giovanni; Williams, Aaron (June 2016). "Super Mario Bros. Is Harder/Easier than We Thought" (PDF). 8th International Conference of Fun with Algorithms.Lay summary: Sabry, Neamat (April 28, 2020). "Super Mario Bros is Harder/Easier Than We Thought". Medium. https://dspace.mit.edu/bitstream/handle/1721.1/103079/Supermario%20Demaine.pdf?sequence=1&isAllowed=y ↩

  21. Gilbert, Lengauer, and R. E. Tarjan: The Pebbling Problem is Complete in Polynomial Space. SIAM Journal on Computing, Volume 9, Issue 3, 1980, pages 513-524. ↩

  22. Philipp Hertel and Toniann Pitassi: Black-White Pebbling is PSPACE-Complete Archived 2011-06-08 at the Wayback Machine /wiki/Toniann_Pitassi ↩

  23. Takumi Kasai, Akeo Adachi, and Shigeki Iwata: Classes of Pebble Games and Complete Problems, SIAM Journal on Computing, Volume 8, 1979, pages 574-586. ↩

  24. Takumi Kasai, Akeo Adachi, and Shigeki Iwata: Classes of Pebble Games and Complete Problems, SIAM Journal on Computing, Volume 8, 1979, pages 574-586. ↩

  25. Erik D. Demaine; Robert A. Hearn (2009). Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. Vol. Games of No Chance 3. /wiki/Bob_Hearn ↩

  26. K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 /wiki/D._Reidel ↩

  27. K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 /wiki/D._Reidel ↩

  28. K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 /wiki/D._Reidel ↩

  29. K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 /wiki/D._Reidel ↩

  30. K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 /wiki/D._Reidel ↩

  31. K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 /wiki/D._Reidel ↩

  32. K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 /wiki/D._Reidel ↩

  33. K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 /wiki/D._Reidel ↩

  34. Christos Papadimitriou (1985). "Games against Nature". Journal of Computer and System Sciences. 31 (2): 288–301. doi:10.1016/0022-0000(85)90045-5. /wiki/Christos_Papadimitriou ↩

  35. A.P.Sistla and Edmund M. Clarke (1985). "The complexity of propositional linear temporal logics". Journal of the ACM. 32 (3): 733–749. doi:10.1145/3828.3837. S2CID 47217193. /wiki/Edmund_M._Clarke ↩

  36. Integer circuit evaluation https://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/6911/18589/00856751.pdf ↩

  37. Garey & Johnson (1979), AL3. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. ↩

  38. Garey & Johnson (1979), AL4. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. ↩

  39. Garey & Johnson (1979), AL2. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. ↩

  40. Galil, Z. Hierarchies of Complete Problems. In Acta Informatica 6 (1976), 77-88. ↩

  41. Garey & Johnson (1979), AL1. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. ↩

  42. L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time. In Proceedings of the 5th Symposium on Theory of Computing, pages 1–9, 1973. /wiki/Larry_Stockmeyer ↩

  43. J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, first edition, 1979. /wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation ↩

  44. D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977. ↩

  45. Langton's Ant problem Archived 2007-09-27 at the Wayback Machine, "Generalized symmetrical Langton's ant problem is PSPACE-complete" by YAMAGUCHI EIJI and TSUKIJI TATSUIE in IEIC Technical Report (Institute of Electronics, Information and Communication Engineers) http://sciencelinks.jp/j-east/article/200212/000020021202A0428168.php ↩

  46. T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on Computing, 22(6):1117–1141, December 1993. ↩

  47. S.-Y. Kuroda, "Classes of languages and linear-bounded automata", Information and Control, 7(2): 207–223, June 1964. ↩

  48. D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977. ↩

  49. Bernátsky, László. "Regular Expression star-freeness is PSPACE-Complete" (PDF). Retrieved 2021-01-13. http://publicatio.bibl.u-szeged.hu/9528/1/Bernatsky_1997_ActaCybernetica.pdf ↩

  50. K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 /wiki/D._Reidel ↩

  51. K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 /wiki/D._Reidel ↩

  52. K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 /wiki/D._Reidel ↩

  53. Garey & Johnson (1979), AL12. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. ↩

  54. Garey & Johnson (1979), AL13. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. ↩

  55. Garey & Johnson (1979), AL14. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. ↩

  56. Garey & Johnson (1979), AL16. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. ↩

  57. Garey & Johnson (1979), AL19. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. ↩

  58. Garey & Johnson (1979), AL21. - Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. ↩

  59. Antonio Lozano and Jose L. Balcazar. The complexity of graph problems for succinctly represented graphs. In Manfred Nagl, editor, Graph-Theoretic Concepts in Computer Science, 15th International Workshop, WG'89, number 411 in Lecture Notes in Computer Science, pages 277–286. Springer-Verlag, 1990. ↩

  60. J. Feigenbaum and S. Kannan and M. Y. Vardi and M. Viswanathan, Complexity of Problems on Graphs Represented as OBDDs, Chicago Journal of Theoretical Computer Science, vol 5, no 5, 1999. ↩

  61. Erik D. Demaine; Robert A. Hearn (2009). Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. Vol. Games of No Chance 3. /wiki/Bob_Hearn ↩

  62. C.H. Papadimitriou; M. Yannakakis (1989). "Shortest paths without a map". Lecture Notes in Computer Science. Proc. 16th ICALP. Vol. 372. Springer-Verlag. pp. 610–620. /wiki/Springer-Verlag ↩

  63. Alex Fabrikant and Christos Papadimitriou. The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond Archived 2008-09-05 at the Wayback Machine. In SODA 2008. /wiki/Christos_Papadimitriou ↩

  64. Erik D. Demaine; Robert A. Hearn (June 23–26, 2008). Constraint Logic: A Uniform Framework for Modeling Computation as Games. Vol. Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (Complexity 2008). College Park, Maryland. pp. 149–162.{{cite book}}: CS1 maint: location missing publisher (link) /wiki/Bob_Hearn ↩

  65. Christos Papadimitriou (1985). "Games against Nature". Journal of Computer and System Sciences. 31 (2): 288–301. doi:10.1016/0022-0000(85)90045-5. /wiki/Christos_Papadimitriou ↩

  66. Costa, Eurinardo; Pessoa, Victor Lage; Soares, Ronan; Sampaio, Rudini (2020). "PSPACE-completeness of two graph coloring games". Theoretical Computer Science. 824–825: 36–45. doi:10.1016/j.tcs.2020.03.022. S2CID 218777459. /wiki/Doi_(identifier) ↩

  67. Schaefer, Thomas J. (1978). "On the complexity of some two-person perfect-information games". Journal of Computer and System Sciences. 16 (2): 185–225. doi:10.1016/0022-0000(78)90045-4. https://doi.org/10.1016%2F0022-0000%2878%2990045-4 ↩

  68. Erik D. Demaine; Robert A. Hearn (2009). Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. Vol. Games of No Chance 3. /wiki/Bob_Hearn ↩

  69. C.H. Papadimitriou; J.N. Tsitsiklis (1987). "The complexity of Markov Decision Processes" (PDF). Mathematics of Operations Research. 12 (3): 441–450. doi:10.1287/moor.12.3.441. hdl:1721.1/2893. http://dspace.mit.edu/bitstream/1721.1/2893/1/P-1479-13685602.pdf ↩

  70. I. Chades; J. Carwardine; T.G. Martin; S. Nicol; R. Sabbadin; O. Buffet (2012). MOMDPs: A Solution for Modelling Adaptive Management Problems. AAAI'12. ↩

  71. Christos Papadimitriou (1985). "Games against Nature". Journal of Computer and System Sciences. 31 (2): 288–301. doi:10.1016/0022-0000(85)90045-5. /wiki/Christos_Papadimitriou ↩

  72. Casanova, Marco A.; et al. (1984). "Inclusion Dependencies and Their Interaction with Functional Dependencies". Journal of Computer and System Sciences. 28: 29–59. doi:10.1016/0022-0000(84)90075-8. https://doi.org/10.1016%2F0022-0000%2884%2990075-8 ↩

  73. P.W. Goldberg and C.H. Papadimitriou and R. Savani (2011). The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke–Howson Solutions. Proc. 52nd FOCS. IEEE. pp. 67–76. /wiki/Christos_Papadimitriou ↩

  74. Maarten Marx (2007). "Complexity of Modal Logic". In Patrick Blackburn; Johan F.A.K. van Benthem; Frank Wolter (eds.). Handbook of Modal Logic. Elsevier. p. 170. ↩

  75. Lewis, Harry R. (1978). Complexity of solvable cases of the decision problem for the predicate calculus. 19th Annual Symposium on Foundations of Computer Science. IEEE. pp. 35–47. ↩