PSPACE - Citizendia

Mathematicians and computer scientists try to carefully define different types of complexity, and PSPACE is one of these types. Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources 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) = 100n²+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.

1 Formal Definition
2 Relation among other classes
3 Other characterizations
4 PSPACE-completeness
5 References
6 External links

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. Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources 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 Turing machines are basic abstract symbol-manipulating devices which despite their simplicity can be adapted to simulate the logic of any Computer Algorithm

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. In Theoretical computer science, a context-sensitive language is a Formal language that can be defined by a Context-sensitive grammar.

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). In Computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970 states that for any function f ( n) ≥ log( n

Relation among other 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. In Computational complexity theory, NL (Nondeterministic Logarithmic-space is the Complexity class containing Decision problems which can be solved by a In Computational complexity theory, P, also known as PTIME or DTIME ( n O(1 is one of the most fundamental Complexity In Computational complexity theory, NP is one of the most fundamental Complexity classes The abbreviation NP refers to " N on-deterministic "EXP" redirects here for other uses see Exp. In Computational complexity theory, the Complexity class EXPTIME In complexity theory, EXPSPACE is the set of all Decision problems solvable by a deterministic Turing machine in O (2 p 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. In Computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems In Computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970 states that for any function f ( n) ≥ log( n 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. Mathematicians and computer scientists try to carefully define different types of complexity and PSPACE-complete is one of these types

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. In Computational complexity theory, an alternating Turing machine ( ATM) is a Non-deterministic Turing machine ( NTM) with a rule for accepting

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. Descriptive complexity is a branch of Finite model theory, a subfield of Computational complexity theory and Mathematical logic, which seeks to characterize In Logic and Mathematics second-order logic is an extension of First-order logic, which itself is an extension of Propositional logic. In Mathematics, the transitive closure of a Binary relation R on a set X is the smallest Transitive relation on X 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. In Computational complexity theory, the Complexity class PH is the union of all complexity classes in the Polynomial hierarchy: \mbox{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 Computational complexity theory, an interactive proof system is an Abstract machine that models Computation as the exchange of messages between two parties In computational complexity theory the class IP is the class of problems solvable by an Interactive proof system. 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-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. Mathematicians and computer scientists try to carefully define different types of complexity and PSPACE-complete is one of these types In Computational complexity theory a polynomial-time reduction is a reduction which is computable by a Deterministic Turing machine in Polynomial time 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.

References

The Complexity Zoo: PSPACE
Michael Sipser (1997). Michael Fredric Sipser is a Professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 8. 2–8. 3 (The Class PSPACE, PSPACE-completeness), pp. 281–294.
Christos Papadimitriou (1993). Christos Harilaos Papadimitriou (Χρίστος Χαριλάου Παπαδημητρίου is a Professor in the Computer Science Division at the University of California Computational Complexity, 1st edition, Addison Wesley. ISBN 0-201-53082-1. Chapter 19: Polynomial space, pp. 455–490.
Michael Sipser (2006). Michael Fredric Sipser is a Professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. Introduction to the Theory of Computation, 2nd edition, Thomson Course Technology. ISBN 0-534-95097-3. Chapter 8: Space Complexity

External links

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents