What makes any NP-complete problem also a PSPACE problem?

markgritter(59)

Published in

#tcs

Words

120

Reading

1 min

Listen

Play

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