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 Go[Go 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 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 ...
* 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 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 ...
[
* 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 ...
of 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
* 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 standard order
* 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 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
* 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 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
* 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 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
* 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 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.
...
evaluation[Integer 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 automaton[Galil, 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 automata[D. 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 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 ...
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[
* ]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 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 with intersection.[
* ]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 star-free 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 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 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
* 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 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
* 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 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 and a width given in unary notation, is there any height such that an rectangle can be tiled such that all the border tiles are ?
See also
* List of NP-complete problems
This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are hundreds of such problems known, this list is in no way comprehensive. Many problems of this type can be found in . ...
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