Jump to content

List of PSPACE-complete problems

Add links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Lepricavark (talk | contribs) at 20:13, 16 March 2020 (→top: added short description). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

This is a dynamic list and may never be able to satisfy particular standards for completeness. You can help by adding missing items with reliable sources.

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[23]

Automata theory

Formal languages

Graph theory

  • succinct versions of many graph problems, with graphs represented as Boolean circuits,[42] ordered binary decision diagrams[43] 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
  • Canadian traveller problem.[44]
  • Determining whether routes selected by the Border Gateway Protocol will eventually converge to a stable state for a given set of path preferences[45]
  • Dynamic graph reliability.[21]
  • Deterministic constraint logic (unbounded)[46]
  • Nondeterministic Constraint Logic (unbounded)[11]
  • Bounded two-player Constraint Logic[11]

Others

  • Finite horizon POMDPs (Partially Observable Markov Decision Processes).[47]
  • Hidden Model MDPs (hmMDPs).[48]
  • Dynamic Markov process.[21]
  • Detection of inclusion dependencies in a relational database[49]
  • Computation of any Nash equilibrium of a 2-player normal-form game, that may be obtained via the Lemke–Howson algorithm.[50]
  • The Corridor Tiling Problem: given a set of Wang tiles, a chosen tile and a width given in unary notation, is there any height such that an rectangle can be tiled such that all the border tiles are ?[51][52]

See also

Notes

  1. ^ R. A. Hearn (2005-02-02). "Amazons is PSPACE-complete". arXiv:cs.CC/0502013.
  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.
  3. ^ Assuming a draw after a polynomial number of moves. 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. {{cite journal}}: Cite journal requires |journal= (help)
  4. ^ Erik D. Demaine (2009). The complexity of the Dyson Telescope Puzzle. Vol. Games of No Chance 3.
  5. ^ a b Robert A. Hearn (2008). "Amazons, Konane, and Cross Purposes are PSPACE-complete". Games of No Chance 3. {{cite journal}}: Cite journal requires |journal= (help)
  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.
  7. ^ Go ladders are PSPACE-complete Archived 2007-09-30 at the Wayback Machine
  8. ^ Stefan Reisch (1980). "Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete)". Acta Informatica. 13: 59–66. doi:10.1007/bf00288536.
  9. ^ Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Inform. (15): 167–191.
  10. ^ Viglietta, Giovanni (2015). "Lemmings Is PSPACE-Complete" (PDF). Theoretical Computer Science. 586: 120–134. doi:10.1016/j.tcs.2015.01.055.
  11. ^ a b c d Erik D. Demaine; Robert A. Hearn (2009). Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. Vol. Games of No Chance 3.
  12. ^ Grier, Daniel (2012). "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.
  13. ^ 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.
  14. ^ a b c Hearn; Demaine (2002). "PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation". arXiv:cs.CC/0205005.
  15. ^ 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.
  16. ^ Demaine; Viglietta; Williams (2016). "Super Mario Bros. Is Harder/Easier than We Thought". {{cite journal}}: Cite journal requires |journal= (help)
  17. ^ 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.
  18. ^ Philipp Hertel and Toniann Pitassi: Black-White Pebbling is PSPACE-Complete Archived 2011-06-08 at the Wayback Machine
  19. ^ a b Takumi Kasai, Akeo Adachi, and Shigeki Iwata: Classes of Pebble Games and Complete Problems, SIAM Journal on Computing, Volume 8, 1979, pages 574-586.
  20. ^ a b c d e f g h i j k K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7
  21. ^ a b c Christos Papadimitriou (1985). "Games against Nature". Journal of Computer and System Sciences. 31 (2): 288–301. doi:10.1016/0022-0000(85)90045-5.
  22. ^ 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.
  23. ^ Integer circuit evaluation
  24. ^ Garey–Johnson: AL3
  25. ^ Garey–Johnson: AL4
  26. ^ Galil, Z. Hierarchies of Complete Problems. In Acta Informatica 6 (1976), 77-88.
  27. ^ Garey–Johnson: AL2
  28. ^ 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.
  29. ^ Garey–Johnson: AL1
  30. ^ J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, first edition, 1979.
  31. ^ a b D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.
  32. ^ 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)
  33. ^ T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on Computing, 22(6):1117–1141, December 1993.
  34. ^ S.-Y. Kuroda, "Classes of languages and linear-bounded automata", Information and Control, 7(2): 207–223, June 1964.
  35. ^ Regular expression star-freeness is PSPACE-complete
  36. ^ Garey–Johnson: AL12
  37. ^ Garey–Johnson: AL13
  38. ^ Garey–Johnson: AL14
  39. ^ Garey–Johnson: AL16
  40. ^ Garey–Johnson: AL19
  41. ^ Garey–Johnson: AL21
  42. ^ 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.
  43. ^ 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.
  44. ^ 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. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
  45. ^ 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.
  46. ^ Erik D. Demaine and 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)
  47. ^ 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.
  48. ^ I. Chades; J. Carwardine; T.G. Martin; S. Nicol; R. Sabbadin; O. Buffet (2012). MOMDPs: A Solution for Modelling Adaptive Management Problems. AAAI'12.
  49. ^ 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.
  50. ^ 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.
  51. ^ 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.
  52. ^ 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.

References

Retrieved from "https://en.wikipedia.org/w/index.php?title=List_of_PSPACE-complete_problems&oldid=945894680"