Here are some of the more commonly known problems that are

PSPACE-complete In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (PSPACE, polynomial space) and if every other problem that can be solved in polynomial sp ...

when expressed as

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...

s. This list is in no way comprehensive.

Games and puzzles

Generalized versions of: *

Amazons The Amazons (Ancient Greek: ', singular '; in Latin ', ') were a people in Greek mythology, portrayed in a number of ancient epic poems and legends, such as the Labours of Hercules, Labours of Heracles, the ''Argonautica'' and the ''Iliad''. ...

* Atomix *

Checkers Checkers (American English), also known as draughts (; English in the Commonwealth of Nations, Commonwealth English), is a group of Abstract strategy game, strategy board games for two players which involve forward movements of uniform game ...

if a draw is forced after a polynomial number of non-jump moves * Dyson Telescope Game *

Cross Purposes ''Cross Purposes'' is the seventeenth studio album by English rock band Black Sabbath, released through I.R.S. Records on 31 January 1994. The album marked the return of Tony Martin as the band's lead vocalist, after the second departure of Ron ...

Geography Geography (from Ancient Greek ; combining 'Earth' and 'write', literally 'Earth writing') is the study of the lands, features, inhabitants, and phenomena of Earth. Geography is an all-encompassing discipline that seeks an understanding o ...

* Two-player game version of Instant Insanity * Ko-free Go * Ladder capturing in GoGo ladders are PSPACE-complete
*

Gomoku ''Gomoku'', also called ''five in a row'', is an Abstract strategy game, abstract strategy board game. It is traditionally played with Go (game), Go pieces (black and white stones) on a 15×15 Go board while in the past a 19×19 board was standa ...

* Hex * Konane *

Lemmings A lemming is a small rodent, usually found in or near the Arctic in tundra biomes. Lemmings form the subfamily Arvicolinae (also known as Microtinae) together with voles and muskrats, which form part of the superfamily Muroidea, which also incl ...

Node Kayles In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex). Node may refer to: In mathematics *Vertex (graph theory), a vertex in a mathematical graph *Vertex (geometry), a point where two or more curves, lines, ...

* Poset Game *

Reversi Reversi is a strategy board game for two players, played on an 8×8 uncheckered board. It was invented in 1883. ''Othello'', a variant with a fixed initial setup of the board, was patented in 1971. Basics Two players compete, using 64 identi ...

* River Crossing *

Rush Hour A rush hour (American English, British English) or peak hour (Australian English, Indian English) is a part of the day during which traffic congestion on roads and crowding on public transport is at its highest. Normally, this happens twice e ...

* Finding optimal play in

Mahjong solitaire Mahjong solitaire (also known as Shanghai solitaire, electronic or computerized mahjong, solitaire mahjong or simply mahjong) is a single-player matching game that uses a set of mahjong tiles rather than cards. It is more commonly played on ...

A. Condon, J. Feigenbaum, C. Lund, and P. Shor, Random debaters and the hardness of approximating stochastic functions,

SIAM Journal on Computing The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation i ...

26:2 (1997) 369-400. *

Scrabble ''Scrabble'' is a word game in which two to four players score points by placing tiles, each bearing a single letter, onto a Board game, game board divided into a 15×15 grid of squares. The tiles must form words that, in crossword fashion, re ...

Sokoban is a puzzle video game in which the player pushes boxes around in a warehouse, trying to get them to storage locations. The game was designed in 1981 by Hiroyuki Imabayashi and first published in Japan in 1982 by his company Thinking Rabbit for ...

Super Mario Bros. is a 1985 Platformer, platform game developed and published by Nintendo for the Nintendo Entertainment System (NES). It is the successor to the 1983 arcade game ''Mario Bros.'' and the first game in the ''Super Mario'' series. It was origi ...

Lay summary: * Black

Pebble game In mathematics and computer science, a pebble game is a type of mathematical game played by placing "pebbles" or "markers" on a directed acyclic graph according to certain rules: * A given step of the game consists of either placing a pebble on an ...

* Black-White

* Acyclic

pebble game In mathematics and computer science, a pebble game is a type of mathematical game played by placing "pebbles" or "markers" on a directed acyclic graph according to certain rules: * A given step of the game consists of either placing a pebble on an ...

Takumi 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

* Token on

acyclic directed graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ...

games:

Logic

