List of PSPACE-complete problems explained

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 evaluation[24]

Automata theory

Formal languages

Graph theory

Others

T0

and a width

n

given in unary notation, is there any height

m

such that an

n x m

rectangle can be tiled such that all the border tiles are

T0

?[44] [45]

See also

Notes

  1. R. A. Hearn . Amazons is PSPACE-complete . 2005-02-02 . cs.CC/0502013 .
  2. Markus Holzer and Stefan Schwoon . Assembling molecules in ATOMIX is hard . Theoretical Computer Science . 313 . 3 . February 2004 . 447–462 . 10.1016/j.tcs.2002.11.002. free .
  3. Aviezri S. Fraenkel . The complexity of checkers on an N x N board - preliminary report . Proceedings of the 19th Annual Symposium on Computer Science . 55–64 . 1978.
  4. Book: Erik D. Demaine . The complexity of the Dyson Telescope Puzzle . Games of No Chance 3 . 2009.
  5. Robert A. Hearn . Amazons, Konane, and Cross Purposes are PSPACE-complete . Games of No Chance 3 . 2008.
  6. Lichtenstein . Sipser . Go is polynomial-space hard . Journal of the Association for Computing Machinery . 27 . 2 . 393–401 . 1980 . 10.1145/322186.322201. 29498352 . free .
  7. http://homepages.cwi.nl/~tromp/lad.ps Go ladders are PSPACE-complete
  8. Stefan Reisch . Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete) . Acta Informatica . 13 . 59–66 . 1980 . 10.1007/bf00288536. 21455572 .
  9. Stefan Reisch . Hex ist PSPACE-vollständig (Hex is PSPACE-complete) . Acta Informatica . 15 . 1981 . 167–191.
  10. Viglietta. Giovanni. Lemmings Is PSPACE-Complete. Theoretical Computer Science. 2015. 586. 120–134 . 10.1016/j.tcs.2015.01.055 . 1202.6581 . free.
  11. Book: Erik D. Demaine . Robert A. Hearn . Playing Games with Algorithms: Algorithmic Combinatorial Game Theory . Games of No Chance 3 . 2009 .
  12. Book: Grier, Daniel . Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-Complete . 1209.1750 . 10.1007/978-3-642-39206-1_42 . Automata, Languages, and Programming . 7965 . 497–503 . Lecture Notes in Computer Science . 2013 . 978-3-642-39205-4 . 13129445 .
  13. Shigeki Iwata and Takumi Kasai . The Othello game on an n*n board is PSPACE-complete . Theoretical Computer Science . 123 . 2 . 1994 . 329 - 340 . 10.1016/0304-3975(94)90131-7. free .
  14. cs.CC/0205005. Hearn. Demaine. PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation . 2002.
  15. [Anne Condon|A. Condon]
  16. Michael . Lampis . Valia . Mitsou . Karolina . Sołtys . Scrabble is PSPACE-complete . Journal of Information Processing . 2015 .
  17. Demaine . Erik D. . Viglietta . Giovanni . Williams . Aaron . Super Mario Bros. Is Harder/Easier than We Thought . 8th International Conference of Fun with Algorithms . June 2016 .
    Lay summary: Web site: Sabry . Neamat . Apr 28, 2020 . Super Mario Bros is Harder/Easier Than We Thought . Medium .
  18. 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.
  19. Philipp Hertel and Toniann Pitassi: Black-White Pebbling is PSPACE-Complete
  20. Takumi Kasai, Akeo Adachi, and Shigeki Iwata: Classes of Pebble Games and Complete Problems, SIAM Journal on Computing, Volume 8, 1979, pages 574-586.
  21. K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986.
  22. Christos Papadimitriou . Games against Nature . 10.1016/0022-0000(85)90045-5 . Journal of Computer and System Sciences . 1985 . 31. 2. 288–301. Christos Papadimitriou . free.
  23. A.P.Sistla and Edmund M. Clarke. The complexity of propositional linear temporal logics. Journal of the ACM. 32. 3. 1985. 10.1145/3828.3837. 733–749. 47217193 . free.
  24. https://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/6911/18589/00856751.pdf Integer circuit evaluation
  25. Galil, Z. Hierarchies of Complete Problems. In Acta Informatica 6 (1976), 77-88.
  26. [Larry Stockmeyer|L. J. Stockmeyer]
  27. J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, first edition, 1979.
  28. D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.
  29. http://sciencelinks.jp/j-east/article/200212/000020021202A0428168.php Langton's Ant problem
  30. T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on Computing, 22(6):1117–1141, December 1993.
  31. S.-Y. Kuroda, "Classes of languages and linear-bounded automata", Information and Control, 7(2): 207 - 223, June 1964.
  32. Web site: Bernátsky . László . Regular Expression star-freeness is PSPACE-Complete . 13 January 2021.
  33. 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.
  34. 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.
  35. C.H. Papadimitriou . M. Yannakakis . Shortest paths without a map . Proc. 16th ICALP . Lecture Notes in Computer Science . 372 . . 1989 . 610–620 .
  36. Alex Fabrikant and Christos Papadimitriou. The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond . In SODA 2008.
  37. Book: Erik D. Demaine and Robert A. Hearn. Constraint Logic: A Uniform Framework for Modeling Computation as Games. Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (Complexity 2008). College Park, Maryland. June 23–26, 2008. 149–162.
  38. Costa. Eurinardo. Pessoa. Victor Lage . Soares. Ronan. Sampaio. Rudini. 2020. PSPACE-completeness of two graph coloring games . Theoretical Computer Science. 824-825. 36–45 . 10.1016/j.tcs.2020.03.022 . 218777459.
  39. Schaefer. Thomas J. . 1978. On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences. 16. 2 . 185–225. 10.1016/0022-0000(78)90045-4. free.
  40. C.H. Papadimitriou . J.N. Tsitsiklis . The complexity of Markov Decision Processes . Mathematics of Operations Research. 12 . 3 . 1987. 441–450 . 10.1287/moor.12.3.441. 1721.1/2893 . free .
  41. I. Chades . J. Carwardine . T.G. Martin . S. Nicol . R. Sabbadin . O. Buffet . MOMDPs: A Solution for Modelling Adaptive Management Problems . AAAI'12 . 2012.
  42. Casanova, Marco A. . et al . 1984 . Inclusion Dependencies and Their Interaction with Functional Dependencies . Journal of Computer and System Sciences . 28 . 29–59 . 10.1016/0022-0000(84)90075-8. free.
  43. P.W. Goldberg and C.H. Papadimitriou and R. Savani . The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke–Howson Solutions . Proc. 52nd FOCS . . 2011 . 67–76 .
  44. Encyclopedia: Maarten Marx . Complexity of Modal Logic . Handbook of Modal Logic . Patrick Blackburn . Johan F.A.K. van Benthem. Frank Wolter. Elsevier . 2007 . 170.
  45. Complexity of solvable cases of the decision problem for the predicate calculus. Lewis, Harry R.. 19th Annual Symposium on Foundations of Computer Science. 35–47. 1978. IEEE.

References