PSPACE
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 definition is not affected by whether the Turing machine is deterministic or non-deterministic. So PSPACE=NPSPACE. The set PSPACE is a strict superset of the set of context-sensitive languages. The following facts are known, where  means "proper subset", and  means "subset" (unknown whether they are equal):
- NC P NP PSPACE
- NC PSPACE EXPSPACE
- PSPACE-Complete PSPACE
There are three symbols on the first line. It is known that at least one of them is a , but it is not known which. It is widely suspected that all three are . A proof of that for the middle one 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.
Referenced By
Complexity theory (computation) | Complexity theory in computation | Computability | Computation | Computational complexity | Computational complexity theory | Computations | EXPSPACE | EXPTIME | EXPTIME-complete | Game of Hex | Games/Hex | Hex (board game) | Hex (game) | Intractable problem | List of computability and complexity topics | List of mathematical topics (P-R) | PSPACE-Complete | Shannon switching game | Theory of computation
|
