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
Shinnecock Hills, New York

... size is 3.00. In the town the population is spread out with 13.8% under the age of 18, 34.0% from 18 to 24, 17.6% from 25 to 44, 20.5% from 45 to 64, and 14.1% who are 65 ...

 
 
 
This page was created in 42.9 ms