List of PSPACE-complete problems
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
[edit]Generalized versions of:
- Amazons[1]
- Atomix[2]
- Checkers if a draw is forced after a polynomial number of non-jump moves[3]
- Dyson Telescope Game[4]
- Cross Purposes[5]
- Geography
- Two-player game version of Instant Insanity
- Ko-free Go[6]
- Ladder capturing in Go[7]
- Gomoku[8]
- Hex[9]
- Konane[5]
- Lemmings[10]
- Node Kayles[11]
- Poset Game[12]
- Reversi[13]
- River Crossing[14]
- Rush Hour[14]
- Finding optimal play in Mahjong solitaire[15]
- Scrabble[16]
- Sokoban[14]
- Super Mario Bros.[17]
- Black Pebble game[18]
- Black-White Pebble game[19]
- Acyclic pebble game[20]
- One-player pebble game[20]
- Token on acyclic directed graph games:[11]
Logic
[edit]- Quantified boolean formulas
- First-order logic of equality[21]
- Provability in intuitionistic propositional logic
- Satisfaction in modal logic S4[21]
- First-order theory of the natural numbers under the successor operation[21]
- First-order theory of the natural numbers under the standard order[21]
- First-order theory of the integers under the standard order[21]
- First-order theory of well-ordered sets[21]
- First-order theory of binary strings under lexicographic ordering[21]
- First-order theory of a finite Boolean algebra[21]
- Stochastic satisfiability[22]
- Linear temporal logic satisfiability and model checking[23]
Lambda calculus
[edit]Type inhabitation problem for simply typed lambda calculus
Automata and language theory
[edit]Circuit theory
[edit]Integer circuit evaluation[24]
Automata theory
[edit]- Word problem for linear bounded automata[25]
- Word problem for quasi-realtime automata[26]
- Emptiness problem for a nondeterministic two-way finite state automaton[27][28]
- Equivalence problem for nondeterministic finite automata[29][30]
- Word problem and emptiness problem for non-erasing stack automata[31]
- Emptiness of intersection of an unbounded number of deterministic finite automata[32]
- A generalized version of Langton's Ant[33]
- Minimizing nondeterministic finite automata[34]
Formal languages
[edit]- Word problem for context-sensitive language[35]
- Intersection emptiness for an unbounded number of regular languages [32]
- Regular Expression Star-Freeness [36]
- Equivalence problem for regular expressions[21]
- Emptiness problem for regular expressions with intersection.[21]
- Equivalence problem for star-free regular expressions with squaring.[21]
- Covering for linear grammars[37]
- Structural equivalence for linear grammars[38]
- Equivalence problem for Regular grammars[39]
- Emptiness problem for ET0L grammars[40]
- Word problem for ET0L grammars[41]
- Tree transducer language membership problem for top down finite-state tree transducers[42]
Graph theory
[edit]- succinct versions of many graph problems, with graphs represented as Boolean circuits,[43] ordered binary decision diagrams[44] 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 Logic[11]
- Canadian traveller problem.[45]
- Determining whether routes selected by the Border Gateway Protocol will eventually converge to a stable state for a given set of path preferences[46]
- Deterministic constraint logic (unbounded)[47]
- Dynamic graph reliability.[22]
- Graph coloring game[48]
- Node Kayles game and clique-forming game:[49] 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)[11]
Others
[edit]- Finite horizon POMDPs (Partially Observable Markov Decision Processes).[50]
- Hidden Model MDPs (hmMDPs).[51]
- Dynamic Markov process.[22]
- Detection of inclusion dependencies in a relational database[52]
- Computation of any Nash equilibrium of a 2-player normal-form game, that may be obtained via the Lemke–Howson algorithm.[53]
- 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 ?[54][55]
See also
[edit]Notes
[edit]- ^ R. A. Hearn (February 2, 2005). "Amazons is PSPACE-complete". arXiv:cs.CC/0502013.
- ^ 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.
- ^ 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.
- ^ Erik D. Demaine (2009). The complexity of the Dyson Telescope Puzzle. Vol. Games of No Chance 3.
- ^ a b Robert A. Hearn (2008). "Amazons, Konane, and Cross Purposes are PSPACE-complete". Games of No Chance 3.
- ^ 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.
- ^ Go ladders are PSPACE-complete Archived 2007-09-30 at the Wayback Machine
- ^ Stefan Reisch (1980). "Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete)". Acta Informatica. 13: 59–66. doi:10.1007/bf00288536. S2CID 21455572.
- ^ Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Informatica (15): 167–191.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Lampis, Michael; Mitsou, Valia; Sołtys, Karolina (2015). "Scrabble is PSPACE-complete". Journal of Information Processing.
- ^ 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. - ^ 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.
- ^ Philipp Hertel and Toniann Pitassi: Black-White Pebbling is PSPACE-Complete Archived 2011-06-08 at the Wayback Machine
- ^ 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.
- ^ 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
- ^ 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.
- ^ 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.
- ^ Integer circuit evaluation
- ^ Garey & Johnson (1979), AL3.
- ^ Garey & Johnson (1979), AL4.
- ^ Garey & Johnson (1979), AL2.
- ^ Galil, Z. Hierarchies of Complete Problems. In Acta Informatica 6 (1976), 77-88.
- ^ Garey & Johnson (1979), AL1.
- ^ 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.
- ^ J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, first edition, 1979.
- ^ a b D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.
- ^ 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)
- ^ T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on Computing, 22(6):1117–1141, December 1993.
- ^ S.-Y. Kuroda, "Classes of languages and linear-bounded automata", Information and Control, 7(2): 207–223, June 1964.
- ^ Bernátsky, László. "Regular Expression star-freeness is PSPACE-Complete" (PDF). Retrieved 2021-01-13.
- ^ Garey & Johnson (1979), AL12.
- ^ Garey & Johnson (1979), AL13.
- ^ Garey & Johnson (1979), AL14.
- ^ Garey & Johnson (1979), AL16.
- ^ Garey & Johnson (1979), AL19.
- ^ Garey & Johnson (1979), AL21.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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) - ^ 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.
- ^ 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.
- ^ 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.
- ^ I. Chades; J. Carwardine; T.G. Martin; S. Nicol; R. Sabbadin; O. Buffet (2012). MOMDPs: A Solution for Modelling Adaptive Management Problems. AAAI'12.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.