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 (polynomial space) and if every other problem that can be solved in polynomial space can b ...

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 of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

s. This list is in no way comprehensive.

Games and puzzles

Generalized versions of: *

Amazons In Greek mythology, the Amazons (Ancient Greek: Ἀμαζόνες ''Amazónes'', singular Ἀμαζών ''Amazōn'', via Latin ''Amāzon, -ŏnis'') are portrayed in a number of ancient epic poems and legends, such as the Labours of Hercules, ...

* Atomix *

Checkers Checkers (American English), also known as draughts (; British English), is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces. Checkers ...

Dyson Telescope Game Dyson may refer to: * Dyson (surname), people with the surname Dyson * Dyson (company), a Singaporean multinational home appliances company founded by James Dyson * Dyson (crater), a crater on the Moon * Dyson (operating system), a Unix general-pur ...

Cross Purposes ''Cross Purposes'' is the seventeenth studio album by English rock band Black Sabbath, released through I.R.S. Records on 26 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 Greek: , ''geographia''. Combination of Greek words ‘Geo’ (The Earth) and ‘Graphien’ (to describe), literally "earth description") is a field of science devoted to the study of the lands, features, inhabitants, and ...

* 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 board game. It is traditionally played with Go pieces (black and white stones) on a Go board. It is played using a 15×15 board while in the past a 19×19 board was standard. Be ...

* 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 include ...

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 There are sixty-four identical game pieces ...

* River Crossing *

Rush Hour A rush hour (American English, British English) or peak hour (Australian 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 every weekday: on ...

* 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 ...

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 is ...

26:2 (1997) 369-400. *

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 December 1982. Gameplay The game is played on a ...

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

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 ve ...

games: * Annihilation * Hit * Capture * Edge Blocking * Target * Pursuit

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 where every variable is quantified ( ...

s *

First-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...

equality Equality may refer to: Society * Political equality, in which all members of a society are of equal standing ** Consociationalism, in which an ethnically, religiously, or linguistically divided state functions by cooperation of each group's elite ...

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

D. Reidel D. Reidel was an academic publishing company based in Dordrecht established in the 1960s which was independent until the 1990s. History Reidel was established in the 1960s, with a focus on publishing research in physics. Reidel himself had been t ...

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

First-order theory First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantif ...

of the

natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...

s under the successor operation *

of the

s under the standard order *

of the

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...

s under the standard order *

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

s *

binary string In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable. The latter may allow its elements to be mutated and the length changed, or it may be fixed (after creation). ...

s 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 variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in e ...

* Stochastic satisfiability * Linear temporal logic satisfiability and model checking * Temporal logic of 2D Minkowski Spacetime.

Lambda calculus

Type inhabitation problem 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 In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of Turing machine. Operation A linear bounded automaton is a nondeterministic Turing machine that satisfies the following three ...

* 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 * 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 one of the four types of grammars in the Chomsky hierarc ...

* 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 In theoretical computer science and formal language theory, the equivalence problem is the question of determining, given two representations of formal languages, whether they denote the same formal language. The complexity and decidability of thi ...

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 search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...

s *

for

s with intersection. *

for star-free

s with squaring. * Covering for

linear grammar In computer science, a linear grammar is a context-free grammar that has at most one nonterminal in the right-hand side of each of its productions. A linear language is a language generated by some linear grammar. Example An example of a linear gr ...

s * Structural equivalence for

s *

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 Automation describes a wide range of technologies that reduce human intervention in processes, namely by predetermining decision criteria, subprocess relationships, and related actions, as well as embodying those predeterminations in machines ...

. ** 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. * 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 makes ...

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 coloring ...

* 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, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...

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 identifying ...

, that may be obtained via the

Lemke–Howson algorithm The Lemke–Howson algorithm is an algorithm that computes a Nash equilibrium of a bimatrix game, named after its inventors, Carlton E. Lemke and J. T. Howson. It is said to be "the best known among the combinatorial algorithms for finding a Nash ...

. * 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, are a class of formal systems. They are modelled visually by square tiles with a color on each side. A set of such tiles is selected, an ...

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