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
Reformed churches

... Church of France reorganized, and was guaranteed toleration under the Edict of Nantes until final revocation of toleration in 1685. The periods of persecution scattered ...

 
 
 
This page was created in 26.6 ms