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 by ...
, PSPACE is the set of all
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 ...
s that can be solved by a
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
using a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
amount of space.
Formal definition
If we denote by SPACE(''t''(''n'')), the set of all problems that can be solved by
Turing machines
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algor ...
using ''O''(''t''(''n'')) space for some function ''t'' of the input size ''n'', then we can define PSPACE formally as
[Arora & Barak (2009) p.81]
:
PSPACE is a strict superset of the set of
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 ...
s.
It turns out that allowing the Turing machine to be
nondeterministic does not add any extra power. Because of
Savitch's theorem,
[Arora & Barak (2009) p.85] NPSPACE is equivalent to PSPACE, essentially because a deterministic Turing machine can simulate a
non-deterministic Turing machine
In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...
without needing much more space (even though
it may use much more time).
[Arora & Barak (2009) p.86] Also, the
complements of all problems in PSPACE are also in PSPACE, meaning that co-PSPACE PSPACE.
Relation among other classes
The following relations are known between PSPACE and the complexity classes
NL,
P,
NP,
PH,
EXPTIME and
EXPSPACE (note that ⊊, meaning strict containment, is not the same as ⊈):
:
From the third line, it follows that both in the first and in the second line, at least one of the set containments must be strict, but it is not known which. It is widely suspected that all are strict.
The containments in the third line are both known to be strict. The first follows from direct diagonalization (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 ...
, NL ⊊ NPSPACE) and the fact that PSPACE NPSPACE via
Savitch's theorem. The second follows simply from the space hierarchy theorem.
The hardest problems in PSPACE are the PSPACE-complete problems. See
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 ...
for examples of problems that are suspected to be in PSPACE but not in NP.
Closure properties
The class PSPACE is closed under operations
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
,
complementation, and
Kleene star
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics,
it is more commonly known as the free monoid ...
.
Other characterizations
An alternative characterization of PSPACE is the set of problems decidable by an
alternating Turing machine
In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. ...
in polynomial time, sometimes called APTIME or just AP.
[Arora & Barak (2009) p.100]
A logical characterization of PSPACE from
descriptive complexity
''Descriptive Complexity'' is a book in mathematical logic and computational complexity theory by Neil Immerman. It concerns descriptive complexity theory, an area in which the expressibility of mathematical properties using different types of log ...
theory is that it is the set of problems expressible in
second-order logic
In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory.
First-order logic quantifies onl ...
with the addition of a
transitive closure
In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite ...
operator. A full transitive closure is not needed; a commutative transitive closure and even weaker forms suffice. It is the addition of this operator that (possibly) distinguishes PSPACE from
PH.
A major result of complexity theory is that PSPACE can be characterized as all the languages recognizable by a particular
interactive proof system
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a ''prover'' and a ''verifier''. The parties interact by exchanging messages in order t ...
, the one defining the class
IP. In this system, there is an all-powerful prover trying to convince a randomized polynomial-time verifier that a string is in the language. It should be able to convince the verifier with high probability if the string is in the language, but should not be able to convince it except with low probability if the string is not in the language.
PSPACE can be characterized as the quantum complexity class
QIP.
PSPACE is also equal to P
CTC, problems solvable by classical computers using
closed timelike curve
In mathematical physics, a closed timelike curve (CTC) is a world line in a Lorentzian manifold, of a material particle in spacetime, that is "closed", returning to its starting point. This possibility was first discovered by Willem Jacob van Sto ...
s, as well as to BQP
CTC, problems solvable by
quantum computer
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
s using closed timelike curves.
PSPACE-completeness
A language ''B'' is ''
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 ...
'' if it is in PSPACE and it is PSPACE-hard, which means for all ''A'' ∈ PSPACE,
, where
means that there is a
polynomial-time many-one reduction
In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming ...
from ''A'' to ''B''. PSPACE-complete problems are of great importance to studying PSPACE problems because they represent the most difficult problems in PSPACE. Finding a simple solution to a PSPACE-complete problem would mean we have a simple solution to all other problems in PSPACE because all PSPACE problems could be reduced to a PSPACE-complete problem.
[Arora & Barak (2009) p.83]
An example of a PSPACE-complete problem is the
quantified Boolean formula problem (usually abbreviated to QBF or TQBF; the T stands for "true").
[
]
Notes
References
*
* Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp. 281–294.
* Chapter 19: Polynomial space, pp. 455–490.
* Chapter 8: Space Complexity
*
{{DEFAULTSORT:Pspace
Complexity classes