List of PSPACE-complete problems

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:

• 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

• 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

Type inhabitation problem for simply typed lambda calculus

Automata and language theory

Circuit theory

Integer circuit evaluation^[24]

Automata theory

• 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

• 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

• 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

• 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 ${\displaystyle T_{0}}$ and a width ${\displaystyle n}$ given in unary notation, is there any height ${\displaystyle m}$ such that an ${\displaystyle n\times m}$ rectangle can be tiled such that all the border tiles are ${\displaystyle T_{0}}$?^[54][55]

See also

• List of NP-complete problems