Quantified boolean formula In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas. A (fully) quantified Boolean formula is a formula in quantified propositional logic (also known as Second-order propos ...

s *

First-order logic First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over ...

equality Equality generally refers to the fact of being equal, of having the same value. In specific contexts, equality may refer to: Society * Egalitarianism, a trend of thought that favors equality for all people ** Political egalitarianism, in which ...

K. Wagner and G. Wechsung. ''Computational Complexity''.

D. Reidel D. Reidel was an academic publishing company based in Dordrecht established in the 1960s. History Reidel was established in the 1960s, with a focus on publishing research in physics. David Reidel himself had been trained under an ex-Elsevier man ...

Publishing Company, 1986. * Provability in intuitionistic propositional logic * Satisfaction in modal logic S4 *

First-order theory In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language. In most scenarios a deductive system is first understood from context, giving rise to a formal system that combines the language with deduct ...

of the

natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...

s under the successor operation *

of the

s under the standard order *

of the

integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

s under the standard order *

well-ordered set In mathematics, a well-order (or well-ordering or well-order relation) on a set is a total ordering on with the property that every non-empty subset of has a least element in this ordering. The set together with the ordering is then called a ...

s *

of binary strings under

lexicographic order In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ...

ing *

of a finite

Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...

* Stochastic satisfiability *

Linear temporal logic In logic, linear temporal logic or linear-time temporal logic (LTL) is a modal logic, modal temporal logic with modalities referring to time. In LTL, one can encode formula (logic), formulae about the future of path (graph theory), paths, e.g., a c ...

satisfiability and model checking

Lambda calculus

Type inhabitation problem In type theory, a branch of mathematical logic, in a given typed calculus, the type inhabitation problem for this calculus is the following problem: given a type \tau and a typing environment \Gamma, does there exist a \lambda-term M such that \Gam ...

for simply typed lambda calculus

Automata and language theory

Circuit theory

Integer circuit In computational complexity theory, an integer circuit is a circuit model of computation in which inputs to the circuit are sets of integers and each gate of the circuit computes either a set operation or an arithmetic operation on its input sets. ...

evaluationInteger circuit evaluation
/ref>

Automata theory

* Word problem for linear bounded automata * Word problem for quasi-realtime automata *

Emptiness problem In theoretical computer science and formal language theory, a formal language is empty if its set of valid sentences is the empty set. The emptiness problem is the question of determining whether a language is empty given some representation of it, ...

for a nondeterministic two-way finite state automatonGalil, Z. ''Hierarchies of Complete Problems''. In Acta Informatica 6 (1976), 77-88. * Equivalence problem for

nondeterministic finite automata In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if * each of its transitions is ''uniquely'' determined by its source state and input symbol, and * reading an input symbol is required for each state tr ...

* Word problem and emptiness problem for non-erasing stack automata * 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 Langton's ant is a two-dimensional Turing machine with a very simple set of rules but complex emergent behavior. It was invented by Chris Langton in 1986 and runs on a square lattice of black and white cells. The idea has been generalized in ...

* Minimizing

Formal languages

* Word problem for

context-sensitive language In formal language theory, a context-sensitive language is a language that can be defined by a context-sensitive grammar (and equivalently by a noncontracting grammar). Context-sensitive is known as type-1 in the Chomsky hierarchy of formal langu ...

* Intersection emptiness for an unbounded number of

regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...

s * Regular Expression Star-Freeness * Equivalence problem for

regular expression A regular expression (shortened as regex or regexp), sometimes referred to as rational expression, is a sequence of characters that specifies a match pattern in text. Usually such patterns are used by string-searching algorithms for "find" ...

s *

for

s with intersection. * Equivalence problem for star-free

s with squaring. * Covering for linear grammars * Structural equivalence for linear grammars * Equivalence problem for

Regular grammar In theoretical computer science and formal language theory, a regular grammar is a grammar that is ''right-regular'' or ''left-regular''. While their exact definition varies from textbook to textbook, they all require that * all production rules ...

s *

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 In computer science, a binary decision diagram (BDD) or branching program is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. Un ...

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, sometimes denoted as simply AI planning, is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots ...

. ** 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 In computer science and graph theory, the Canadian traveller problem (CTP) is a generalization of the shortest path problem to graphs that are partially observable. In other words, a "traveller" on a given point on the graph cannot see the full g ...

. * Determining whether routes selected by the

Border Gateway Protocol Border Gateway Protocol (BGP) is a standardized exterior gateway protocol designed to exchange routing and reachability information among autonomous systems (AS) on the Internet. BGP is classified as a path-vector routing protocol, and it ...

will eventually converge to a stable state for a given set of path preferences * Deterministic constraint logic (unbounded) * Dynamic graph reliability. *

Graph coloring game The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a colori ...

* Node Kayles game and clique-forming game: 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)

Others

* Finite horizon POMDPs (Partially Observable Markov Decision Processes). * Hidden Model MDPs (hmMDPs). * Dynamic Markov process. * Detection of inclusion dependencies in a relational database * Computation of any

Nash equilibrium In game theory, the Nash equilibrium is the most commonly used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed) ...

of a 2-player

normal-form game In game theory, normal form is a description of a ''game''. Unlike extensive form, normal-form representations are not graphical ''per se'', but rather represent the game by way of a matrix. While this approach can be of greater use in identifyi ...

, that may be obtained via the Lemke–Howson algorithm. * The Corridor Tiling Problem: given a set of

Wang tile Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, is a class of formal systems. They are modeled visually by square tiles with a color on each side. A set of such tiles is selected, and ...

s, a chosen tile

T_0

and a width

n

given in unary notation, is there any height

m

such that an

n\times m

rectangle can be tiled such that all the border tiles are

T_0

Notes

References

*
Eppstein's page on computational complexity of games

The Complexity of Approximating PSPACE-complete problems for hierarchical specifications
{{DEFAULTSORT:PSPACE-complete problems Mathematics-related lists Lists of problems

Games and puzzles

Logic

Lambda calculus

Automata and language theory

Circuit theory

Automata theory

Formal languages

Graph theory

Others

See also

Notes

References