known to be strict. The first follows from direct diagonalization (the space hierarchy theorem, NL ? NPSPACE) and the fact that PSPACE NPSPACE 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.

Closure properties

1.Previous
3.Next