PSPACE

From Wikipedia, the free encyclopedia

Mathematicians and computer scientists try to carefully define different types of complexity, and PSPACE is one of these types. Roughly, PSPACE is all the problems which can be solved by programs which only need a polynomial (in the length of the problem instance specification) amount of memory to run. In the term "PSPACE", the P stands for polynomial, and SPACE refers to the amount of space, i.e. the amount of memory, that is needed.

The limitation to a polynomial amount of memory means that for the given problem there is some polynomial P(n), such that if the input is of length n, then the problem must be solvable using only P(n) memory. For example, since there is a program that can check whether two numbers (of any size) add up to a third number using much less than P(n) = 100n2+500 memory, where n is the total length (in numbers of digits) of the three numbers given to the program, this shows that addition is in PSPACE. Much harder problems are also in PSPACE.

Contents

[edit] Formal Definition

In complexity theory the class PSPACE is the set of decision problems that can be solved by a Turing machine using a polynomial amount of memory and unlimited time.

The formal definition of PSPACE is:

PSPACE = \bigcup_{k\in\mathbb{N}} \mbox{SPACE}(n^k)

PSPACE is a strict superset of the set of context-sensitive languages.

It turns out that allowing the Turing machine to be nondeterministic does not add any extra power. Because of Savitch's theorem, NPSPACE is equivalent to PSPACE, essentially because a deterministic Turing machine can simulate a nondeterministic Turing machine without needing much more space (even though it may use much more time).

[edit] Relation among other classes

A representation of the relation among complexity classes
A representation of the relation among complexity classes

The following relations are known between PSPACE and the complexity classes NL, P, NP, EXPTIME and EXPSPACE:

\mbox{NL} \subseteq \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PSPACE}
\mbox{PSPACE} \subseteq \mbox{EXPTIME} \subseteq \mbox{EXPSPACE}
\mbox{NL} \subsetneq \mbox{PSPACE} \subsetneq \mbox{EXPSPACE}

There are three \subseteq (subset or equal) symbols on the first line and two on the second line. It is known that, in each line, at least one of them must be a \subsetneq symbol, but it is not known which. It is widely suspected that all are \subsetneq.

In contrast, the containments in the third line are all known to be strict. The first follows from direct diagonalization (the space hierarchy theorem, \mbox{NL} \subsetneq \mbox{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 for examples of problems that are suspected to be in PSPACE but not in NP.

[edit] Other characterizations

An alternative characterization of PSPACE is the set of problems decidable by an alternating Turing machine in polynomial time, sometimes called APTIME or just AP.

A logical characterization of PSPACE from descriptive complexity theory is that it is the set of problems expressible in second-order logic with the addition of a transitive closure 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, 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.

[edit] PSPACE-completeness

A language B is PSPACE-complete if:

a) B \in PSPACE

b) For all A \in PSPACE, A \leq_p B

where A \leq_p B means that there is a polynomial-time many-one reduction 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.

[edit] References


[edit] External links


v • d • e
Important complexity classes (more)
P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH