List of PSPACE-complete problems

Generalized versions of:

{{div col |colwidth=18em}}

• Amazons{{cite arXiv | author = R. A. Hearn | author-link=Bob Hearn | title = Amazons is PSPACE-complete | date = 2005-02-02 | eprint = cs.CC/0502013 }}
• Atomix{{Cite journal | author = Markus Holzer and Stefan Schwoon | title = Assembling molecules in ATOMIX is hard | journal = Theoretical Computer Science | volume = 313 | issue = 3 |date=February 2004 | pages = 447–462 | doi = 10.1016/j.tcs.2002.11.002| doi-access = free }}
• Checkers if a draw is forced after a polynomial number of non-jump moves{{cite journal | author = Aviezri S. Fraenkel | title = The complexity of checkers on an N x N board - preliminary report | journal = Proceedings of the 19th Annual Symposium on Computer Science | pages = 55–64 | year = 1978}}
• Dyson Telescope Game{{cite book | author=Erik D. Demaine | title=The complexity of the Dyson Telescope Puzzle | volume = Games of No Chance 3 | year=2009}}
• Cross Purposes{{cite journal | author = Robert A. Hearn | author-link = Bob Hearn | title=Amazons, Konane, and Cross Purposes are PSPACE-complete | journal = Games of No Chance 3 | year=2008}}
• Geography
• Two-player game version of Instant Insanity
• Ko-free Go{{cite journal | author = Lichtenstein | author2 = Sipser | title = Go is polynomial-space hard | journal = Journal of the Association for Computing Machinery | volume = 27 | issue=2 | pages = 393–401 | year = 1980 | doi = 10.1145/322186.322201| s2cid = 29498352 | doi-access = free }}
• Ladder capturing in Go[http://homepages.cwi.nl/~tromp/lad.ps Go ladders are PSPACE-complete] {{webarchive|url=https://web.archive.org/web/20070930044618/http://homepages.cwi.nl/~tromp/lad.ps |date=2007-09-30 }}
• Gomoku{{cite journal | author = Stefan Reisch | title = Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete) | journal = Acta Informatica | volume = 13 | pages = 59–66 | year = 1980 | doi=10.1007/bf00288536| s2cid = 21455572 }}
• Hex{{cite journal | author = Stefan Reisch | title = Hex ist PSPACE-vollständig (Hex is PSPACE-complete) | journal = Acta Informatica | issue = 15 | year = 1981 | pages = 167–191}}
• Konane
• Lemmings{{cite journal|last1=Viglietta|first1=Giovanni|title=Lemmings Is PSPACE-Complete|journal=Theoretical Computer Science|date=2015|volume=586|pages=120–134 |url=http://giovanniviglietta.com/papers/lemmings2.pdf|doi=10.1016/j.tcs.2015.01.055 |arxiv=1202.6581 |doi-access=free}}
• Node Kayles{{cite book | author=Erik D. Demaine | author2=Robert A. Hearn | author2-link = Bob Hearn | title=Playing Games with Algorithms: Algorithmic Combinatorial Game Theory | volume = Games of No Chance 3 | year=2009 | url=http://erikdemaine.org/papers/AlgGameTheory_GONC3/}}
• Poset Game{{cite book | last = Grier | first = Daniel | chapter = Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-Complete | arxiv = 1209.1750 | doi = 10.1007/978-3-642-39206-1_42 | title = Automata, Languages, and Programming | volume = 7965 | pages = 497–503 | series = Lecture Notes in Computer Science | date = 2013 | isbn = 978-3-642-39205-4 | s2cid = 13129445 }}
• Reversi{{cite journal | author = Shigeki Iwata and Takumi Kasai | title = The Othello game on an n*n board is PSPACE-complete | journal = Theoretical Computer Science | volume = 123 | issue = 2 | year = 1994 | pages = 329–340 | doi = 10.1016/0304-3975(94)90131-7| doi-access = free }}
• River Crossing
• Rush Hour{{cite arXiv|eprint=cs.CC/0205005|author1=Hearn|author1-link=Bob Hearn|author2=Demaine|title=PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation |year=2002}}
• Finding optimal play in Mahjong solitaireA. 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.
• Scrabble{{ cite journal | first1=Michael | last1=Lampis | first2 = Valia | last2 = Mitsou | first3 = Karolina | last3 = Sołtys | title = Scrabble is PSPACE-complete | journal = Journal of Information Processing | date = 2015 | url = https://www.jstage.jst.go.jp/article/ipsjjip/23/3/23_284/_article }}
• Sokoban
• Super Mario Bros.{{cite journal|last1=Demaine |first1=Erik D. |last2=Viglietta |first2=Giovanni |last3=Williams |first3=Aaron |title=Super Mario Bros. Is Harder/Easier than We Thought |journal=8th International Conference of Fun with Algorithms |date=June 2016 |url=https://dspace.mit.edu/bitstream/handle/1721.1/103079/Supermario%20Demaine.pdf?sequence=1&isAllowed=y}}
  Lay summary: {{cite web |last=Sabry |first=Neamat |date=Apr 28, 2020 |title=Super Mario Bros is Harder/Easier Than We Thought |website=Medium |url=https://medium.com/smith-hcv/super-mario-bros-is-harder-easier-than-we-thought-2d2c31f79bbb}}
• Black Pebble gameGilbert, 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.
• Black-White Pebble gamePhilipp Hertel and Toniann Pitassi: [http://www.cs.toronto.edu/~philipp/pages/papers/BWPebbling.pdf Black-White Pebbling is PSPACE-Complete] {{webarchive|url=https://web.archive.org/web/20110608053819/http://www.cs.toronto.edu/~philipp/pages/papers/BWPebbling.pdf |date=2011-06-08 }}
• Acyclic pebble gameTakumi Kasai, Akeo Adachi, and Shigeki Iwata: Classes of Pebble Games and Complete Problems, SIAM Journal on Computing, Volume 8, 1979, pages 574-586.
• One-player pebble game
• Token on acyclic directed graph games:

{{div col end}}

{{div col |colwidth=36em}}

• Quantified boolean formulas

• First-order logic of equalityK. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. {{isbn|90-277-2146-7}}
• Provability in intuitionistic propositional logic
• Satisfaction in modal logic S4
• First-order theory of the natural numbers under the successor operation
• First-order theory of the natural numbers under the standard order
• First-order theory of the integers under the standard order
• First-order theory of well-ordered sets
• First-order theory of binary strings under lexicographic ordering
• First-order theory of a finite Boolean algebra
• Stochastic satisfiability{{cite journal|author=Christos Papadimitriou |title=Games against Nature |doi=10.1016/0022-0000(85)90045-5 | journal=Journal of Computer and System Sciences |year=1985 |volume=31|issue=2|pages=288–301|author-link=Christos Papadimitriou |doi-access=free}}
• Linear temporal logic satisfiability and model checking{{cite journal|author=A.P.Sistla and Edmund M. Clarke|title=The complexity of propositional linear temporal logics|journal=Journal of the ACM|volume=32|issue=3|year=1985|doi=10.1145/3828.3837|pages=733–749|s2cid=47217193 |doi-access=free}}

{{div col end}}

Type inhabitation problem for simply typed lambda calculus

Integer circuit evaluation[https://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/6911/18589/00856751.pdf Integer circuit evaluation]

{{div col |colwidth=36em}}

• Word problem for linear bounded automata{{sfnp|Garey|Johnson|1979|loc=AL3}}
• Word problem for quasi-realtime automata{{sfnp|Garey|Johnson|1979|loc=AL4}}
• Emptiness problem for a nondeterministic two-way finite state automaton{{sfnp|Garey|Johnson|1979|loc=AL2}}Galil, Z. Hierarchies of Complete Problems. In Acta Informatica 6 (1976), 77-88.
• Equivalence problem for nondeterministic finite automata{{sfnp|Garey|Johnson|1979|loc=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.
• Word problem and emptiness problem for non-erasing stack automataJ. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, first edition, 1979.
• Emptiness of intersection of an unbounded number of deterministic finite automataD. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.

• A generalized version of Langton's Ant[http://sciencelinks.jp/j-east/article/200212/000020021202A0428168.php Langton's Ant problem] {{webarchive|url=https://web.archive.org/web/20070927225749/http://sciencelinks.jp/j-east/article/200212/000020021202A0428168.php |date=2007-09-27 }}, "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)
• Minimizing nondeterministic finite automataT. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on Computing, 22(6):1117–1141, December 1993.

{{div col end}}

{{div col |colwidth=36em}}

• Word problem for context-sensitive languageS.-Y. Kuroda, "Classes of languages and linear-bounded automata", Information and Control, 7(2): 207–223, June 1964.
• Intersection emptiness for an unbounded number of regular languages
• Regular Expression Star-Freeness {{cite web |last1=Bernátsky |first1=László |title=Regular Expression star-freeness is PSPACE-Complete |url=http://publicatio.bibl.u-szeged.hu/9528/1/Bernatsky_1997_ActaCybernetica.pdf |access-date=13 January 2021}}
• Equivalence problem for regular expressions
• Emptiness problem for regular expressions with intersection.
• Equivalence problem for star-free regular expressions with squaring.
• Covering for linear grammars{{sfnp|Garey|Johnson|1979|loc=AL12}}
• Structural equivalence for linear grammars{{sfnp|Garey|Johnson|1979|loc=AL13}}
• Equivalence problem for Regular grammars{{sfnp|Garey|Johnson|1979|loc=AL14}}
• Emptiness problem for ET0L grammars{{sfnp|Garey|Johnson|1979|loc=AL16}}
• Word problem for ET0L grammars{{sfnp|Garey|Johnson|1979|loc=AL19}}
• Tree transducer language membership problem for top down finite-state tree transducers{{sfnp|Garey|Johnson|1979|loc=AL21}}

{{div col end}}

{{div col |colwidth=36em}}

• succinct versions of many graph problems, with graphs represented as Boolean circuits,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. ordered binary decision diagramsJ. 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. 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
• Canadian traveller problem.{{cite conference | author=C.H. Papadimitriou |author2=M. Yannakakis | title=Shortest paths without a map | conference=Proc. 16th ICALP | book-title=Lecture Notes in Computer Science | volume=372 | publisher=Springer-Verlag | year=1989 | pages=610–620 }}
• Determining whether routes selected by the Border Gateway Protocol will eventually converge to a stable state for a given set of path preferencesAlex Fabrikant and Christos Papadimitriou. [http://www.cs.berkeley.edu/~alexf/papers/fp08.pdf The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond] {{webarchive|url=https://web.archive.org/web/20080905124129/http://www.cs.berkeley.edu/~alexf/papers/fp08.pdf |date=2008-09-05 }}. In SODA 2008.
• Deterministic constraint logic (unbounded){{cite book

| author1 = Erik D. Demaine

| author2 = Robert A. Hearn | author2-link = Bob Hearn

| title = Constraint Logic: A Uniform Framework for Modeling Computation as Games

| volume = Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (Complexity 2008)

| url = http://ccc08.cs.washington.edu/

| location = College Park, Maryland

|date=June 23–26, 2008

| pages = 149–162

}}

• Dynamic graph reliability.
• Graph coloring game{{cite journal|last1=Costa|first1=Eurinardo|last2=Pessoa|first2=Victor Lage |last3=Soares|first3=Ronan|last4=Sampaio|first4=Rudini|date=2020|title=PSPACE-completeness of two graph coloring games |journal=Theoretical Computer Science|volume=824-825|pages=36–45 |doi=10.1016/j.tcs.2020.03.022 |s2cid=218777459}}
• Node Kayles game and clique-forming game:{{cite journal|last1=Schaefer|first1=Thomas J. |date=1978|title=On the complexity of some two-person perfect-information games|journal=Journal of Computer and System Sciences|volume=16|issue=2 |pages=185–225|doi=10.1016/0022-0000(78)90045-4|doi-access=free}} 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)

{{div col end}}

{{div col |colwidth=36em}}

• Finite horizon POMDPs (Partially Observable Markov Decision Processes).{{cite journal | author=C.H. Papadimitriou |author2=J.N. Tsitsiklis | title=The complexity of Markov Decision Processes | journal= Mathematics of Operations Research| volume=12 | number=3 | year=1987| pages=441–450 | doi=10.1287/moor.12.3.441| url=http://dspace.mit.edu/bitstream/1721.1/2893/1/P-1479-13685602.pdf|hdl=1721.1/2893 | hdl-access=free }}
• Hidden Model MDPs (hmMDPs).{{cite conference | author=I. Chades |author2=J. Carwardine |author3=T.G. Martin |author4=S. Nicol |author5=R. Sabbadin |author6=O. Buffet | title=MOMDPs: A Solution for Modelling Adaptive Management Problems | conference=AAAI'12 | year=2012}}
• Dynamic Markov process.
• Detection of inclusion dependencies in a relational database{{cite journal |author=Casanova, Marco A. |display-authors=et al |year=1984 |title=Inclusion Dependencies and Their Interaction with Functional Dependencies |journal=Journal of Computer and System Sciences |volume=28 |pages=29–59 |doi=10.1016/0022-0000(84)90075-8| doi-access=free}}
• Computation of any Nash equilibrium of a 2-player normal-form game, that may be obtained via the Lemke–Howson algorithm.{{cite conference | author= P.W. Goldberg and C.H. Papadimitriou and R. Savani | title=The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke–Howson Solutions | conference=Proc. 52nd FOCS | publisher=IEEE | year=2011 | pages=67–76 }}
• The Corridor Tiling Problem: given a set of Wang tiles, a chosen tile $T\_0$ and a width $n$ given in unary notation, is there any height $m$ such that an $n\backslash times\; m$ rectangle can be tiled such that all the border tiles are $T\_0$?{{cite encyclopedia |author= Maarten Marx | title=Complexity of Modal Logic | encyclopedia=Handbook of Modal Logic |editor1=Patrick Blackburn |editor2= Johan F.A.K. van Benthem|editor3 = Frank Wolter| publisher=Elsevier |year=2007 |page=170}}{{cite conference| title= Complexity of solvable cases of the decision problem for the predicate calculus| author=Lewis, Harry R.| conference=19th Annual Symposium on Foundations of Computer Science| pages= 35–47| year= 1978| publisher=IEEE}}

{{div col end}}

• List of NP-complete problems

• {{cite book

| last1 = Garey

| first1 = M.R.

| author-link = Michael Garey

| last2=Johnson |first2=D.S. |author-link2=David S. Johnson

| title = Computers and Intractability: A Guide to the Theory of NP-Completeness

| year = 1979

| publisher = W.H. Freeman

| location = New York

| isbn = 978-0-7167-1045-5

| title-link = Computers and Intractability: A Guide to the Theory of NP-Completeness

}}

• [http://www.ics.uci.edu/~eppstein/cgt/hard.html Eppstein's page on computational complexity of games]
• [https://arxiv.org/abs/math/9409225 The Complexity of Approximating PSPACE-complete problems for hierarchical specifications]

{{DEFAULTSORT:PSPACE-complete problems}}

Category:Mathematics-related lists

Category:Lists of problems