PSPACE-complete
Encyclopedia
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 (see complete (complexity)
). The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, because a solution to any one such problem could easily be used to solve any other problem in PSPACE. These problems are widely suspected to be outside of the more famous complexity classes P
and NP
, but that is not known. It is known that they lie outside of the small class NC
, since NC is contained in PolyL
= DSPACE((log n)O(1))), which is strictly contained in PSPACE by the space hierarchy theorem
.
for deterministic context-sensitive grammar
s. 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 S.-Y. Kuroda
's 1964 work "Classes of languages and linear-bounded automata" showed that any (possibly non-deterministic) program computable in linear space 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.
But the archetypal PSPACE-complete problem is generally taken to be the quantified Boolean formula problem (usually abbreviated to QBF or TQBF; the T stands for "true"), a generalization of the first known NP-complete
problem, the Boolean satisfiability problem
(SAT). The satisfiability problem is the problem of whether there are assignments of truth values to variables that make a Boolean expression true. For example, one instance of SAT would be the question of whether the following is true:
The quantified Boolean formula problem differs in allowing both universal and existential quantification over the values of the variables:
The proof that QBF is a PSPACE-complete problem is essentially a restatement of the proof of Savitch's theorem
in the language of logic, and is a bit more technical.
Notice that the NP-complete problem resembles a typical puzzle: is there some way to plug in values that solves the problem? The PSPACE-complete problem resembles a game: is there some move I can make, such that for all moves my opponent might make, there will then be some move I can make to win? The question alternates existential and universal quantifiers. Not surprisingly, many puzzles turn out to be NP-complete, and many games turn out to be PSPACE-complete.
Examples of games that are PSPACE-complete (when generalized
so that they can be played on an n × n board) are the games hex
and Reversi
and the solitaire games Rush Hour
, Mahjong
, Atomix
, and Sokoban
. Some other generalized games, such as chess
, checkers (draughts), and Go
are EXPTIME-complete 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.
Note that the definition of PSPACE-completeness is based on asymptotic complexity: the time it takes to solve a problem of size n, in the limit as n grows without bound. That means a game like checkers (which is played on an 8 × 8 board) could never be PSPACE-complete (in fact, they can be solved in constant time and space using a very large lookup table
). That is why all the games were modified by playing them on an n × n board instead; in some cases, such as for Chess, these extensions are somewhat artificial and subjective.
for more games whose completeness for PSPACE or other complexity classes has been determined.
R, determining whether it generates all strings (i.e., L(R) = Σ*) is PSPACE-complete.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, a 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...
is PSPACE-complete if it is in the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
, and every problem in PSPACE can be reduced to it in polynomial time (see complete (complexity)
Complete (complexity)
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class...
). The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, because a solution to any one such problem could easily be used to solve any other problem in PSPACE. These problems are widely suspected to be outside of the more famous complexity classes P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
and NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
, but that is not known. It is known that they lie outside of the small class NC
NC (complexity)
In complexity theory, the class NC is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem is in NC if there exist constants c and k such that it can be solved in time O using O parallel processors...
, since NC is contained in PolyL
PolyL
In computational complexity theory, PolyL is the complexity class of decision problems that can be solved on a deterministic Turing machine whose required space is bounded by some polylogarithmic function in the size of the input...
= DSPACE((log n)O(1))), which is strictly contained in PSPACE by the space hierarchy theorem
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 more space, subject to certain conditions. For example, a deterministic Turing machine can solve more decision problems...
.
Discussion
The first known PSPACE-complete problem was the word problemWord problem
The term word problem has several meanings:* word problem is a type of textbook problem designed to help students apply abstract mathematical concepts to "real-world" situations...
for deterministic context-sensitive grammar
Context-sensitive grammar
A context-sensitive grammar is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols...
s. 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 S.-Y. Kuroda
S.-Y. Kuroda
, aka S.-Y. Kuroda, was Professor Emeritusand Research Professor of Linguistics at the University of California, San Diego.Although a pioneer in the application of Chomskyan generative syntax to...
's 1964 work "Classes of languages and linear-bounded automata" showed that any (possibly non-deterministic) program computable in linear space could be converted into the parsing of a context-sensitive grammar, in a way which preserves determinism.
In 1970, Savitch's theorem
Savitch's theorem
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, states that for any function ƒ ≥ log,...
showed that PSPACE is closed under nondeterminism, implying that even non-deterministic context-sensitive grammars are in PSPACE.
But the archetypal PSPACE-complete problem is generally taken to be the quantified Boolean formula problem (usually abbreviated to QBF or TQBF; the T stands for "true"), a generalization of the first known NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problem, the Boolean satisfiability problem
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
(SAT). The satisfiability problem is the problem of whether there are assignments of truth values to variables that make a Boolean expression true. For example, one instance of SAT would be the question of whether the following is true:
The quantified Boolean formula problem differs in allowing both universal and existential quantification over the values of the variables:
-
.
The proof that QBF is a PSPACE-complete problem is essentially a restatement of the proof of Savitch's theorem
Savitch's theorem
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, states that for any function ƒ ≥ log,...
in the language of logic, and is a bit more technical.
Notice that the NP-complete problem resembles a typical puzzle: is there some way to plug in values that solves the problem? The PSPACE-complete problem resembles a game: is there some move I can make, such that for all moves my opponent might make, there will then be some move I can make to win? The question alternates existential and universal quantifiers. Not surprisingly, many puzzles turn out to be NP-complete, and many games turn out to be PSPACE-complete.
Examples of games that are PSPACE-complete (when 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...
so that they can be played on an n × n board) are the games hex
Hex (board game)
Hex is a board game played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as an 11x11 rhombus. Other popular dimensions are 13x13 and 19x19 as a result of the game's relationship to the older game of Go...
and 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...
and the solitaire games 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 ....
, Mahjong
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...
, 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...
, and 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....
. Some other generalized games, such as chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
, checkers (draughts), and Go
Go (board game)
Go , is an ancient board game for two players that originated in China more than 2,000 years ago...
are EXPTIME-complete 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.
Note that the definition of PSPACE-completeness is based on asymptotic complexity: the time it takes to solve a problem of size n, in the limit as n grows without bound. That means a game like checkers (which is played on an 8 × 8 board) could never be PSPACE-complete (in fact, they can be solved in constant time and space using a very large lookup table
Lookup table
In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
). That is why all the games were modified by playing them on an n × n board instead; in some cases, such as for Chess, these extensions are somewhat artificial and subjective.
Examples of PSPACE-complete problems
Following are a few PSPACE-complete problems with outlines of the algorithms showing that they are in PSPACE. More examples can be found at list of PSPACE-complete problems.TQBF
- Let TQBF = {
: F is a true fully quantified boolean formula }. On input F: - If F has no quantifier, evaluate and accept iff F is true.
- If F=
pF', recursively evaluate F'[p=1] and F'[p=0], accept iff both accept. - If F=
qF', recursively evaluate F'[q=1], F'[q=0] and accept iff at least one accept.
- Space Usage: The number of levels of recursion is equal to the number of variables of F. The amount of information stored at each level of recursion is constant (values of formula for p=0 and p=1). Therefore the total space used is linear.
Winning strategies for games
See Game complexityGame complexity
Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity.-Measures of game complexity:...
for more games whose completeness for PSPACE or other complexity classes has been determined.
Generalized geography
- On input
- If b has no outgoing edge, reject.
- Otherwise, remove b and all its edges, call this new graph G1.
- Recursively run on inputs
- Reject if all accept; otherwise accept.
- Space Usage: The number of levels of recursion is equal to the number of nodes in G. The amount of information stored at each level of recursion is equal to the number of nodes in G. Therefore the total space used is linear.
Determining if a regular expression generates all strings
Given a regular expressionRegular 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"...
R, determining whether it generates all strings (i.e., L(R) = Σ*) is PSPACE-complete.