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
This post has been voted on by the SteemSTEM curation team and voting trail in collaboration with @curie.
If you appreciate the work we are doing then consider voting both projects for witness by selecting stem.witness and curie!
For additional information please join us on the SteemSTEM discord and to get to know the rest of the community!
Downvoting a post can decrease pending rewards and make it less visible. Common reasons:
Submit