For any f(n), DTIME(f(n)) ⊆ SPACE(f(n)). This is because if you run for f(n) steps you can write to at most f(n) locations. (The reverse, of course, is not true.) The same applies for nondeterministic machines: NTIME(f(n)) ⊆ NSPACE(f(n))
Savitch's theorem says that NSPACE(f(n)) = SPACE(f(n)^2), that we can can convert a nondeterministic machine into a determinstic one at a cost of squaring its space usage, at most.
If f(n) is a polynomial, then f(n)^2 is a polynomial too.
Any problem X in NP is, by definition, time-bounded by some polynomial f(n), so
X ∈ NTIME(f(n)),
X ∈ NSPACE(f(n))
X ∈ SPACE(f(n)^2)
X ∈ PSPACE
Therefore, any NP problem is in PSPACE (including the NP-complete ones.)
Originally answered on Quora: https://www.quora.com/What-makes-any-NP-complete-problem-also-a-PSPACE-problem-in-the-complexity-theory-field/answer/Mark-Gritter
