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
Generalized versions of:
Amazons[1] Atomix[2] · Checkers[3] · Dyson Telescope Game[4] · Cross Purposes[5] · Geography · 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] · Sokoban[14] · Super Mario Bros.[16] · Black Pebble game[17] · Black-White Pebble game[18] · Acyclic pebble game[19] · One-player pebble game[19] · Token on acyclic directed graph games:[11] Annihilation; Hit; Capture; Edge Blocking; Target; Pursuit
Logic
Quantified boolean formulas · First-order logic of equality[20] · Satisfaction in intuitionistic propositional logic[20] · Satisfaction in modal logic S4[20] · First-order theory of the natural numbers under the successor operation[20] · First-order theory of the natural numbers under the standard order[20] · First-order theory of the integers under the standard order[20] · First-order theory of well-ordered sets[20] · First-order theory of binary strings under lexicographic ordering[20] · First-order theory of a finite Boolean algebra[20] · Stochastic satisfiability[21] · Linear temporal logic satisfiability and model checking[22]
Lambda calculus
Type inhabitation problem for simply typed lambda calculus
Automata and language theory
Circuit theory
Integer circuit evaluation[23]
Automata theory
Word problem for linear bounded automata[24] · Word problem for quasi-realtime automata[25] · Emptiness problem for a nondeterministic two-way finite state automaton[26] [27] · Equivalence problem for nondeterministic finite automata[28][29] · Word problem and emptiness problem for non-erasing stack automata[30] · Deterministic finite automata intersection emptiness[31] · A generalized version of Langton's Ant[32] · Minimizing nondeterministic finite automata[33]
Formal languages
Word problem for context-sensitive language[34] · Regular language intersection[31] · Regular expression star freeness[35] · Equivalence problem for regular expressions[20] · Emptiness problem for regular expressions with intersection.[20] · Equivalence problem for star-free regular expressions with squaring.[20] · Covering for linear grammars[36] · Structural equivalence for linear grammars[37] · Equivalence problem for Regular grammars[38] · Emptiness problem for ET0L grammars[39] · Word problem for ET0L grammars[40] · Tree transducer language membership problem for top down finite-state tree transducers[41]
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]
See also
Notes
- ↑ R. A. Hearn (2005-02-02). "Amazons is PSPACE-complete". arXiv:cs.CC/0502013 [cs.CC].
- ↑ 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.
- ↑ 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.
- ↑ Erik D. Demaine (2009). The complexity of the Dyson Telescope Puzzle. Games of No Chance 3.
- 1 2 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.
- ↑ Go ladders are PSPACE-complete
- ↑ Stefan Reisch (1980). "Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete)". Acta Informatica. 13: 5966. doi:10.1007/bf00288536.
- ↑ Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Inf. (15): 167–191.
- ↑ Viglietta, Giovanni. "Lemmings is PSPACE-complete".
- 1 2 3 4 Erik D. Demaine; Robert A. Hearn (2009). Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. Games of No Chance 3.
- ↑ Grier, Daniel (2012). "Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-Complete". arXiv:1209.1750.
- ↑ Shigeki Iwata and Takumi Kasai (1994). "The Othello game on an n*n board is PSPACE-complete". Theor. Comp. Sci. 123 (123): 329–340. doi:10.1016/0304-3975(94)90131-7.
- 1 2 3 Hearn; Demaine (2002). "PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation". arXiv:cs.CC/0205005 [cs.CC].
- ↑ 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.
- ↑ Demaine; Viglietta; Williams (2016). "Super Mario Bros. Is Harder/Easier than We Thought".
- ↑ 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
- 1 2 Takumi Kasai, Akeo Adachi, and Shigeki Iwata: Classes of Pebble Games and Complete Problems, SIAM Journal on Computing, Volume 8, 1979, pages 574-586.
- 1 2 3 4 5 6 7 8 9 10 11 12 K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7
- 1 2 3 Christos Papadimitriou (1985). "Games against Nature". Journal of Computer and System Sciences. 31 (2): 288. 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. doi:10.1145/3828.3837.
- ↑ Integer circuit evaluation
- ↑ Garey–Johnson: AL3
- ↑ Garey–Johnson: AL4
- ↑ Galil, Z. Hierarchies of Complete Problems. In Acta Informatica 6 (1976), 77-88.
- ↑ Garey–Johnson: AL2
- ↑ 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.
- ↑ Garey–Johnson: AL1
- ↑ J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, first edition, 1979.
- 1 2 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, "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.
- ↑ Regular expression star-freeness is PSPACE-complete
- ↑ Garey–Johnson: AL12
- ↑ Garey–Johnson: AL13
- ↑ Garey–Johnson: AL14
- ↑ Garey–Johnson: AL16
- ↑ Garey–Johnson: AL19
- ↑ Garey–Johnson: 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. 372. Springer-Verlag. pp. 610–620.
- ↑ Alex Fabrikant and Christos Papadimitriou. The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond. In SODA 2008.
- ↑ Erik D. Demaine and Robert A. Hearn (June 23–26, 2008). 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. pp. 149–162.
- ↑ C.H. Papadimitriou; J.N. Tsitsiklis (1987). "The complexity of Markov Decision Processes". Journal of Mathematics of Operations Research. 12 (3): 441–450. doi:10.1287/moor.12.3.441.
- ↑ 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. "Inclusion Dependencies and Their Interaction with Functional Dependencies". Journal of Computer and System Sciences 28, 29-59 (1984).
- ↑ 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.
References
- Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5.
- Eppstein's page on computational complexity of games
- The Complexity of Approximating PSPACE-complete problems for hierarchical specifications