Here are some of the more commonly known problems that are PSPACE-complete

PSPACE-complete

In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...

 when expressed as decision problem

Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...

s. This list is in no way comprehensive.

Games and puzzles

Generalized

Generalized game

In computational complexity theory, a generalized game is a game that has been generalized so that it can be played on a board of any size. For example, generalized chess is the game of chess played on an n-by-n board, with 2n pieces on each side.Complexity theory studies the asymptotic difficulty...

 versions of:
Amazons
· Atomix

Atomix (computer game)

Atomix is a transport puzzle video game developed by Günter Krämer and published by Thalion Software, released for the Commodore Amiga and other personal computers in late 1990...

· Checkers 
· Dyson Telescope Game 
· Cross Purposes 
· Geography

Generalized Geography

In computational complexity theory, generalized geography is a problem that can be proven to be PSPACE-complete.-Introduction:Geography is a children's game, which is good for a long car trip, where players take turns naming cities from anywhere in the world. Each city chosen must begin with the...

· Ko-free Go 
· Ladder capturing in Go

Ladder (Go)

In the game of Go, a is a basic sequence of moves in which an attacker pursues a group in atari in a zig-zag pattern across the board. If there are no intervening stones, the group will hit the edge of the board and be captured....

· Gomoku
· Hex
· Konane

Konane

Kōnane is a two-player abstract strategy board game from Hawaii. It was invented by the ancient Hawaiian Polynesians. The game begins with all the counters laid out on the board in an alternating pattern of black and white. Players then hop over one another's pieces capturing them similar to...

 
· Node Kayles
· Reversi

Reversi

Reversi is a board game involving abstract strategy and played by two players on a board with 8 rows and 8 columns and a set of distinct pieces for each side. Pieces typically are disks with a light and a dark face, each face belonging to one player...

· River Crossing
· Rush Hour

Rush Hour (board game)

Rush Hour is a sliding block puzzle invented by Nob Yoshigahara in the late 1970s and first sold in the United States in 1996. It is manufactured by ThinkFun ....

· Finding optimal play in Mahjong solitaire

Mahjong solitaire

Mahjong solitaire is a solitaire matching game that uses a set of Mahjong tiles rather than cards. It is also known as Shanghai solitaire, electronic or computerized mahjong, MahJong solitaire, solitaire Mahjong and, erroneously, as Mahjong...

· Sokoban

Sokoban

is a type of transport puzzle, in which the player pushes boxes or crates around in a warehouse, trying to get them to storage locations. The puzzle is usually implemented as a video game....

· Black Pebble game

Pebble game

In mathematics and computer science, a pebble game is a type of mathematical game played by moving "pebbles" or "markers" on a directed graph. A variety of different pebble games exist....

 
· Black-White Pebble game

Pebble game

In mathematics and computer science, a pebble game is a type of mathematical game played by moving "pebbles" or "markers" on a directed graph. A variety of different pebble games exist....

· Acyclic pebble game

Pebble game

In mathematics and computer science, a pebble game is a type of mathematical game played by moving "pebbles" or "markers" on a directed graph. A variety of different pebble games exist....

· One-player pebble game

Pebble game

In mathematics and computer science, a pebble game is a type of mathematical game played by moving "pebbles" or "markers" on a directed graph. A variety of different pebble games exist....

· Token on acyclic directed graph games: Annihilation; Hit; Capture; Edge Blocking; Target; Pursuit

Logic

Quantified boolean formulas

· First-order logic

First-order logic

First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

 of equality 
· Satisfaction in intuitionistic propositional logic

Intuitionistic logic

Intuitionistic logic, or constructive logic, is a symbolic logic system differing from classical logic in its definition of the meaning of a statement being true. In classical logic, all well-formed statements are assumed to be either true or false, even if we do not have a proof of either...

· Satisfaction in modal logic S4

Modal logic

Modal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is...

· First-order theory of the natural number

Natural number

In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s under the successor operation
· First-order theory of the natural number

Natural number

In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s under the standard order
· First-order theory of the integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

s 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
· Linear temporal logic

Linear temporal logic

In logic, Linear temporal logic is a modal temporal logic with modalities referring to time. In LTL, one can encode formulae about the future of paths such as that a condition will eventually be true, that a condition will be true until another fact becomes true, etc. It is a fragment of the more...

 satisfiability and model checking

Automata theory

Word problem for linear bounded automata
· Word problem for quasi-realtime automata
· Emptiness problem for a nondeterministic two-way finite state automaton 

· Equivalence problem for nondeterministic finite automata
· Word problem and emptiness problem for non-erasing stack automata
· Deterministic finite automata intersection emptiness

· A generalized version of Langton's Ant

Langton's ant

Langton's ant is a two-dimensional Turing machine with a very simple set of rules but complicated emergent behavior. It was invented by Chris Langton in 1986 and runs on a square lattice of black and white cells. The universality of Langton's ant was proven in 2000...

· Minimizing nondeterministic finite automata

Formal languages

Word problem for Context-sensitive language

Context-sensitive language

In theoretical computer science, a context-sensitive language is a formal language that can be defined by a context-sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy...

 
· Regular language

Regular language

In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....

 intersection
· Regular expression

Regular expression

In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...

 star freeness
· Equivalence problem for regular expression

Regular expression

In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...

s
· Emptiness problem for regular expression

Regular expression

In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...

s with intersection.
· Equivalence problem for star-free regular expression

Regular expression

In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...

s with squaring.
· Covering for linear grammar

Linear grammar

In computer science, a grammar is linear if it is context-free and all of its productions' right hand sides have at most one nonterminal.A linear language is a language generated by some linear grammar.-Example:...

s
· Structural equivalence for linear grammar

Linear grammar

In computer science, a grammar is linear if it is context-free and all of its productions' right hand sides have at most one nonterminal.A linear language is a language generated by some linear grammar.-Example:...

s
· Equivalence problem for Regular grammar

Regular grammar

In theoretical computer science, a regular grammar is a formal grammar that describes a regular language.- Strictly regular grammars :A right regular grammar is a formal grammar such that all the production rules in P are of one of the following forms:# B → a - where B is a non-terminal in N and...

s
· Emptiness problem for ET0L grammars
· Word problem for ET0L grammars
· Tree transducer language membership problem for top down finite-state tree transducers

Graph Theory

• succinct versions of many graph problems, with graphs represented as Boolean circuits , ordered Binary Decision Diagram
  Binary decision diagram
  In the field of computer science, a binary decision diagram or branching program, like a negation normal form or a propositional directed acyclic graph , is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed...
  
  s 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
    Automated planning and scheduling
    Automated planning and scheduling is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles. Unlike classical control and classification problems, the solutions are...
    
    .
  • planarity of succinct graphs
  • acyclicity of succinct graphs
  • connectedness of succinct graphs
  • existence of Eulerian paths in a succinct graph
• Canadian Traveller Problem
  Canadian traveller problem
  In computer science and graph theory, the Canadian Traveller Problem is a generalization of the shortest path problem to graphs that are partially observable...
  
  .
• Determining whether routes selected by the Border Gateway Protocol
  Border Gateway Protocol
  The Border Gateway Protocol is the protocol backing the core routing decisions on the Internet. It maintains a table of IP networks or 'prefixes' which designate network reachability among autonomous systems . It is described as a path vector protocol...
  
   will eventually converge to a stable state for a given set of path preferences
• Dynamic graph reliability.
• Deterministic Constraint Logic (unbounded)
• Nondeterministic Constraint Logic (unbounded)
• Bounded two-player Constraint Logic