PSPACE is a strict superset of the set of context-sensitive languages. The following facts are known, where ⊂ means "proper subset", and ⊆ means "subset":
There are three ⊆ symbols on the first line. It is known that at least one of them must be a ⊂, but it is not known which. It is widely suspected that all three are ⊂. A solution of the P vs. NP question (the second ⊆) is worth $1,000,000. It is also widely suspected that the ⊆ on the last line should be a ⊂.
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.
An alternative characterization of PSPACE is the set of problems decidable by an alternating Turing machine in polynomial time.
A logical characterization of PSPACE 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 decision problem is in PSPACE-complete if it is in PSPACE, and every problem in PSPACE can be reduced to it in polynomial time.
These problems are widely suspected to be outside of P and NP, but that is not known.
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.
PSPACE represents the class of languages that can be solved by a polynomial space bounded Turing machine.
Also, if one is given an unbounded amount of time yet a bound on space, it seems one should be able to solve more problems with those resources than if one were constrained to the same bound on time, yet unbounded space to work with, since time is required to use the unbounded space.
In contrast, for problems in PSPACE, their solutions are extremely hard to verify, yet checking that a solution exists is just as hard as it is for the P problems.
Feeds |
Contact