In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, a
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 wheth ...
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 be
transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
Formal definition
If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...
, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.
Problems known to be PSPACE-complete include determining properties of
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" ...
s and
context-sensitive grammars, determining the truth of
quantified Boolean formulas, step-by-step changes between solutions of combinatorial optimization problems, and many puzzles and games.
Theory
A problem is defined to be PSPACE-complete if it can be solved using a polynomial amount of memory (it belongs to PSPACE) and every problem in PSPACE can be transformed in polynomial time into an equivalent instance of the given problem.
The PSPACE-complete problems are widely suspected to be outside the more famous complexity classes
P (polynomial time) and
NP (non-deterministic polynomial time), but that is not known. It is known that they lie outside of the class
NC, a class of problems with highly efficient
parallel algorithm
In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is an algorithm which can do multiple operations in a given time. It has been a tradition of computer science to describe serial algorithms in abstract machin ...
s, because problems in NC can be solved in an amount of space polynomial in the
logarithm
In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 of ...
of the input size, and the class of problems solvable in such a small amount of space is strictly contained in PSPACE by the
space hierarchy theorem In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. For exampl ...
.
The transformations that are usually considered in defining PSPACE-completeness are polynomial-time
many-one reduction
In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem L_1 into instances of a second decision problem L_2 where the insta ...
s, transformations that take a single instance of a problem of one type into an equivalent single instance of a problem of a different type. However, it is also possible to define completeness using
Turing reduction
In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to s ...
s, in which one problem can be solved in a polynomial number of calls to a subroutine for the other problem. It is not known whether these two types of reductions lead to different classes of PSPACE-complete problems. Other types of reductions, such as many-one reductions that always increase the length of the transformed input, have also been considered.
A version of the
Berman–Hartmanis conjecture
In structural complexity theory, the Berman–Hartmanis conjecture is an unsolved conjecture named after Leonard C. Berman and Juris Hartmanis that states that all NP-complete languages look alike, in the sense that they can be related to each ot ...
for PSPACE-complete sets states that all such sets look alike, in the sense that they can all be transformed into each other by polynomial-time
bijections.
Examples
Formal languages
Given a
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" ...
, determining whether it generates every string over its alphabet is PSPACE-complete.
The first known PSPACE-complete problem was the
word problem for
deterministic context-sensitive grammars. In the word problem for context-sensitive grammars, one is given a set of grammatical transformations which can increase, but cannot decrease, the length of a sentence, and wishes to determine if a given sentence could be produced by these transformations. The technical condition of "determinism" (implying roughly that each transformation makes it obvious that it was used) ensures that this process can be solved in polynomial space, and showed that every (possibly non-deterministic) program computable in
linear space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
could be converted into the parsing of a context-sensitive grammar, in a way which preserves determinism. In 1970,
Savitch's theorem showed that PSPACE is closed under nondeterminism, implying that even non-deterministic context-sensitive grammars are in PSPACE.
Logic
A standard PSPACE-complete problem, used in many other PSPACE-completeness results, is the
quantified Boolean formula problem, a generalization of the
Boolean satisfiability problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
. The quantified Boolean formula problem takes as input a Boolean expression, with all of its variables quantified either universally or existentially, for example:
The output of the problem is the value of the quantified expression. Finding this value is PSPACE-complete.
Reconfiguration
Reconfiguration
In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or connectivity of state spaces.
Types of problems
Here, a state space is a discrete set of configurations of a s ...
problems concern the connectivity of a
state space
A state space is the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory.
For instance, the to ...
of solutions to a combinatorial problem. For instance, testing whether two 4-colorings of a graph can be connected to each other by moves that change the color of one vertex at a time, maintaining at each step a valid 4-coloring, is PSPACE-complete, even though the same problem for 3-colorings can be solved in polynomial time. Another family of reconfiguration problems, used similarly to quantified Boolean formulas as the basis for PSPACE-completeness proofs of many other problems in this area, involve
nondeterministic constraint logic
In theoretical computer science, nondeterministic constraint logic is a combinatorial system in which an orientation is given to the edges of a weighted undirected graph, subject to certain constraints. One can change this orientation by steps in ...
, in which the states are
orientations
''Orientations'' is a bimonthly print magazine published in Hong Kong and distributed worldwide since 1969. It is an authoritative source of information on the many and varied aspects of the arts of East and Southeast Asia, the Himalayas, the India ...
of a constraint graph subject to certain constraints on how many edges must be oriented inwards at each vertex, and in which the moves from state to state reverse the orientation of a single edge.
Puzzles and games
The quantified Boolean formula problem can be interpreted as a game by two players, a verifier and a falsifier. The players make moves that fill in values for the quantified variables, in the order they are nested, with the verifier filling in existentially quantified variables and the falsifier filling in universally quantified variables; the game is won by the verifier if the filled-in formula becomes true, and by the falsifier otherwise. A quantified formula is true if and only if the verifier has a winning strategy. Similarly, the problem of determining the winner or loser of many other
combinatorial games turns out to be PSPACE-complete. Examples of games that are PSPACE-complete (when
generalized so that they can be played on an
board) are the games
Hex and
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 ...
. Some other generalized games, such as
chess
Chess is a board game for two players, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to dist ...
,
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 ...
(draughts), and
Go are
EXPTIME-complete
In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2''p''(''n'')) time, w ...
because a game between two perfect players can be very long, so they are unlikely to be in PSPACE. But they will become PSPACE-complete if a polynomial bound on the number of moves is enforced.
It is also possible for puzzles played by a single player to be PSPACE-complete. These often can be interpreted as reconfiguration problems, and include the solitaire games
Rush Hour,
Mahjong,
Atomix and
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 ...
, and the
mechanical computer
A mechanical computer is a computer built from mechanical components such as levers and gears rather than electronic components. The most common examples are adding machines and mechanical counters, which use the turning of gears to increment out ...
Turing Tumble
''Turing Tumble'' is a game and demonstration of logic gates via mechanical computer. Named after Alan Turing, the game itself could (abstractly) duplicate the processes of any computer whatsoever if the game field itself were sufficiently large. ...
.
PSPACE-completeness is based on complexity as a function of the input size
, in the limit as
grows without bound. Puzzles or games with a bounded number of positions such as chess on a conventional
board cannot be PSPACE-complete, because they could be solved in constant time and space using a very large
lookup table. To formulate PSPACE-complete versions of these games, they must be modified in a way that makes their number of positions unbounded, such as by playing them on an
board instead. In some cases, such as for chess, these extensions are artificial.
References
Further reading
*
{{ComplexityClasses
Complexity classes