Relation Among Other Classes
The following relations are known between PSPACE and the complexity classes NL, P, NP, PH, EXPTIME and EXPSPACE (note that is not ):
It is known that in the first and second line, at least one of the set containments must be strict, but it is not known which. It is widely suspected that all are strict.
The containments in the third line are both known to be strict. The first follows from direct diagonalization (the space hierarchy theorem, ) and the fact that via Savitch's theorem. The second follows simply from the space hierarchy theorem.
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.
Read more about this topic: PSPACE
Famous quotes containing the words relation and/or classes:
“Parents ought, through their own behavior and the values by which they live, to provide direction for their children. But they need to rid themselves of the idea that there are surefire methods which, when well applied, will produce certain predictable results. Whatever we do with and for our children ought to flow from our understanding of and our feelings for the particular situation and the relation we wish to exist between us and our child.”
—Bruno Bettelheim (20th century)
“I have no doubt but that the misery of the lower classes will be found to abate whenever the Government assumes a freer aspect and the laws favor a subdivision of Property.”
—James Madison (1751–1836)