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.

Contents

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] · Node Kayles[10] · Reversi[11] · River Crossing[12] · Rush Hour[12] · Finding optimal play in Mahjong solitaire[13] · Sokoban[12] · Black Pebble game [14] · Black-White Pebble game[15] · Acyclic pebble game[16] · One-player pebble game[16] · Token on acyclic directed graph games: [10] Annihilation; Hit; Capture; Edge Blocking; Target; Pursuit

Logic

Quantified boolean formulas · First-order logic of equality [17] · Satisfaction in intuitionistic propositional logic[17] · Satisfaction in modal logic S4[17] · First-order theory of the natural numbers under the successor operation[17] · First-order theory of the natural numbers under the standard order[17] · First-order theory of the integers under the standard order[17] · First-order theory of well-ordered sets[17] · First-order theory of binary strings under lexicographic ordering[17] · First-order theory of a finite Boolean algebra[17] · Stochastic satisfiability[18] · Linear temporal logic satisfiability and model checking[19]

Lambda calculus

Type inhabitation problem for simply typed lambda calculus

Automata and language theory

Circuit theory

Integer circuit evaluation [20]

Automata theory

Word problem for linear bounded automata[21] · Word problem for quasi-realtime automata[22] · Emptiness problem for a nondeterministic two-way finite state automaton [23] [24] · Equivalence problem for nondeterministic finite automata[25][26] · Word problem and emptiness problem for non-erasing stack automata[27] · Deterministic finite automata intersection emptiness[28] · A generalized version of Langton's Ant[29] · Minimizing nondeterministic finite automata[30]

Formal languages

Word problem for Context-sensitive language [31] · Regular language intersection[28] · Regular expression star freeness[32] · Equivalence problem for regular expressions[17] · Emptiness problem for regular expressions with intersection.[17] · Equivalence problem for star-free regular expressions with squaring.[17] · Covering for linear grammars[33] · Structural equivalence for linear grammars[34] · Equivalence problem for Regular grammars[35] · Emptiness problem for ET0L grammars[36] · Word problem for ET0L grammars[37] · Tree transducer language membership problem for top down finite-state tree transducers[38]

Graph Theory

Others

See also

Notes

  1. ^ R. A. Hearn (2005-02-02). "Amazons is PSPACE-complete". arXiv:cs.CC/0502013 [cs.CC]. 
  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. pp. 55–64. 
  4. ^ Erik D. Demaine (2009). The complexity of the Dyson Telescope Puzzle. 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. 
  6. ^ Lichtenstein; Sipser (1980). "Go is polynomial-space hard". Journal of the Association for Computing Machinery 27 (2): 393–401. 
  7. ^ Go ladders are PSPACE-complete
  8. ^ Stefan Reisch (1980). "Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete)". Acta Informatica 13: 5966. 
  9. ^ Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Inf. (15): 167–191. 
  10. ^ a b c d Erik D. Demaine; Robert A. Hearn (2009). Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. Games of No Chance 3. http://erikdemaine.org/papers/AlgGameTheory_GONC3/. 
  11. ^ 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. 
  12. ^ 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 [cs.CC]. 
  13. ^ 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.
  14. ^ 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.
  15. ^ Philipp Hertel and Toniann Pitassi: Black-White Pebbling is PSPACE-Complete
  16. ^ 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.
  17. ^ a b c d e f g h i j k l K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7
  18. ^ a b c Christos Papadimitriou (1985). "Games against Nature". Journal of Computer and System Sciences 31. doi:10.1016/0022-0000(85)90045-5. 
  19. ^ A.P.Sistla and Edmund M. Clarke (1985). "The complexity of propositional linear temporal logics". Journal of the ACM 32. 
  20. ^ Integer circuit evaluation
  21. ^ Garey–Johnson: AL3
  22. ^ Garey–Johnson: AL4
  23. ^ Galil, Z. Hierarchies of Complete Problems. In Acta Informatica 6 (1976), 77-88.
  24. ^ Garey–Johnson: AL2
  25. ^ 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.
  26. ^ Garey–Johnson: AL1
  27. ^ J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, first edition, 1979.
  28. ^ a b D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.
  29. ^ 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)
  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. ^ Regular expression star-freeness is PSPACE-complete
  33. ^ Garey–Johnson: AL12
  34. ^ Garey–Johnson: AL13
  35. ^ Garey–Johnson: AL14
  36. ^ Garey–Johnson: AL16
  37. ^ Garey–Johnson: AL19
  38. ^ Garey–Johnson: AL21
  39. ^ 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.
  40. ^ 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.
  41. ^ C.H. Papadimitriou; M. Yannakakis (1989). "Shortest paths without a map". Lecture notes in computer science. 372. Proc. 16th ICALP. Springer-Verlag. pp. 610–620. 
  42. ^ Alex Fabrikant and Christos Papadimitriou. The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond. In SODA 2008.
  43. ^ 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). pp. 149–162. http://ccc08.cs.washington.edu/. 

References