Encyclopedia > PSPACE

  Article Content

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 "strict 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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Photosynthesis

... yields oxygen plus sugar. In animal bodies, this is exactly reversed: oxygen plus sugar yields carbon dioxide plus water plus energy. However, it is important to note ...

 
 
 
This page was created in 22.5 ms